pkglog
EN

C++ queue와 stack: 컨테이너 어댑터 사용법과 BFS·DFS 활용

작성 · · 14분 읽기 · 수정 초급 튜토리얼

이 글의 핵심

stack·queue·priority_queue는 deque나 vector를 감싸 연산을 일부러 제한한 컨테이너 어댑터입니다. 빈 컨테이너에서 top()을 부르면 예외가 아니라 정의되지 않은 동작이 되는 이유, pop()이 값을 돌려주지 않는 이유, priority_queue 비교자의 방향과 다익스트라에서 쓰는 지연 삭제 패턴을 DFS·BFS·스케줄링 예제와 함께 설명합니다.

LIFO·FIFO 개념과 코딩 테스트에서의 쓰임은 알고리즘 시리즈: 스택과 큐와 맞물려 있습니다.

자료구조 비교

특성stackqueuepriority_queue
순서LIFO (후입선출)FIFO (선입선출)우선순위
접근top()front(), back()top()
삽입push()push()push()
삭제pop()pop()pop()

stack 기본

std::stack은 원소를 넣은 순서의 역순으로 꺼내는 후입선출(LIFO) 자료구조로, 내부적으로는 원시 배열이나 연결 리스트를 직접 구현하는 대신 std::deque를 기본 컨테이너로 감싸는 컨테이너 어댑터(container adapter)로 구현되어 있습니다. push()로 맨 위에 원소를 쌓고, top()으로 맨 위 원소를 확인하고, pop()으로 맨 위 원소를 제거하는 세 가지 연산만으로 동작하는 단순한 인터페이스 덕분에, 함수 호출 스택 흉내나 괄호 짝 맞추기, 실행 취소(undo) 기능처럼 “가장 최근 것부터 처리해야 하는” 문제에 자연스럽게 들어맞습니다. 아래 예시는 push로 1, 2, 3을 순서대로 쌓은 뒤 top()과 pop()을 반복 호출하며 3, 2 순서로 값이 나오는 LIFO 동작을 직접 확인해 볼 수 있습니다.

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

int main() {
    stack<int> s;
    
    // 삽입
    s.push(1);
    s.push(2);
    s.push(3);
    
    // 맨 위 확인
    cout << s.top() << endl;  // 3
    
    // 제거
    s.pop();  // 3 제거
    cout << s.top() << endl;  // 2
    
    // 크기
    cout << s.size() << endl;
    
    // 비어있는지
    if (s.empty()) {
        cout << "비어있음" << endl;
    }

    return 0;
}

어댑터가 연산을 이렇게 줄여 둔 것은 불편을 주려는 것이 아니라 의도를 코드에 드러내기 위해서입니다. vector로도 스택을 흉내 낼 수 있지만, std::stack으로 선언하면 읽는 사람은 “이 컨테이너는 맨 위에서만 넣고 뺀다”는 것을 곧바로 알 수 있고, 누군가 실수로 중간 원소를 건드리는 코드를 쓰면 컴파일러가 막아 줍니다. 두 번째 템플릿 인자로 내부 컨테이너를 바꿀 수도 있습니다. stack<int, vector<int>>는 원소가 연속된 메모리에 놓여 캐시 효율이 좋고, 크기를 대략 안다면 내부 vector를 미리 reserve한 뒤 생성자로 넘겨 재할당을 줄일 수 있습니다. 기본값이 deque인 이유는 재할당 시 기존 원소를 옮기지 않아 원소의 주소가 유지되고, 크게 늘었다 줄어드는 경우에도 메모리를 블록 단위로 관리할 수 있기 때문입니다.

