큐와 덱

큐와 덱이란?

큐(queue) 는 먼저 넣은 것이 먼저 나오는 자료구조입니다. 이 규칙을
FIFO(First In First Out)라고 합니다. 줄 서기를 떠올리면 정확합니다 — 먼저 온
사람이 먼저 처리됩니다. 스택의 LIFO와 정반대입니다.

덱(deque, double-ended queue) 은 양쪽 끝 모두에서 넣고 뺄 수 있는 큐입니다.
큐와 스택을 모두 포함하는 더 일반적인 구조입니다.

1. 기본 연산

큐의 연산:

• push(enqueue) — 뒤에 넣는다.
• pop(dequeue) — 앞에서 뺀다.
• front — 맨 앞을 본다.

덱은 여기에 앞에도 넣고 뒤에서도 빼는 연산이 추가됩니다. 모든 연산이 \(O(1)\).

2. 큐가 푸는 문제: 순서대로 처리

큐의 핵심 용도는 들어온 순서대로 공정하게 처리하는 것입니다.

• BFS(너비 우선 탐색): 가까운 정점부터 차례로 방문 — 큐가 핵심 부품.
• 시뮬레이션: 요청을 들어온 순서대로 처리, 작업 대기열.
• 회전 시뮬레이션: 앞에서 빼서 뒤에 넣으면 줄을 한 칸 돌리는 효과.

특히 BFS에서 큐가 왜 필요한지가 중요합니다. "거리 1인 정점들을 다 보고 나서야
거리 2인 정점을 본다"는 순서를 큐의 FIFO가 자동으로 보장하기 때문입니다.

3. 덱이 푸는 문제: 양쪽이 필요할 때

덱은 양쪽에서 조작이 필요한 상황에서 씁니다.

• 0-1 BFS: 가중치가 0이면 앞에, 1이면 뒤에 넣어 다익스트라 없이 최단 경로.
• 슬라이딩 윈도우 최댓값: 창이 움직일 때 양 끝에서 후보를 넣고 빼는
  모노톤 덱.
• 회문·양방향 탐색: 앞뒤를 동시에 다뤄야 할 때.

4. 원형 큐: 메모리를 아끼는 구현

배열로 큐를 만들 때 앞에서 계속 빼면 앞쪽 공간이 버려집니다. 원형 큐(circular
queue) 는 인덱스가 끝에 닿으면 처음으로 돌아가게 해 공간을 재활용합니다.

[ _ _ C D E ]   front=2, rear=0 (E 다음은 0번 칸)

(인덱스 + 1) % 크기로 회전시키는 것이 핵심입니다. 라이브러리를 쓰면 신경 쓸
필요 없지만, 원리를 알면 메모리 제한이 빡빡할 때 유용합니다.

5. 복잡도

큐와 덱의 모든 기본 연산은 \(O(1)\)입니다. \(N\)개의 원소를 한 번씩 넣고 빼는
BFS는 \(O(N + E)\)(정점 + 간선)이 됩니다. "들어온 순서대로", "가까운 것부터"가
보이면 큐를 떠올리세요.

정리

큐는 FIFO, 덱은 양쪽 끝 자유. 큐는 BFS와 순서 처리의 부품이고, 덱은 슬라이딩
윈도우와 0-1 BFS처럼 양쪽 조작이 필요할 때 쓰입니다.

큐와 덱을 코드로

라이브러리 사용법과 직접 구현, 그리고 대표 응용인 모노톤 덱을 다룹니다.

1. 라이브러리 큐

#include <queue>
queue<int> q;
q.push(5);                 // 뒤에 넣기
if (!q.empty()) {
    int x = q.front();     // 맨 앞 보기
    q.pop();               // 맨 앞 빼기 (값 반환 안 함)
}
cout << q.size();

from collections import deque
q = deque()
q.append(5)                # 뒤에 넣기
if q:
    x = q.popleft()        # 앞에서 빼기 — O(1)

파이썬에서 리스트의 pop(0)는 \(O(N)\) 이라 큐로 쓰면 느립니다. 반드시
collections.deque를 쓰세요. 이것이 가장 흔한 성능 실수입니다.

2. 라이브러리 덱

#include <deque>
deque<int> dq;
dq.push_back(1);  dq.push_front(2);   // 양쪽에 넣기
dq.pop_back();    dq.pop_front();     // 양쪽에서 빼기
int f = dq.front(), b = dq.back();

dq = deque()
dq.append(1);    dq.appendleft(2)     # 뒤 / 앞에 넣기
dq.pop();        dq.popleft()         # 뒤 / 앞에서 빼기

3. 배열로 직접 구현한 큐

int q[1000000], head = 0, tail = 0;   // [head, tail) 이 큐
void push(int x) { q[tail++] = x; }
int pop() { return q[head++]; }
bool empty() { return head == tail; }

BFS에서 이렇게 배열 큐를 쓰면 라이브러리보다 빠르고 디버깅도 편합니다. 인덱스
크기만 충분히 잡아 주면 됩니다.

4. 모노톤 덱: 슬라이딩 윈도우 최댓값

길이 \(K\)인 창이 한 칸씩 움직일 때 각 창의 최댓값을 \(O(N)\)에 구합니다. 덱에는
인덱스를 값이 내림차순이 되도록 유지합니다.

