YEAHx4YEAHx4

Stack, Queue, Deque

스택, 큐, 덱

YEAHx4

YEAHx4

2025-04-19
11 mins

Stack, Queue, Deque

스택, 큐, 덱은 세 자료구조 처럼 보이지만 실제로는 굉장히 유사합니다. 굉장히 다양하게 사용되는 필수적인 자료구조로서 나중에 살펴볼 수많은 알고리즘에 사용됩니다. 스택, 큐, 덱 모두 앞/뒤에서 자료를 삽입(insert)하고 빼낼(pop) 수 있으며 전부 \( O(1) \)에 수행되는 것이 핵심입니다. LinkedList를 사용해서 구현하기 때문에 양 끝의 데이터를 추가하고 제거하거나 읽는 것은 \( O(1) \)에 가능하지만 \( n \)번째 데이터를 읽는 연산은 \( O(n) \)의 시간복잡도를 갖습니다. 애초에 그런 작업이 필요했다면 이 자료구조가 적합하지 않은 경우입니다. 저 세 자료구조의 차이는 데이터를 넣을 수 있는 방향과 뺄 수 있는 방향의 차이입니다. 아래 그림을 봅시다.

stack-queue-deque

스택은 아래가 막힌 기다란 병 모양입니다. 어떤 데이터를 넣으면 제일 위에 쌓이고, 새로 데이터를 넣으면 그 데이터가 다시 맨 위에 올라와서 덮습니다. 그럼 아래가 막혀있으니 데이터는 맨 위에 있는 데이터가 나오겠죠. 즉, 1, 2번 순서대로 넣었으면 2, 1번 순서대로 나옵니다. 먼저 넣은 데이터일수록 마지막에 나오게 됩니다. 이것을 선입후출(First In Last Out, FILO) 또는 후입선출(Last In First Out, LIFO)라고 합니다.

큐는 한 쪽으로 넣어서 다른 쪽으로 뺄 수 있는 기다란 통로 모양입니다. 들어간 순서대로 나옵니다. 가장 직관적으로 이해하기 쉬운 모양입니다. 큐는 순서대로 나온다는 특징 덕분에 앞으로 해야할 일을 저장해 놓는 방식으로 많이 씁니다. 이렇게 먼저 들어간 데이터가 먼저 나오는 구조를 선입선출(First In First Out, FIFO) 또는 후입후출(Last In Last Out, LILO)라고 합니다.

덱은 가장 자유로운 형태로 어느 방향에서도 넣을 수 있고 어느 방향에서도 뺄 수 있습니다. 따라서 위 그림에서 Data1과 Data2 중 어느 것이 먼저 들어왔는지는 저 그림만 보고 알 수 없습니다. 이중 연결 리스트(Doubly Linked List)를 통해 구현되며 양쪽을 전부 사용해야 하는 특수한 경우에 사용하게 됩니다.

스택, 큐, 덱은 C++, Python 에서 서로 다른 모습으로 구현되어 있기 때문에 개념을 먼저 살펴본 후 각 언어별로 어떻게 사용하는지 알아보겠습니다.

C++

C++에는 stack, queue, deque헤더가 따로 있고 stack<T>, queue<T>, deque<T> 클래스가 구현되어 있습니다. 사용법은 다음과 같습니다.

int main() {
    int n; cin >> n;
    stack<int> s;

    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        s.push(x);                 // 값 추가
    }

    while (!s.empty()) {
        cout << s.top() << " ";    // 맨 위의 값 읽기 (제거X)
        s.pop();                   // 맨 위의 값 제거 (읽기X)
    }
}

Python

파이썬에는 stack, queue가 따로 구현되어 있지 않고 collections 모듈에 deque만 구현되어 있습니다. deque 하나로 stack, queue 모두 deque로 같은 동작을 만들 수 있으니 deque하나로 전부 사용합니다. stack은 리스트로도 같은 동작을 할 수 있습니다. 다만 queue는 맨 앞의 요소를 ArrayList에서 제거하면 \( O(n) \)의 시간이 걸리기 때문에 deque을 사용해야 합니다.

stack = []
stack.append(1)   # push
stack.append(2)
print(stack.pop())  # pop → 2
print(stack)        # [1]

연습문제