C++ 컨테이너 어댑터 | stack·queue·priority_queue 완벽 가이드

C++ 컨테이너 어댑터 | stack·queue·priority_queue 완벽 가이드

· 28분 읽기 · 수정 초급 튜토리얼
C++ 컨테이너 어댑터 | stack·queue·priority_queue 완벽 가이드

이 글의 핵심

C++ 컨테이너 어댑터 stack (LIFO), queue (FIFO), priority_queue (힙)의 사용법과 실무 활용. DFS·BFS·다익스트라 알고리즘 구현, 괄호 검증, 작업 스케줄링 예제를 다룹니다.

들어가며

C++의 컨테이너 어댑터는 기존 컨테이너를 특정 인터페이스로 감싼 것입니다. stack (LIFO), queue (FIFO), priority_queue (힙) 세 가지가 있습니다. 비유로 말씀드리면, stack은 접시 쌓기 (마지막에 올린 것을 먼저 내림), queue는 줄 서기 (먼저 온 사람이 먼저 나감), priority_queue는 응급실 (우선순위가 높은 사람이 먼저 진료)에 가깝습니다.

이 글을 읽으면

  • stack, queue, priority_queue의 사용법을 이해합니다
  • 각 어댑터의 시간 복잡도를 파악합니다
  • DFS, BFS, 다익스트라 알고리즘을 구현합니다
  • 실무 활용 패턴과 주의사항을 확인합니다

컨테이너 어댑터 개요

비교표

어댑터자료구조삽입삭제접근기반 컨테이너
stackLIFOpushpoptopdeque (기본)
queueFIFOpushpopfront/backdeque (기본)
priority_queue힙pushpoptopvector (기본)

실전 구현

1) stack (LIFO)

#include <iostream>
#include <stack>
int main() {
    std::stack<int> s;
    
    // push
    s.push(1);
    s.push(2);
    s.push(3);
    
    // top
    std::cout << s.top() << std::endl;  // 3
    
    // pop
    s.pop();
    std::cout << s.top() << std::endl;  // 2
    
    // size
    std::cout << s.size() << std::endl;  // 2
    
    // empty
    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    std::cout << std::endl;  // 2 1
    
    return 0;
}

2) queue (FIFO)

#include <iostream>
#include <queue>
int main() {
    std::queue<int> q;
    
    // push
    q.push(1);
    q.push(2);
    q.push(3);
    
    // front/back
    std::cout << q.front() << std::endl;  // 1
    std::cout << q.back() << std::endl;   // 3
    
    // pop
    q.pop();
    std::cout << q.front() << std::endl;  // 2
    
    // size
    std::cout << q.size() << std::endl;  // 2
    
    // empty
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << std::endl;  // 2 3
    
    return 0;
}

3) priority_queue (힙)

#include <iostream>
#include <queue>
#include <vector>
int main() {
    // 최대 힙 (기본)
    std::priority_queue<int> maxHeap;
    
    maxHeap.push(3);
    maxHeap.push(1);
    maxHeap.push(4);
    maxHeap.push(2);
    
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " ";  // 4 3 2 1
        maxHeap.pop();
    }
    std::cout << std::endl;
    
    // 최소 힙
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    
    minHeap.push(3);
    minHeap.push(1);
    minHeap.push(4);
    minHeap.push(2);
    
    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";  // 1 2 3 4
        minHeap.pop();
    }
    std::cout << std::endl;
    
    return 0;
}

4) 기반 컨테이너 선택

#include <deque>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>
int main() {
    // stack (기본: deque)
    std::stack<int> s1;
    std::stack<int, std::vector<int>> s2;  // vector 기반
    std::stack<int, std::list<int>> s3;    // list 기반
    
    // queue (기본: deque)
    std::queue<int> q1;
    std::queue<int, std::list<int>> q2;
    
    // priority_queue (기본: vector)
    std::priority_queue<int> pq1;
    std::priority_queue<int, std::deque<int>> pq2;
    
    return 0;
}

고급 활용

1) 괄호 검증 (stack)

#include <iostream>
#include <stack>
#include <string>
bool isValid(const std::string& s) {
    std::stack<char> st;
    
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            
            char top = st.top();
            st.pop();
            
            if (c == ')' && top != '(') return false;
            if (c == '}' && top != '{') return false;
            if (c == ']' && top != '[') return false;
        }
    }
    
    return st.empty();
}
int main() {
    std::cout << isValid("()[]{}") << std::endl;     // 1
    std::cout << isValid("([)]") << std::endl;       // 0
    std::cout << isValid("{[()]}") << std::endl;     // 1
    
    return 0;
}

