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, 다익스트라 알고리즘을 구현합니다
- 실무 활용 패턴과 주의사항을 확인합니다
목차
컨테이너 어댑터 개요
비교표
| 어댑터 | 자료구조 | 삽입 | 삭제 | 접근 | 기반 컨테이너 |
|---|---|---|---|---|---|
| stack | LIFO | push | pop | top | deque (기본) |
| queue | FIFO | push | pop | front/back | deque (기본) |
| priority_queue | 힙 | push | pop | top | vector (기본) |
실전 구현
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성능 비교
시간 복잡도
| 연산 | 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) |
실무 사례
사례 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();
}마무리
컨테이너 어댑터는 기존 컨테이너를 특정 인터페이스로 감싼 것입니다.
핵심 요약
-
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 | “자료구조” 완벽 정리 [BFS/DFS 활용]
- C++ Algorithm Heap | “힙 알고리즘” 가이드
- C++ Algorithm Numeric | “수치 알고리즘” 가이드
관련 글
- C++ queue/stack |