주의할 점은 빈 스택에서 top()이나 pop()을 호출하는 것이 예외가 아니라 정의되지 않은 동작이라는 것입니다. std::vector::at()처럼 범위를 검사해 주는 버전이 없으므로, 괄호 짝 맞추기처럼 입력에 따라 스택이 비어 있을 수 있는 코드에서 )를 만났을 때 s.top()부터 부르면 테스트 입력에서는 멀쩡하다가 ())같은 입력에서만 크래시가 납니다. 항상 empty()를 먼저 확인하는 습관이 필요하고, 디버그 빌드에서는 libstdc++의 -D_GLIBCXX_ASSERTIONS나 MSVC의 디버그 반복자 검사가 이런 호출을 단언 실패로 알려 줍니다.

queue 기본

std::queue는 stack과 반대로 넣은 순서 그대로 꺼내는 선입선출(FIFO) 자료구조로, 은행 창구 대기열이나 프린터 작업 대기열처럼 “먼저 온 것부터 먼저 처리해야 하는” 상황을 모델링하는 데 적합합니다. stack과 달리 양쪽 끝에 각각 다른 이름의 접근 함수가 있는데, push()는 뒤쪽(back)에 원소를 추가하고 front()는 맨 앞 원소를, back()은 맨 뒤 원소를 각각 확인할 수 있으며 pop()은 항상 맨 앞 원소를 제거합니다. 아래 예시에서 1, 2, 3을 순서대로 push한 뒤 front()를 확인하면 가장 먼저 넣은 1이 나오는 것을 볼 수 있고, 이는 뒤에서 다룰 BFS(너비 우선 탐색) 알고리즘이 queue를 핵심 자료구조로 사용하는 이유이기도 합니다.

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

int main() {
    queue<int> q;
    
    // 삽입
    q.push(1);
    q.push(2);
    q.push(3);
    
    // 앞/뒤 확인
    cout << q.front() << endl;  // 1
    cout << q.back() << endl;   // 3
    
    // 제거
    q.pop();  // 1 제거
    cout << q.front() << endl;  // 2
    
    return 0;
}

priority_queue 기본

std::priority_queue는 삽입 순서와 무관하게 항상 가장 우선순위가 높은 원소가 맨 위에 오도록 유지되는 자료구조로, 내부적으로는 힙(heap) 자료구조로 구현되어 삽입과 삭제 모두 O(log n) 시간에 처리됩니다. 별도로 비교 기준을 지정하지 않으면 기본값은 최대 힙이라 가장 큰 값이 항상 top()에 오지만, 세 번째 템플릿 인자로 greater<int>를 지정하면 비교 방향이 뒤집혀 가장 작은 값이 top()에 오는 최소 힙으로 동작합니다. 아래 예시에서 3, 1, 5, 2를 순서 없이 넣어도 pop()을 반복할 때마다 5, 3, 2, 1처럼 항상 큰 값부터 나오는 것을 볼 수 있으며, 이런 특성 덕분에 다익스트라 최단 경로 알고리즘이나 작업 스케줄링처럼 “항상 가장 급한 것부터 처리해야 하는” 문제에 널리 쓰입니다.

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

int main() {
    // 기본: 최대 힙 (큰 값이 top)
    priority_queue<int> pq;
    
    pq.push(3);
    pq.push(1);
    pq.push(5);
    pq.push(2);
    
    while (!pq.empty()) {
        cout << pq.top() << " ";  // 5 3 2 1
        pq.pop();
    }
    
    // 최소 힙 (작은 값이 top)
    priority_queue<int, vector<int>, greater<int>> minHeap;
    
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(5);
    
    cout << "\n최소 힙: " << minHeap.top();  // 1
    
    return 0;
}

실전 예시

stack과 queue의 진짜 활용 가치는 단순한 자료 저장을 넘어, 그래프나 트리를 탐색하는 알고리즘의 핵심 자료구조로 쓰일 때 드러납니다. 아래 세 가지 예시는 각각 stack 기반 DFS, queue 기반 BFS, priority_queue 기반 작업 스케줄링이라는 코딩 테스트와 실무 모두에서 자주 등장하는 패턴을 다룹니다.

