[기초 자료구조] Stack

1. Stack 이란?

• LIFO 방식으로 데이터를 저장하는 자료구조 입니다.

 

LIFO

• Last-In, First Out
• 가장 나중에 들어온 데이터가 가장 먼저 나가는 방식을 의미합니다.

 

2. 연산

push	맨 위에 항목을 추가합니다.	O(1)
pop	맨 위에 항목을 반환하고 제거합니다.	O(1)
peek	맨 위에 항목을 반환합니다.	O(1)

 

 

3. 사용 사례

Undo / Redo	애플리케이션 사용중, 최근 수행한 명령을 취소 / 취소한 명령을 다시실행 하는 기능으로 사용합니다.
call stack	운영체제에서 프로그램의 함수 호출을 관리하기 위해 사용합니다.
괄호 짝 맞추기	수식의 괄호가 문법에 맞게 작성되었는지 확인하는데 사용합니다.
문자열 역순으로 변환하기	문자열을 역순으로 바꾸는데 사용합니다.
후위 표기법으로 변환하기	수식을 후위 표기법으로 변환하는데 사용합니다.

 

4. Stack Overflow / Underflow

Stack Overflow

• Stack에 할당된 메모리 용량이 초과된 상황에서 요소를 추가하려 할 때 발생하는 오류

 

사례

• 재귀함수 : 스레드가 재귀함수를 호출할 때, 깊이가 너무 깊어져 스택 메모리의 용량을 초과합니다.

 

Stack Underflow

• Stack에 할당된 요소가 없는 상황에서 요소를 제거하려 할 때 발생하는 예외

 

5. 구현

public class MyStack<T> {

    final T[] arr;
    final int size;
    int top;

    public MyStack(int size) {
        this.arr = (T[]) new Object[size];
        this.size = size;
        this.top = -1;
    }

    public void push(T item) {
        fullCheck();

        arr[++top] = item;
    }

    public T pop() {
        emptyCheck();

        return arr[top--];
    }

    public T peek() {
        return arr[top];
    }

    private void emptyCheck() {
        if (top == -1) throw new IllegalStateException("empty");
    }

    private void fullCheck() {
        if (top == size-1) throw new IllegalStateException("full");
    }
}

 

 

출처

• Wiki - Stack
• Wiki - Stack (eng)