2) BFS (queue)

#include <iostream>
#include <queue>
#include <vector>
void bfs(const std::vector<std::vector<int>>& graph, int start) {
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        std::cout << node << " ";
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    std::cout << std::endl;
}
int main() {
    std::vector<std::vector<int>> graph = {
        {1, 2},     // 0 → 1, 2
        {0, 3, 4},  // 1 → 0, 3, 4
        {0, 4},     // 2 → 0, 4
        {1},        // 3 → 1
        {1, 2}      // 4 → 1, 2
    };
    
    bfs(graph, 0);  // 0 1 2 3 4
    
    return 0;
}

3) 다익스트라 (priority_queue)

#include <iostream>
#include <queue>
#include <vector>
using Edge = std::pair<int, int>;  // {거리, 노드}
std::vector<int> dijkstra(const std::vector<std::vector<Edge>>& graph, int start) {
    int n = graph.size();
    std::vector<int> dist(n, INT_MAX);
    std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [w, v] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}
int main() {
    std::vector<std::vector<Edge>> graph = {
        {{1, 1}, {4, 2}},  // 0 → 1(1), 2(4)
        {{2, 2}, {5, 3}},  // 1 → 2(2), 3(5)
        {{1, 3}},          // 2 → 3(1)
        {}                 // 3
    };
    
    auto dist = dijkstra(graph, 0);
    
    for (int i = 0; i < dist.size(); ++i) {
        std::cout << "0 → " << i << ": " << dist[i] << std::endl;
    }
    
    return 0;
}

출력:

0 → 0: 0
0 → 1: 1
0 → 2: 3
0 → 3: 4

성능 비교

시간 복잡도

연산stackqueuepriority_queue
pushO(1)O(1)O(log n)
popO(1)O(1)O(log n)
top/frontO(1)O(1)O(1)
sizeO(1)O(1)O(1)
emptyO(1)O(1)O(1)

실무 사례

사례 1: 작업 스케줄러

#include <iostream>
#include <queue>
#include <string>
#include <vector>
struct Task {
    int priority;
    std::string name;
    
    bool operator>(const Task& other) const {
        return priority > other.priority;  // 낮은 우선순위가 먼저
    }
};
int main() {
    std::priority_queue<Task, std::vector<Task>, std::greater<Task>> scheduler;
    
    scheduler.push({3, "낮은 우선순위"});
    scheduler.push({1, "높은 우선순위"});
    scheduler.push({2, "중간 우선순위"});
    
    while (!scheduler.empty()) {
        Task task = scheduler.top();
        scheduler.pop();
        
        std::cout << "실행: " << task.name << " (우선순위 " << task.priority << ")" << std::endl;
    }
    
    return 0;
}

출력:

실행: 높은 우선순위 (우선순위 1)
실행: 중간 우선순위 (우선순위 2)
실행: 낮은 우선순위 (우선순위 3)

사례 2: 되돌리기 (Undo)

#include <iostream>
#include <stack>
#include <string>
class TextEditor {
private:
    std::string text_;
    std::stack<std::string> history_;
    
public:
    void write(const std::string& str) {
        history_.push(text_);
        text_ += str;
    }
    
    void undo() {
        if (!history_.empty()) {
            text_ = history_.top();
            history_.pop();
        }
    }
    
    std::string getText() const {
        return text_;
    }
};
int main() {
    TextEditor editor;
    
    editor.write("Hello");
    std::cout << editor.getText() << std::endl;  // Hello
    
    editor.write(" World");
    std::cout << editor.getText() << std::endl;  // Hello World
    
    editor.undo();
    std::cout << editor.getText() << std::endl;  // Hello
    
    editor.undo();
    std::cout << editor.getText() << std::endl;  // (빈 문자열)
    
    return 0;
}

사례 3: 프린터 큐

#include <iostream>
#include <queue>
#include <string>
struct PrintJob {
    int priority;
    std::string document;
    
    bool operator<(const PrintJob& other) const {
        return priority < other.priority;  // 높은 우선순위가 먼저
    }
};
int main() {
    std::priority_queue<PrintJob> printer;
    
    printer.push({1, "문서1.pdf"});
    printer.push({3, "긴급.pdf"});
    printer.push({2, "문서2.pdf"});
    
    while (!printer.empty()) {
        PrintJob job = printer.top();
        printer.pop();
        
        std::cout << "인쇄: " << job.document << " (우선순위 " << job.priority << ")" << std::endl;
    }
    
    return 0;
}