예시 1: DFS (깊이 우선 탐색) - stack

깊이 우선 탐색은 한 방향으로 최대한 깊이 파고들다가 더 갈 곳이 없으면 되돌아오는 탐색 방식으로, stack의 LIFO 특성과 정확히 맞아떨어집니다. 아래 코드는 시작 노드를 stack에 넣고, stack에서 노드를 하나씩 꺼내며 아직 방문하지 않았다면 방문 처리를 하고 그 인접 노드들을 다시 stack에 쌓는 방식으로 동작하는데, 가장 최근에 쌓인 인접 노드가 먼저 처리되므로 자연스럽게 한 경로를 깊게 파고드는 탐색 순서가 만들어집니다.

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

void dfs(int start, vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    stack<int> s;
    
    s.push(start);
    
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        
        if (visited[node]) continue;
        
        visited[node] = true;
        cout << node << " ";
        
        // 인접 노드를 스택에 추가
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                s.push(neighbor);
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},    // 0의 인접 노드
        {0, 3, 4}, // 1의 인접 노드
        {0, 4},    // 2의 인접 노드
        {1},       // 3의 인접 노드
        {1, 2}     // 4의 인접 노드
    };
    
    cout << "DFS: ";
    dfs(0, graph);
    
    return 0;
}

설명: stack을 사용한 DFS 구현입니다. 깊이 우선으로 탐색하며, 백트래킹 문제에 자주 사용됩니다.

이 구현은 재귀 DFS와 방문 순서가 다르다는 점을 알아 두어야 합니다. 인접 노드를 {1, 2} 순서로 쌓으면 나중에 넣은 2가 먼저 꺼내지므로 0 2 4 1 3 순서가 되고, 재귀 DFS는 0 1 3 4 2 순서로 방문합니다. 둘 다 올바른 깊이 우선 탐색이지만, “문제의 예시 출력과 순서까지 같아야 하는” 코딩 테스트라면 인접 노드를 역순으로 쌓아야 재귀와 같은 순서가 됩니다. 또 방문 표시를 꺼낼 때 하므로 같은 노드가 스택에 여러 번 들어갈 수 있어, 간선이 많은 그래프에서는 스택 크기가 노드 수가 아니라 간선 수에 비례해 커집니다. 그래도 명시적 스택을 쓰는 이유는 재귀의 깊이 한계를 피하기 위해서입니다. 노드가 수십만 개인 경로 모양 그래프를 재귀로 탐색하면 기본 스택 크기(Linux에서 흔히 8MB, Windows는 1MB)를 넘어 스택 오버플로로 죽을 수 있습니다.

예시 2: BFS (너비 우선 탐색) - queue

너비 우선 탐색은 시작 노드에서 가까운 노드부터 한 단계씩 넓혀가며 탐색하는 방식으로, 이 순서를 정확히 지키려면 queue의 FIFO 특성이 필요합니다. 아래 코드는 큐에 {노드, 거리} 쌍을 넣어 시작 노드로부터의 거리를 함께 추적하면서, 먼저 큐에 들어온 노드(즉 더 가까운 노드)부터 처리하는 덕분에 목표 노드에 처음 도달했을 때의 거리가 항상 최단 거리임을 보장합니다. 만약 여기서 queue 대신 stack을 썼다면 깊이 우선으로 파고들어 최단 경로가 아닌 엉뚱한 경로를 먼저 찾아버렸을 것이므로, 이 예시는 자료구조 선택이 알고리즘의 정확성 자체를 좌우한다는 것을 잘 보여줍니다.

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

