[C++] Stack 와 Queue 의 이해

1️⃣ Stack & Queue는 ‘컨테이너 어댑터’다

C++ STL에서 stack과 queue는 사실 이렇게 만들어져 있다.

stack  → 내부적으로 deque 사용
queue  → 내부적으로 deque 사용

 

즉,

Stack과 Queue는 새로운 자료구조가 아니라

기존 컨테이너(deque)를 특정 규칙으로 제한한 인터페이스다.

 

그래서 이를 Container Adapter라고 부른다.

 

구조	허용되는 연산
stack	push, pop, top
queue	push, pop, front, back
deque	양쪽 삽입/삭제 + 인덱스 접근

 

이 “기능 제한” 덕분에
코드 자체가 문제의 흐름을 그대로 표현하게 된다.

---

2️⃣ LIFO / FIFO는 “저장 방식”이 아니라 “사고 방식”이다

Stack과 Queue의 진짜 차이는

어디에 저장하느냐가 아니라 어떻게 처리하느냐다.

🔹 Stack (LIFO) — “되돌리기(Undo)”

Stack의 철학:

가장 최근의 상태를 가장 먼저 되돌린다

 

그래서 Stack은 이런 문제에서 등장한다:

유형	이유
괄호 검사	마지막에 열린 괄호부터 닫힙
문자열 뒤집기	push → pop 만으로 역순
브라우저 뒤로가기	가장 최근 페이지부터
Ctrl+Z	가장 최근 편집부터 취소

 

즉, 문제에 이런 말이 나오면:

“이전으로 돌아간다”

“가장 최근의 상태”

“현재 값이 이전 값들을 무효화한다”

→ Stack

---

🔹 Queue (FIFO) — “공정한 대기열”

Queue의 철학:

먼저 들어온 것을 먼저 처리한다

 

그래서 Queue는:

상황 의미

상황	의미
BFS	가까운 노드부터 탐색
최단 거리	먼저 도착한 경로가 더 짧음
시뮬레이션	먼저 요청된 작업 먼저

 

문제에 이런 표현이 나오면:

“순서대로”

“먼저 들어온 것부터”

“가장 빠른 시간”

→ Queue

---

3️⃣ 실전 디버깅 포인트

Stack과 Queue를 쓰는 코테에서

가장 흔한 탈락 원인은 이것이다:

비어있는 컨테이너 접근

s.top();
q.front();

이건 비어있으면 즉시 프로그램 종료다.

그래서 반드시:

while (!s.empty() && s.top() != target) {
    s.pop();
}

이렇게 써야 한다.

또 이런 실수도 매우 흔하다:

s.pop();
process(s.top());   // ❌ s가 비었을 수도 있음

---

4️⃣  모노톤 스택 (Monotonic Stack)

Stack의 코테 진짜 활용은

“되돌리기”를 이용한 최적화다.

대표 문제:

“나보다 큰 값이 처음 등장하는 위치”

예: 오큰수, 주식 가격, 히스토그램

while (!st.empty() && st.top() < x)
    st.pop();
st.push(x);

의미:

현재 값이 이전 값들을 무효화 → Undo

각 원소는:

• 1번 push
• 1번 pop

→ 전체가 O(N)

이게 브루트포스 O(N²)을 O(N)으로 바꾸는 핵심이다.

---

5️⃣ Queue — BFS

BFS는 사실 Queue가 없으면 불가능하다.

queue.push(start);

while (!queue.empty()) {
    cur = queue.front(); queue.pop();
    for (next : neighbors)
        queue.push(next);
}

Queue를 쓰는 이유:

먼저 도착한 경로가 항상 더 짧기 때문

그래서:

• 미로
• 최단 거리
• 퍼져나감(전염, 확산)

→ 전부 Queue

---

6️⃣ Deque — Stack과 Queue를 모두 대체하는 만능 구조

deque는:

• 앞 삽입 O(1)
• 뒤 삽입 O(1)
• 인덱스 접근 가능

그래서:

• 슬라이딩 윈도우
• 구간 최대/최소

같은 문제는 deque 없이는 풀기 힘들다.

---

7️⃣Stack / Queue를 vector로 흉내내지 마라

vector.erase(v.begin()) → O(N)

queue.pop() → O(1)

시뮬레이션, BFS에서 vector 쓰면 시간 초과 난다.

---

8️⃣코테에서 가장 많이 쓰는 함수 요약

Stack

st.push(x)	삽입
st.pop()	제거
st.top()	맨 위 값
st.empty()	비었는지
st.size()	개수

Queue

q.push(x)	뒤에 삽입
q.pop()	앞 제거
q.front()	앞 값
q.back()	뒤 값
q.empty()	비었는지
q.size()	크기

 

Deque

push_front, push_back	양쪽 삽입
pop_front, pop_back	양쪽 제거
front(), back()	앞/뒤 값

---

최종 요약

되돌리기, 짝 맞추기, 이전 상태	Stack
순서대로 처리, 최단 거리	Queue
양쪽 처리, 구간	Deque
이전 값들이 현재 값에 의해 무효화	Monotonic Stack
퍼져나감, 탐색	BFS + Queue