C++ stack·queue·priority_queue: 컨테이너 어댑터로 DFS·BFS·다익스트라 구현하기
이 글의 핵심
컨테이너 어댑터는 pop()이 값을 반환하지 않아 top()이나 front()를 먼저 호출해야 하고, 빈 상태에서 호출하면 정의되지 않은 동작이 됩니다. priority_queue가 기본으로 최대 힙이라는 점, 반복자를 제공하지 않아 내부를 순회할 수 없는 제약을 짚어 알고리즘 문제와 실무 코드에서 흔한 실수를 피하도록 돕습니다.
들어가며
C++의 컨테이너 어댑터는 기존 컨테이너를 특정 인터페이스로 감싼 것입니다. stack (LIFO), queue (FIFO), priority_queue (힙) 세 가지가 있습니다. 비유로 말씀드리면, stack은 접시 쌓기 (마지막에 올린 것을 먼저 내림), queue는 줄 서기 (먼저 온 사람이 먼저 나감), priority_queue는 응급실 (우선순위가 높은 사람이 먼저 진료)에 가깝습니다.
어댑터라는 이름은 디자인 패턴의 어댑터처럼 이미 있는 컨테이너의 인터페이스를 좁혀서 다른 모양으로 보이게 한다는 뜻입니다. std::stack은 내부의 deque가 할 수 있는 수많은 연산 중 push_back, pop_back, back만 push, pop, top이라는 이름으로 노출합니다. 기능을 빼는 것이 목적이라는 점이 중요합니다. 스택으로 쓰기로 한 자료구조에서 누군가 중간 원소를 지우는 코드를 쓸 수 없게 막아, 코드를 읽는 사람이 “이 데이터는 LIFO로만 다뤄진다”고 믿을 수 있게 해 줍니다.
컨테이너 어댑터 개요
비교표
| 어댑터 | 자료구조 | 삽입 | 삭제 | 접근 | 기반 컨테이너 |
|---|---|---|---|---|---|
| stack | LIFO | push | pop | top | deque (기본) |
| queue | FIFO | push | pop | front/back | deque (기본) |
| priority_queue | 힙 | push | pop | top | vector (기본) |
실전 구현
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;
}처음 보면 가장 어색한 점은 pop()이 값을 돌려주지 않는다는 것입니다. 다른 언어처럼 int x = s.pop();을 기대하지만 C++에서는 top()으로 읽고 pop()으로 지우는 두 단계가 필요합니다. 이 설계는 예외 안전성 때문입니다. pop()이 원소를 값으로 반환하려면 내부에서 원소를 지운 뒤 복사해 돌려줘야 하는데, 그 복사 생성자가 예외를 던지면 원소는 이미 컨테이너에서 사라졌고 호출자는 값을 받지도 못해 데이터가 유실됩니다. 읽기와 삭제를 나누면 읽기(top(), 참조 반환)가 실패해도 컨테이너는 그대로입니다. top()은 참조를 돌려주므로 const auto& x = s.top(); s.pop();처럼 참조로 받은 뒤 pop()하면 댕글링 참조가 된다는 점도 조심해야 합니다.
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;
}queue의 기본 기반 컨테이너가 vector가 아니라 deque인 이유는 앞에서 빼는 연산 때문입니다. vector는 맨 앞 원소를 지우면 나머지를 모두 한 칸씩 당겨야 해서 O(n)이고, pop_front 자체가 없어 std::queue<int, std::vector<int>>는 pop()을 호출하는 순간 컴파일 에러가 납니다. deque는 여러 개의 고정 크기 블록으로 이루어져 양 끝의 삽입·삭제가 O(1)입니다.
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;
}최소 힙을 만들 때 std::greater를 쓰는 규칙이 직관과 반대라서 자주 헷갈립니다. priority_queue의 비교자는 “a가 b보다 뒤에 나와야 하는가(우선순위가 낮은가)“를 묻습니다. 기본값 std::less는 작은 값을 우선순위가 낮다고 보므로 가장 큰 값이 top()에 오고, std::greater를 주면 반대가 됩니다. 비교자를 바꾸려면 두 번째 인자인 기반 컨테이너(std::vector<int>)도 반드시 함께 적어야 합니다. 템플릿 인자는 순서대로만 지정할 수 있기 때문입니다. 원소가 정수라면 값을 음수로 넣어 최대 힙을 최소 힙처럼 쓰는 요령도 있지만, INT_MIN을 뒤집으면 오버플로가 나므로 비교자를 쓰는 편이 안전합니다.
내부적으로 priority_queue는 std::make_heap, std::push_heap, std::pop_heap을 vector에 적용한 것입니다. 그래서 top()은 O(1)이지만 전체가 정렬되어 있지는 않고, 두 번째로 큰 원소가 어디 있는지는 알 수 없습니다.
기반 컨테이너 선택
#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;
}기반 컨테이너는 어댑터가 호출하는 멤버 함수만 제공하면 됩니다. stack은 back/push_back/pop_back, queue는 여기에 front/pop_front, priority_queue는 임의 접근 반복자와 front/push_back/pop_back이 필요합니다. stack을 vector 기반으로 바꾸면 메모리가 연속이라 캐시 효율이 좋고 reserve로 재할당을 줄일 수 있지만, 크기가 커질 때 전체 재할당이 일어나는 순간이 있습니다. deque는 재할당 없이 블록만 추가하므로 최악의 경우가 부드럽습니다. list는 원소마다 노드를 할당해 대부분의 경우 가장 느리므로, 특별한 이유가 없으면 기본값을 쓰는 것이 무난합니다.
고급 활용
괄호 검증 (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;
}괄호 검증이 스택에 딱 맞는 이유는 “가장 최근에 연 괄호가 가장 먼저 닫혀야 한다”는 규칙이 곧 LIFO이기 때문입니다. 코드에서 놓치기 쉬운 경계는 두 곳입니다. 닫는 괄호가 나왔는데 스택이 비어 있으면(")(") 즉시 실패해야 하고, 문자열이 끝났을 때 스택에 남은 여는 괄호가 있으면("((") 역시 실패입니다. 마지막 return st.empty();가 두 번째 경우를 처리합니다. 이 함수는 괄호 외의 문자도 모두 닫는 괄호로 취급하므로, 실제 수식 검증에 쓰려면 괄호가 아닌 문자는 건너뛰는 분기를 추가해야 합니다.
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;
}BFS에서 visited를 큐에 넣을 때 표시하는 것이 중요합니다. 꺼낼 때 표시하면 같은 노드가 여러 이웃에서 발견될 때마다 큐에 중복으로 들어가, 밀집한 그래프에서는 큐가 간선 수만큼 커지고 같은 노드를 여러 번 처리합니다. 결과는 맞게 나오는 경우가 많아서 코딩 테스트에서 시간 초과나 메모리 초과로만 드러나는 흔한 실수입니다.
다익스트라 (priority_queue)
#include <climits>
#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: 4pair를 {거리, 노드} 순서로 두는 데는 이유가 있습니다. std::pair의 비교는 첫 번째 원소부터 사전식으로 하므로, std::greater<Edge>가 자연스럽게 “거리가 짧은 것 먼저”가 됩니다. 순서를 {노드, 거리}로 바꾸면 노드 번호 순으로 꺼내져 다익스트라가 아니게 되는데, 작은 예제에서는 결과가 우연히 맞기도 해서 발견이 늦어집니다. 도달할 수 없는 노드는 INT_MAX로 남으므로 출력 전에 확인해야 하고, 가중치 합이 int 범위를 넘을 수 있는 입력이라면 거리 타입을 long long으로 바꿔야 dist[u] + w가 오버플로하지 않습니다. 음수 가중치가 있으면 다익스트라 자체가 성립하지 않으므로 벨만-포드를 써야 합니다.
성능 비교
시간 복잡도
| 연산 | stack | queue | priority_queue |
|---|---|---|---|
| push | O(1) | O(1) | O(log n) |
| pop | O(1) | O(1) | O(log n) |
| top/front | O(1) | O(1) | O(1) |
| size | O(1) | O(1) | O(1) |
| empty | O(1) | O(1) | O(1) |
표의 O(1)은 기반 컨테이너가 deque일 때 기준이고, vector 기반 stack의 push는 재할당 때문에 분할 상환(amortized) O(1)입니다. priority_queue에 n개를 하나씩 push하면 O(n log n)이지만, 이미 모인 데이터로 만들 때는 반복자 쌍을 받는 생성자(std::priority_queue<int> pq(v.begin(), v.end());)가 내부적으로 make_heap을 써서 O(n)에 힙을 만듭니다.
실무 사례
사례 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)std::greater<Task>는 Task의 operator>를 호출하므로, 구조체에 operator>를 정의해 둔 것입니다. 실무 스케줄러에서 주의할 점은 우선순위가 같은 작업의 순서가 보장되지 않는다는 것입니다. 힙은 안정 정렬이 아니므로, 같은 우선순위로 먼저 넣은 작업이 나중에 실행될 수 있습니다. 먼저 들어온 순서를 지켜야 한다면 Task에 증가하는 순번(seq)을 두고 우선순위가 같을 때 순번으로 비교해야 합니다. 또 top()은 const 참조를 돌려주므로 std::move(scheduler.top())으로 꺼낼 수 없고 항상 복사됩니다. 작업 객체가 크다면 std::unique_ptr<Task>나 인덱스를 큐에 넣는 방식이 낫습니다.
사례 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;
}이 되돌리기 구현은 편집할 때마다 전체 텍스트 사본을 스택에 쌓습니다. 짧은 예제에서는 문제없지만, 문서가 커질수록 편집 한 번마다 문서 크기만큼 메모리를 쓰게 됩니다. 실제 편집기는 “무엇을 바꿨는지”만 기록하는 커맨드 패턴(삽입 위치와 문자열, 삭제한 범위와 내용)을 스택에 넣고, 되돌릴 때 그 역연산을 적용합니다. 다시 실행(redo)까지 지원하려면 되돌린 커맨드를 두 번째 스택에 옮기고, 새 편집이 들어오면 그 스택을 비우는 구조가 일반적입니다.
사례 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() 누락
증상: 같은 원소를 반복 처리하거나, while (!s.empty()) 루프가 끝나지 않음
// ❌ pop 누락
std::stack<int> s;
s.push(1);
int x = s.top();
// s.pop() 누락!
// ✅ pop 호출
int x = s.top();
s.pop();top()만 읽고 pop()을 빠뜨리면 원소가 계속 남아 같은 값을 반복해서 처리하게 되고, 루프 조건이 !s.empty()라면 무한 루프가 됩니다. 메모리가 새는 것은 아니지만 CPU 100%로 프로그램이 멈춘 것처럼 보입니다. 반대로 pop()을 두 번 호출하는 실수는 원소를 건너뛰게 만들고, 스택이 비어 있다면 정의되지 않은 동작이 됩니다.
문제 2: empty() 체크 누락
증상: 미정의 동작
// ❌ 빈 스택
std::stack<int> s;
// std::cout << s.top() << std::endl; // 미정의 동작
// ✅ empty() 체크
if (!s.empty()) {
std::cout << s.top() << std::endl;
}빈 어댑터에서 top()·front()·pop()을 호출하면 예외가 아니라 정의되지 않은 동작입니다. 릴리스 빌드에서는 쓰레기 값을 읽거나 조용히 메모리를 망가뜨리고 한참 뒤에 크래시가 나기도 합니다. 디버그 모드에서는 MSVC가 deque empty before pop 같은 assertion으로 멈추고, libstdc++는 -D_GLIBCXX_ASSERTIONS를 켜면 같은 검사를 해 주므로 테스트 빌드에는 이 옵션을 켜 두면 좋습니다.
문제 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();
}pop으로 순회하면 어댑터가 비워지므로, 내용을 보존해야 한다면 복사본(auto copy = s;)을 만들어 비우거나, 처음부터 std::vector나 std::deque를 직접 쓰는 편이 맞습니다. 디버깅 중 내용을 보고 싶을 뿐이라면, 어댑터의 기반 컨테이너가 protected 멤버 c로 선언되어 있다는 점을 이용해 파생 클래스에서 c에 접근하는 방법도 있지만, 운영 코드에서 쓸 만한 패턴은 아닙니다. 순회가 자주 필요하다는 것 자체가 어댑터가 아닌 컨테이너를 써야 한다는 신호입니다.
마무리
컨테이너 어댑터는 기존 컨테이너를 특정 인터페이스로 감싼 것입니다.
핵심 요약
- stack (LIFO)
- push, pop, top
- DFS, 괄호 검증, 되돌리기
- O(1)
- queue (FIFO)
- push, pop, front, back
- BFS, 작업 큐
- O(1)
- priority_queue (힙)
- push, pop, top
- 다익스트라, 작업 스케줄링
- O(log n)
- 기반 컨테이너
- stack/queue: deque (기본)
- priority_queue: vector (기본)
선택 가이드
| 상황 | 권장 | 이유 |
|---|---|---|
| DFS | stack | LIFO |
| BFS | queue | FIFO |
| 다익스트라 | priority_queue | 최소값 |
| 괄호 검증 | stack | LIFO |
| 작업 큐 | queue | FIFO |
| 작업 스케줄링 | 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;다음 단계
- queue/stack: C++ queue/stack
- 힙 알고리즘: C++ 힙 알고리즘
- 수치 알고리즘: C++ 수치 알고리즘
참고 자료
- “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·다익스트라 등의 알고리즘에 활용됩니다.
같이 보면 좋은 글
- C++ queue와 stack
- C++ make_heap·push_heap·pop_heap: priority_queue 대신 힙을 직접 다룰 때
- C++ Algorithm Numeric | accumulate·reduce
자주 묻는 질문 (FAQ)
Q. priority_queue로 다익스트라를 구현할 때 거리 갱신(decrease-key)은 어떻게 처리하나요?
A. std::priority_queue에는 이미 들어간 원소의 우선순위를 바꾸는 연산이 없으므로, 더 짧은 거리를 찾을 때마다 (거리, 노드) 쌍을 새로 push합니다. 대신 pop한 거리가 현재 기록된 dist[u]보다 크면 이미 낡은 항목이므로 본문 코드의 if (d > dist[u]) continue;처럼 건너뜁니다. 이 지연 삭제 방식은 큐에 중복 항목이 쌓여 크기가 간선 수만큼 커질 수 있지만, 구현이 단순하고 대부분의 입력에서 충분히 빠릅니다.