int bfs(vector<vector<int>>& graph, int start, int target) {
    vector<bool> visited(graph.size(), false);
    queue<pair<int, int>> q;  // {노드, 거리}
    
    q.push({start, 0});
    visited[start] = true;
    
    while (!q.empty()) {
        int node = q.front().first;
        int dist = q.front().second;
        q.pop();
        
        if (node == target) {
            return dist;  // 최단 거리 반환
        }
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push({neighbor, dist + 1});
            }
        }
    }
    
    return -1;  // 도달 불가
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 4},
        {1},
        {1, 2}
    };
    
    int distance = bfs(graph, 0, 3);
    cout << "0에서 3까지 최단 거리: " << distance << endl;
    
    return 0;
}

설명: queue를 사용한 BFS로 최단 경로를 찾습니다. 미로 찾기, 최단 거리 문제에 필수입니다.

DFS 예제와 달리 여기서는 노드를 큐에 넣을 때 방문 표시를 합니다. 꺼낼 때 표시하면 같은 노드가 여러 경로로 큐에 중복해서 들어가, 결과는 맞더라도 큐가 불필요하게 커지고 격자 미로 같은 문제에서는 시간 초과나 메모리 초과로 이어집니다. BFS가 최단 거리를 보장하는 것은 모든 간선의 가중치가 같을 때뿐이라는 점도 중요합니다. 간선마다 비용이 다르다면 다음 절의 priority_queue를 쓰는 다익스트라 알고리즘이 필요합니다.

예시 3: 작업 스케줄링 - priority_queue

우선순위가 다른 여러 작업을 처리 순서대로 관리해야 하는 스케줄러는 priority_queue를 활용하기에 이상적인 상황입니다. 아래 Task 구조체는 operator<를 오버로드해 priority 값이 높을수록 우선순위가 높다고 정의하고 있으며, 이 비교 연산자 덕분에 priority_queue<Task>에 작업을 순서 없이 넣어도 pop()을 반복할 때마다 항상 우선순위가 가장 높은 작업부터 꺼낼 수 있습니다. 커스텀 타입을 priority_queue에 넣으려면 이렇게 비교 기준을 반드시 정의해야 하는데, 이 부분은 뒤에서 다룰 “자주 발생하는 문제” 섹션에서 더 자세히 다룹니다.

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

struct Task {
    string name;
    int priority;
    int duration;
    
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 높은 우선순위가 먼저
    }
};

int main() {
    priority_queue<Task> tasks;
    
    tasks.push({"이메일 확인", 2, 10});
    tasks.push({"긴급 회의", 5, 60});
    tasks.push({"코드 리뷰", 3, 30});
    tasks.push({"점심 식사", 1, 60});
    tasks.push({"버그 수정", 4, 120});
    
    cout << "=== 작업 실행 순서 ===" << endl;
    int totalTime = 0;
    
    while (!tasks.empty()) {
        Task t = tasks.top();
        tasks.pop();
        
        cout << t.priority << ". " << t.name 
             << " (" << t.duration << "분)" << endl;
        totalTime += t.duration;
    }
    
    cout << "\n총 소요 시간: " << totalTime << "분" << endl;
    
    return 0;
}

설명: priority_queue로 우선순위 기반 스케줄링을 구현합니다. 작업 관리, 이벤트 처리에 활용됩니다.

priority_queue에는 알아 둘 제약이 두 가지 있습니다. 첫째, 우선순위가 같은 원소의 순서는 보장되지 않습니다. 힙은 안정 정렬이 아니므로, 같은 우선순위의 작업을 들어온 순서대로 처리하고 싶다면 Task에 증가하는 일련번호를 넣고 비교자에서 우선순위가 같을 때 번호로 한 번 더 비교해야 합니다. 둘째, 이미 들어간 원소의 우선순위를 바꾸거나 중간 원소를 지울 수 없습니다. 다익스트라 알고리즘에서 이 문제를 푸는 표준 방법은 “지연 삭제”입니다. 거리가 줄어들 때마다 새 항목을 그냥 다시 넣고, 꺼낼 때 if (d > dist[u]) continue;로 이미 더 짧은 거리로 처리된 옛 항목을 건너뜁니다. 큐에 항목이 더 쌓이지만 구현이 단순하고 실제로도 충분히 빠르기 때문에 대부분의 코드가 이 방식을 씁니다.

