스택(stack)

conbrio·2022년 3월 5일

스택이란?

스택이란 그 접근방법이 제한적인 일종의 나열식 자료구조로써 후입선출(LIFO; Last In First Out)의 특징을 가집니다.

LIFO : Last In First Out. 나중(가장 최근)에 들어간 것이 먼저 나온다는 뜻
FIFO : First In First Out. 먼저(가장 오래전)에 들어간 것이 먼저 나온다는 뜻

쉽게 말해서 위 그림과 같이 바닥이 막힌 깊은 상자를 생각하면 됩니다. 나중에 넣은 물건이 위에 있으므로, 위에 있는 물건부터 먼저 꺼낼 수 밖에 없습니다.

스택의 연산

스택 자료구조의 구현을 위해 top(스택의 가장 위에 쌓인 데이터)을 가리키는 포인터를 유지해야합니다. 스택의 가장 윗 부분에 새로운 데이터를 추가하거나 꺼내는 연산은 스택의 현재 top 위치가 어디인지 가리키는 요소 없이는 불가능하기 때문입니다.

다음은 일반적으로 스택에 사용되는 연산들입니다.

push(item)

새로운 item을 스택의 가장 위에 추가합니다.
top = top + 1

pop()

스택의 가장 위에 있는 item이 제거되며, 반환합니다.
언어에 따라서는 return은 안해주는 경우도 있습니다.
스택이 비어있다면 불능입니다.
top = top - 1

peek()

스택의 가장 위에 있는 항목을 반환합니다.
스택이 비어있다면 불능입니다.

isEmpty

스택이 비어있는지 아닌지 true, false 값으로 반환합니다.

테스트

다음은 Java에서 제공하는 Stack 클래스를 이용하여 위 연산들을 확인해 본 것입니다. 일반적으로 대부분의 언어에서 직접 구현하지 않아도 왠만한 자료구조는 사용할 수 있도록 제공합니다.

import java.util.Stack;

public class StackTest {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // System.out.println(stack.peek()); // EmptyStackException
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.peek());
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
        // System.out.println(stack.pop()); // EmptyStackException
    }
}