[C++] 스택과 큐

C++에서 데이터를 효율적으로 관리하기 위해 스택 (Stack)과 큐 (Queue)는 필수적인 자료구조다. 각각의 특성과 동작 방식이 다르며, 벡터 (Vector)와도 차이가 있다. 이전 글에서 배열과 리스트, 벡터에 대해 정리했던 적이 있으니 아래 글을 참고할 수 있다.

[C++] 배열과 리스트, 벡터

이 글에서는 스택과 큐의 개념과 활용법을 설명하고, 벡터와 비교하여 어떤 상황에서 적절한지를 살펴본다.

---

스택과 큐는 데이터가 들어가고 나가는 방법 (또는 통로)에 따라 차이가 있다.

- 스택 (Stack)

스택은 후입선출(LIFO, Last In First Out) 구조를 가지며, 나중에 삽입된 데이터가 먼저 제거된다. 흔히 접시를 쌓아 올리는 것과 유사하다. C++에서는 std::stack을 사용하여 스택을 구현할 수 있다.

스택의 주요 연산은 아래와 같이 정리할 수 있다.

• push(): 요소 추가 (맨 위에 삽입)
• pop(): 요소 제거 (맨 위 요소 제거)
• top(): 맨 위 요소 확인
• empty(): 스택이 비어 있는지 확인
• size(): 스택의 크기 확인

정의에서 알 수 있듯, 요소를 추가하고 제거하는 것이 한 위치 (가장 마지막에 들어온 그 위치)에서 모두 이루어진다. 쌓아올린 접시로 비유하면 가장 위층에 대해서만 데이터의 삽입과 제거가 이루어진다.

 

아래 예제의 출력을 보면 요소가 추가될 때에는 가장 뒤에 위치하고 가장 마지막에 있는 값이 제거되는 것을 알 수 있다.

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    
    cout << "Top: " << s.top() << endl; // 3
    s.pop();
    cout << "Top after pop: " << s.top() << endl; // 2
    return 0;
}

스택은 함수 호출 관리(재귀), 괄호 검사, 백트래킹(DFS) 등에서 자주 사용된다. 이들에 대해서는 추후에 정리할 기회가 올 것이다.

- 큐 (Queue)

큐는 선입선출(FIFO, First In First Out) 구조로 동작하며, 먼저 들어온 데이터가 먼저 나간다. 줄을 서서 순서대로 처리하는 방식과 비슷하다. C++에서는 std::queue를 사용하여 큐를 구현할 수 있다.

큐의 주요 연산은 스택과 거의 같으나 그 방법이 다르고 맨 앞과 뒤 두 요소를 확인할 수 있는 것을 볼 수 있다.

• push(): 요소 추가 (맨 뒤에 삽입)
• pop(): 요소 제거 (맨 앞 요소 제거)
• front(): 맨 앞 요소 확인
• back(): 맨 뒤 요소 확인
• empty(): 큐가 비어 있는지 확인
• size(): 큐의 크기 확인

아래 예제의 출력을 통해 큐의 동작 원리를 알 수 있을 것이다.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    
    cout << "Front: " << q.front() << endl; // 1
    q.pop();
    cout << "Front after pop: " << q.front() << endl; // 2
    return 0;
}

큐는 BFS(너비 우선 탐색), 작업 예약 시스템, 데이터 스트림 처리 등에서 많이 활용된다.

- 벡터와의 차이점

벡터에 대해서 알고 있으므로, 벡터와 어떤 차이가 있는지 알 수 있었다.

자료구조	삽입	삭제	접근
스택	push() (맨 위)	pop() (맨 위)	후입선출 (LIFO)
큐	push() (뒤쪽)	pop() (앞쪽)	선입선출 (FIFO)
벡터	push_back() (뒤쪽)	pop_back() (앞쪽)	임의 접근 가능 (Index Access)

스택과 큐는 특정한 위치에서만 삽입/삭제가 가능하기 때문에 항상 \( O(1) \)의 속도를 보장하지만, 벡터는 중간에 요소를 삽입하거나 삭제할 경우 전체 원소를 이동해야 하므로 \( O(n) \)의 비용이 발생할 수 있다. 그러나 원하는 위치의 요소에 접근할 수 있다는 점에서 스택이나 큐보다 유리하다.

알고리즘을 구현할 때 데이터 접근 방식에 대해 정의가 되면 그에 맞는 자료 구조를 사용하여 유리하게 할 수 있을 것이다.

---

정리하자면, 빠른 삽입/삭제가 필요하고, 특정한 순서(LIFO/FIFO)로 데이터를 다루는 상황이면 스택이나 큐를 사용하고, 데이터에 임의 접근이 필요하고 배열처럼 사용하면서 크기를 유동적으로 조정하는 상황이 있다면 벡터를 사용해야 한다.

적절한 자료구조를 선택하면 효율적인 프로그램 작성에 도움이 될 것이다.