자주 발생하는 문제

stack, queue, priority_queue는 컨테이너 어댑터라는 특성 때문에 std::vector나 std::deque에 익숙한 개발자가 처음 접하면 당황하기 쉬운 제약들이 있습니다. 아래 세 가지는 특히 초보자가 자주 마주치는 컴파일 에러와 그 해결법입니다.

문제 1: stack/queue에서 직접 접근 불가

증상: stack[0] 또는 queue[1] 같은 접근 시 컴파일 에러

원인: stack과 queue는 인덱스 접근을 지원하지 않음. 컨테이너 어댑터는 내부 컨테이너(기본적으로 deque)를 감싸서 의도적으로 제한된 인터페이스만 노출하도록 설계되었기 때문에, 순서를 지키지 않고 임의 위치에 접근하는 연산 자체를 애초에 허용하지 않습니다. 이는 실수가 아니라 “LIFO/FIFO 규칙을 어기는 접근을 원천적으로 막는다”는 설계 의도가 반영된 결과입니다.

해결법:

// ❌ 컴파일 에러
stack<int> s;
s.push(1);
s.push(2);
cout << s[0];  // 에러!

// ✅ 방법 1: 모두 꺼내서 확인
stack<int> s;
s.push(1);
s.push(2);
s.push(3);

while (!s.empty()) {
    cout << s.top() << " ";
    s.pop();
}

// ✅ 방법 2: vector 사용
vector<int> v = {1, 2, 3};
cout << v[0];  // OK

// ✅ 방법 3: deque 사용 (양쪽 접근 가능)
#include <deque>
deque<int> dq;
dq.push_back(1);
dq.push_back(2);
cout << dq[0];  // OK
cout << dq.front();  // OK
cout << dq.back();   // OK

문제 2: pop()은 값을 반환하지 않음

증상: int x = s.pop(); 같은 코드가 컴파일 에러

원인: pop()은 void 반환 (값을 반환하지 않음). 이는 표준 라이브러리 설계상 의도적인 선택인데, 만약 pop()이 값을 반환하면서 동시에 원소를 제거한다면 반환값을 복사하는 도중 예외가 발생했을 때 원소가 이미 제거되었는지 아닌지 애매한 상황이 생겨 예외 안전성을 보장하기 어려워지기 때문입니다. 그래서 표준 라이브러리는 “확인”(top)과 “제거”(pop)를 항상 별개의 연산으로 분리해 두었습니다.

해결법:

// ❌ 컴파일 에러
stack<int> s;
s.push(10);
int x = s.pop();  // 에러! pop()은 void

// ✅ 올바른 코드
stack<int> s;
s.push(10);
int x = s.top();  // 값 확인
s.pop();          // 제거

// ✅ 한 줄로
int x = s.top(); s.pop();

// ✅ 헬퍼 함수
template<typename T>
T pop_value(stack<T>& s) {
    T value = s.top();
    s.pop();
    return value;
}

int x = pop_value(s);  // OK

문제 3: priority_queue 커스텀 비교

증상: 커스텀 타입을 priority_queue에 넣으면 에러

원인: operator< 또는 비교 함수 필요. priority_queue는 내부적으로 힙을 유지하기 위해 두 원소 중 어느 쪽이 더 “크다”고 볼 것인지 끊임없이 비교해야 하는데, int나 string처럼 표준 타입은 이미 < 연산자가 정의되어 있어 문제가 없지만 사용자 정의 구조체는 컴파일러가 두 값을 비교할 방법을 전혀 모르기 때문에 비교 기준을 직접 알려주어야 합니다.

해결법:

// ❌ 컴파일 에러
struct Person {
    string name;
    int age;
};

priority_queue<Person> pq;  // 에러!