출력:

인쇄: 긴급.pdf (우선순위 3)
인쇄: 문서2.pdf (우선순위 2)
인쇄: 문서1.pdf (우선순위 1)

사례 4: DFS (stack)

#include <iostream>
#include <stack>
#include <vector>
void dfs(const std::vector<std::vector<int>>& graph, int start) {
    std::vector<bool> visited(graph.size(), false);
    std::stack<int> s;
    
    s.push(start);
    
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        
        if (visited[node]) continue;
        
        visited[node] = true;
        std::cout << node << " ";
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                s.push(neighbor);
            }
        }
    }
    std::cout << std::endl;
}
int main() {
    std::vector<std::vector<int>> graph = {
        {1, 2},     // 0 → 1, 2
        {0, 3, 4},  // 1 → 0, 3, 4
        {0, 4},     // 2 → 0, 4
        {1},        // 3 → 1
        {1, 2}      // 4 → 1, 2
    };
    
    dfs(graph, 0);  // 0 2 4 1 3
    
    return 0;
}

트러블슈팅

문제 1: top() 후 pop() 누락

증상: 메모리 누수 또는 중복 처리

// ❌ pop 누락
std::stack<int> s;
s.push(1);
int x = s.top();
// s.pop() 누락!
// ✅ pop 호출
int x = s.top();
s.pop();

문제 2: empty() 체크 누락

증상: 미정의 동작

// ❌ 빈 스택
std::stack<int> s;
// std::cout << s.top() << std::endl;  // 미정의 동작
// ✅ empty() 체크
if (!s.empty()) {
    std::cout << s.top() << std::endl;
}

문제 3: priority_queue 순서 혼동

증상: 의도와 다른 순서

// 기본: 최대 힙
std::priority_queue<int> maxHeap;
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(4);
std::cout << maxHeap.top() << std::endl;  // 4 (최대값)
// 최소 힙
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
minHeap.push(3);
minHeap.push(1);
minHeap.push(4);
std::cout << minHeap.top() << std::endl;  // 1 (최소값)

문제 4: 반복자 미제공

증상: 순회 불가

// ❌ 반복자 없음
std::stack<int> s;
s.push(1);
s.push(2);
// for (int x : s) {}  // 에러: 반복자 없음
// ✅ pop으로 순회
while (!s.empty()) {
    std::cout << s.top() << " ";
    s.pop();
}

마무리

컨테이너 어댑터는 기존 컨테이너를 특정 인터페이스로 감싼 것입니다.

핵심 요약

  1. stack (LIFO)
    • push, pop, top
    • DFS, 괄호 검증, 되돌리기
    • O(1)
  2. queue (FIFO)
    • push, pop, front, back
    • BFS, 작업 큐
    • O(1)
  3. priority_queue (힙)
    • push, pop, top
    • 다익스트라, 작업 스케줄링
    • O(log n)
  4. 기반 컨테이너
    • stack/queue: deque (기본)
    • priority_queue: vector (기본)

선택 가이드

상황권장이유
DFSstackLIFO
BFSqueueFIFO
다익스트라priority_queue최소값
괄호 검증stackLIFO
작업 큐queueFIFO
작업 스케줄링priority_queue우선순위

코드 예제 치트시트

// stack
std::stack<int> s;
s.push(1);
s.top();
s.pop();
// queue
std::queue<int> q;
q.push(1);
q.front();
q.back();
q.pop();
// priority_queue (최대 힙)
std::priority_queue<int> maxHeap;
maxHeap.push(1);
maxHeap.top();
maxHeap.pop();
// priority_queue (최소 힙)
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

다음 단계

참고 자료

  • “The C++ Standard Library” - Nicolai M. Josuttis
  • “Effective STL” - Scott Meyers
  • cppreference: https://en.cppreference.com/w/cpp/container 한 줄 정리: stack은 LIFO, queue는 FIFO, priority_queue는 힙으로, 각각 DFS·BFS·다익스트라 등의 알고리즘에 활용된다.

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

관련 글

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. C++ 컨테이너 어댑터 완벽 가이드. stack (LIFO), queue (FIFO), priority_queue (힙)의 사용법과 실무 활용.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

이 글에서 다루는 키워드 (관련 검색어)

C++, container, stack, queue, priority_queue, STL 등으로 검색하시면 이 글이 도움이 됩니다.