Quick Reference
최근 넣은 항목부터 꺼내면 stack(LIFO), 먼저 넣은 항목부터 꺼내면 queue(FIFO), 우선순위가 가장 높은 항목부터 꺼내면 priority_queue를 씁니다. 세 컨테이너 모두 비어 있지 않은지 확인한 뒤 top 또는 front를 읽습니다.
cpp
#include <iostream>
#include <queue>
#include <stack>
int main() {
std::stack<int> stack; stack.push(10); stack.push(20); stack.pop();
std::queue<int> queue; queue.push(1); queue.push(2); queue.pop();
std::priority_queue<int> priority; priority.push(5); priority.push(1); priority.push(9);
std::cout << stack.top() << ' ' << queue.front() << ' ' << priority.top() << '\n';
}문법
컨테이너 어댑터 — 제한된 인터페이스로 접근 순서를 강제
세 컨테이너 모두 "어댑터"입니다. 내부적으로 다른 컨테이너(deque, vector)를 감싸고 특정 접근 규칙만 외부에 노출합니다. 임의 인덱스 접근이 없고 begin()/end()도 없습니다. 접근 순서가 자료구조의 핵심이기 때문입니다.
cpp
// stack의 내부 컨테이너는 deque (기본값)
std::stack<int, std::vector<int>> st; // vector를 내부 컨테이너로 사용
// queue의 내부 컨테이너는 deque (기본값)
std::queue<int, std::list<int>> q; // list를 내부 컨테이너로 사용
// priority_queue의 내부 컨테이너는 vector (기본값)
std::priority_queue<int, std::vector<int>> pq;stack — LIFO, DFS에 자연스럽게 맞음
push로 쌓고 top으로 확인하고 pop으로 제거합니다. 함수 호출 스택, DFS, 괄호 매칭 문제에 적합합니다.
cpp
// 괄호 매칭
std::stack<char> st;
for (char c : "({[]})") {
if (c == '(' || c == '{' || c == '[') st.push(c);
else if (!st.empty()) st.pop();
}
bool balanced = st.empty();queue — FIFO, BFS에 자연스럽게 맞음
push로 넣고 front로 앞쪽을 확인하고 pop으로 제거합니다. BFS, 작업 큐, 메시지 처리에 적합합니다.
cpp
// BFS 뼈대
std::queue<int> bfsQ;
bfsQ.push(start);
while (!bfsQ.empty()) {
int node = bfsQ.front();
bfsQ.pop();
for (int next : graph[node]) bfsQ.push(next);
}priority_queue — 최댓값 우선, 최솟값 우선 큐 패턴
기본값은 최댓값이 top()에 옵니다. 최솟값 우선이 필요하면 greater<T>를 비교자로 지정합니다.
cpp
// 최댓값 우선 (기본)
std::priority_queue<int> maxPQ;
maxPQ.push(3); maxPQ.push(1); maxPQ.push(4);
maxPQ.top(); // 4
// 최솟값 우선
std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;
minPQ.push(3); minPQ.push(1); minPQ.push(4);
minPQ.top(); // 1체크포인트
| 상황 | 적합한 선택 |
|---|---|
| 나중에 넣은 것 먼저 처리 (DFS, undo) | std::stack |
| 먼저 넣은 것 먼저 처리 (BFS, 작업 큐) | std::queue |
| 항상 가장 큰 값 먼저 처리 | std::priority_queue |
| 항상 가장 작은 값 먼저 처리 | priority_queue<T, vector<T>, greater<T>> |
| 스택의 내부를 vector로 | stack<T, vector<T>> |
주의할 점
stack/queue/priority_queue는 top()/front() 전에 반드시 empty() 검사가 필요합니다. 빈 컨테이너 접근은 정의되지 않은 동작입니다.
cpp
std::stack<int> st;
// ❌ 빈 stack에서 top()/pop() 호출 — 정의되지 않은 동작
int val = st.top(); // UB
st.pop(); // UB
// ✅ 항상 비어 있는지 먼저 확인
if (!st.empty()) {
int val = st.top();
st.pop();
}
// ❌ priority_queue는 전체 정렬된 순서가 아님
// top()은 최댓값 하나만 O(1)로 제공
// 전체를 정렬된 순서로 꺼내려면 while 루프 필요
std::priority_queue<int> pq{};
pq.push(3); pq.push(1); pq.push(4);
// pq[0] // 컴파일 오류 — 인덱스 접근 없음
while (!pq.empty()) { std::cout << pq.top(); pq.pop(); } // ✅참고 링크
2 sources