// ✅ 방법 1: operator< 정의
struct Person {
    string name;
    int age;
    
    bool operator<(const Person& other) const {
        return age < other.age;  // 나이 많은 사람이 우선
    }
};

priority_queue<Person> pq;  // OK

// ✅ 방법 2: 비교 함수
struct PersonCompare {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age;
    }
};

priority_queue<Person, vector<Person>, PersonCompare> pq;  // OK

// ✅ 방법 3: 람다 (복잡함)
auto cmp = [](const Person& a, const Person& b) {
    return a.age < b.age;
};

priority_queue<Person, vector<Person>, decltype(cmp)> pq(cmp);

비교자 방향은 가장 헷갈리는 부분입니다. priority_queue의 비교자는 “a가 b보다 우선순위가 낮으면 true”를 뜻하므로, a.age < b.age는 나이가 많은 사람이 top()에 오는 최대 힙이 됩니다. 나이가 적은 사람부터 꺼내고 싶다면 a.age > b.age로 뒤집어야 합니다. std::sort에서 <가 오름차순인 것과 반대로 느껴지는 이유입니다. 또 비교자는 엄격한 약순서(strict weak ordering)를 지켜야 해서, < 대신 <=를 쓰면 같은 값끼리 서로 “더 작다”가 되어 정의되지 않은 동작이 됩니다. MSVC 디버그 빌드는 이런 비교자를 invalid comparator 단언으로 잡아 주지만, 릴리스 빌드에서는 힙 구조가 조용히 깨져 엉뚱한 순서가 나올 수 있습니다.

람다 비교자를 쓸 때 C++17까지는 람다 타입에 기본 생성자가 없어서 위처럼 pq(cmp)로 객체를 넘겨야 했고, 빠뜨리면 긴 템플릿 에러가 납니다. C++20부터는 캡처 없는 람다가 기본 생성 가능해져 priority_queue<Person, vector<Person>, decltype(cmp)> pq;만으로도 컴파일됩니다.

FAQ

Q1: stack과 queue는 언제 사용하나요?

A:

  • stack: 되돌리기(undo), 괄호 매칭, DFS, 함수 호출 스택
  • queue: BFS, 프린터 대기열, 작업 큐, 버퍼
  • priority_queue: 최단 경로(다익스트라), 작업 스케줄링, 힙 정렬

Q2: deque는 언제 사용하나요?

A: 양쪽에서 삽입/삭제가 필요할 때 사용합니다.

#include <deque>
deque<int> dq;

dq.push_front(1);  // 앞에 추가
dq.push_back(2);   // 뒤에 추가
dq.pop_front();    // 앞에서 제거
dq.pop_back();     // 뒤에서 제거

Q3: 최소 힙을 어떻게 만드나요?

A: greater를 사용합니다.

// 최대 힙 (기본)
priority_queue<int> maxHeap;

// 최소 힙
priority_queue<int, vector<int>, greater<int>> minHeap;

Q4: stack/queue의 크기를 미리 정할 수 있나요?

A: 아니요, 동적으로 크기가 조절됩니다. 고정 크기가 필요하면 배열이나 vector를 사용하세요.

Q5: 성능은 어떤가요?

A: 모든 연산이 O(1)입니다 (priority_queue는 O(log n)).

Q6: 여러 스레드에서 안전한가요?

A: 아니요, 멀티스레드 환경에서는 mutex로 보호해야 합니다. 특히 if (!q.empty()) { auto x = q.front(); q.pop(); }처럼 확인과 꺼내기가 나뉜 패턴은 두 연산을 각각 잠가도 그 사이에 다른 스레드가 원소를 가져갈 수 있으므로, 확인부터 제거까지를 한 번의 잠금 안에서 처리하고, 빈 큐를 기다려야 한다면 std::condition_variable과 함께 쓰는 작업 큐 클래스로 감싸는 것이 일반적입니다.

같이 보면 좋은 글