숏컷 코드
cpp
#include <stack>
#include <queue>
std::stack<int> st;
st.push(10); st.push(20);
st.pop(); // 20 제거
int top = st.top(); // 10
std::queue<int> q;
q.push(1); q.push(2);
q.pop(); // 1 제거
int front = q.front(); // 2
std::priority_queue<int> pq;
pq.push(5); pq.push(1); pq.push(9);
int max = pq.top(); // 9 (최댓값 우선)문법
컨테이너 어댑터 — 제한된 인터페이스로 접근 순서를 강제
세 컨테이너 모두 "어댑터"입니다. 내부적으로 다른 컨테이너(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