deque<int> dq;                          // 값이 내림차순인 인덱스들
for (int i = 0; i < n; i++) {
    // 뒤에서: 새 값보다 작은 후보는 영원히 쓸모없다 → 제거
    while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
    dq.push_back(i);
    // 앞에서: 창을 벗어난 인덱스 제거
    if (dq.front() <= i - k) dq.pop_front();
    if (i >= k - 1) cout << a[dq.front()] << ' ';   // 창의 최댓값
}

dq = deque()
res = []
for i in range(n):
    while dq and a[dq[-1]] <= a[i]:
        dq.pop()
    dq.append(i)
    if dq[0] <= i - k:
        dq.popleft()
    if i >= k - 1:
        res.append(a[dq[0]])

각 인덱스가 한 번 들어가고 한 번 나오므로 전체 \(O(N)\). 맨 앞이 항상 현재 창의
최댓값입니다.

5. 흔한 실수

• 파이썬 리스트로 큐 — pop(0)는 \(O(N)\). deque.popleft()를 쓰자.
• 빈 큐 접근 — front/pop 전에 empty() 확인.
• 모노톤 덱의 창 범위 — 앞에서 제거할 때 인덱스가 i - k 이하인지 정확히
  비교하세요. 한 칸 어긋나면 답이 틀립니다.
• C++ queue::pop() — 값 반환 안 함. front()로 먼저 읽기.

6. 패턴 알아보기

• "최단 거리(가중치 없음)" → BFS → 큐.
• "고정 길이 창의 최대/최소" → 모노톤 덱.
• "가중치가 0과 1뿐인 최단 경로" → 0-1 BFS → 덱.
• "양쪽에서 처리" → 덱.

실전에서 큐·덱 문제 알아보기

큐와 덱은 BFS의 부품으로 익숙하지만, Silver에서는 시뮬레이션과 모노톤 덱
문제로 단독 출제됩니다. 어떤 모양의 문제인지 정리합니다.

1. 출제 신호

• "먼저 온 것을 먼저 처리" — 줄 서기, 작업 대기열, 프린터 큐. 서술 자체가
  FIFO면 큐입니다.
• 카드를 위에서 뽑아 아래로 넣는다 — 요세푸스, 카드2 류의 회전
  시뮬레이션. 덱의 rotate 패턴입니다.
• 양쪽 끝에서 넣거나 뺀다 — 풍선 터뜨리기, 좌우 이동. 덱이 직접 신호입니다.
• "길이 \(K\) 구간의 최솟값을 모든 위치에서" — 모노톤 덱(슬라이딩 윈도우
  최솟값)의 대표 신호입니다.
• 명령 문자열(push_front, pop_back …)을 그대로 수행하는 구현 문제.

2. 풀이 결정 절차

1. 어느 끝에서 넣고 어느 끝에서 빼는가? — 한쪽 삽입·반대쪽 삭제면 큐,
   양쪽 다면 덱.
2. 회전인가 삭제인가? — "맨 앞을 맨 뒤로"는 pop 후 push.
3. 구간 최솟값 유지가 필요한가? — 모노톤 덱: 뒤에서 자기보다 못한 원소를
   제거하며 push, 앞에서 창을 벗어난 원소를 제거.
4. 연산 횟수를 셉니다 — 각 원소가 들어가고 나가는 횟수는 각 1번이므로
   전체 \(O(N)\)임을 확인합니다.

3. 자주 하는 실수

• 파이썬 list.pop(0). 리스트 앞 삭제는 \(O(N)\)이라 \(10^5\)번 반복하면
  시간 초과입니다. 반드시 collections.deque를 쓰세요.

from collections import deque
q = deque(range(1, n + 1))
while len(q) > 1:
    q.popleft()              # O(1) — list.pop(0)은 O(N)
    q.append(q.popleft())

• 모노톤 덱에서 창 밖 원소를 값으로 제거. 같은 값이 여러 개면 엉뚱한 것을
  지웁니다. 덱에는 인덱스를 넣고 dq[0] <= i - k로 만료를 판단하세요.
• 앞뒤 혼동. deque의 appendleft/popleft와 append/pop 짝을 바꿔 쓰면
  답이 거꾸로 됩니다. 문제의 "앞"이 코드의 어느 쪽인지 주석으로 고정하세요.
• 빈 덱 접근. 양 끝 삭제 명령이 섞인 구현 문제는 빈 상태 검사(-1 출력 등)가
  채점 포인트입니다.
• 회전을 한 칸씩 시뮬레이션. \(K\)칸 회전을 \(K\)번 반복하지 말고, 가능하면
  인덱스 계산이나 rotate로 한 번에 처리해 복잡도를 줄이세요.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 것부터 어려운 것 순으로 놓여
있습니다. 명령 수행형 구현 → 회전 시뮬레이션 → 모노톤 덱 순서로 단계를
밟도록 되어 있으니 차례대로 푸세요.

풀기 전에 "각 원소가 덱에 몇 번 들어가고 몇 번 나가는가"를 따져 전체
복잡도를 먼저 계산하는 습관을 들이세요. 3문제 이상 해결해 클리어하면
레이팅의 CLASS 보너스에 반영됩니다.