[자료구조] 스택(Stack)

자료구조 첫번째 시간의 주제를 스택입니다. 

 

사전에서는 "(깔끔하게 정돈하여) 쌓다[포개다]; 쌓이다, 포개지다" 정도로 설명되는 데요, 만약 저희가 뷔페에 가서 음식을 담을 접시를 사용할 때, 가장 위에부분을 가져가죠? 접시가 부족해서 다시 채울때도 위에 부터 다시 쌓습니다.

 

스택은 이와 똑같이 동작하는 데요, 스택을 LIFO(Last In First Out)구조를 유지합니다. 마지막에 들어가는 녀석이 처음 나오는 구조죠.

 

스택에 자료를 넣는 동작은 push, 빼는 동작은 pop이라고 합니다.

근데 만약, push할 때 스택이 모두 차있으면 어떻게 될까요 ? 이런 경우는 "stack overflow"라고 합니다. 

반대로 pop할 때, 스택이 비어있는 경우를 "stack underflow"라고 합니다.

 

 

그럼, 스택을 어떻게 구현하는지 알아봅시다.

class Stack {

    int top = -1;
    int[] stack;

    void create(int n) {
        stack = new int[n];
    }

    void push(int n) {
        if (top + 1 >= stack.length) {
            System.out.println("Overflow");
        } else {
            top++;
            stack[top] = n;
        }
    }

    void pop() {
        if (top < 0) {
            System.out.println("Underflow");
        } else {
            stack[top] = 0;
            top--;
        }
    }

    void peek() {
        if (top < 0) {
            System.out.println("NULL");
        } else {
            System.out.println(stack[top]);
        }
    }
}

create(n) : 먼저 n크기의 스택을 생성해 줍니다. 저는 여기서 스택을 배열로 구현했습니다.

push(n) : 먼저 스택에 공간이 있는지 검사하고, 데이터를 넣습니다. 만약 스택에 공간이 없다면 Overflow를 출력합니다.

pop() : 먼저 데이터가 있는지 검사하고, 데이터를 출력합니다. 만약 데이터가 없다면 Underflow를 출력합니다.

peek(n) : 스택에서 가장 위에있는 값을 출력합니다. 제거하지는 않고, 단순히 꺼내보기만 합니다.