덱 (Deque)

정의

Deque (덱, double-ended queue) 는 양쪽 끝에서 O(1) push/pop 이 가능한 선형 자료구조. 큐 + 스택의 일반화.

내부 구현은 대개 chunked array (C++ STL std::deque) 또는 doubly-linked list. 랜덤 접근은 O(1) (STL 기준), 중간 삽입/삭제는 O(N).

문제 상황과 동기

큐는 front 에서만 pop, rear 에서만 push. 스택은 한쪽 끝만 push/pop. 양쪽 모두 가능하면?

• naive: vector 를 쓰되, 맨 앞 삽입은 O(N) shift. 실시간 불가.
• deque: push_front, push_back, pop_front, pop_back 모두 O(1). 슬라이딩 윈도우 최대/최소 같은 응용 가능.

핵심 통찰: monotonic deque (단조 덱) 로 윈도우 내 min/max 를 O(1) 로 유지. 각 원소가 덱에 한 번만 들어감 → amortized O(N).

시각화

핵심 아이디어

Deque 를 양방향 확장 가능한 배열 또는 리스트로 구현:

1. chunked array (STL std::deque 방식): 고정 크기 블록 여러 개를 관리. 각 블록은 배열. 블록 간 포인터로 연결.
2. doubly-linked list: 노드 양 끝에 prev, next. head/tail 포인터로 O(1) 접근.

Monotonic Deque 활용 (슬라이딩 윈도우 최대값 예):

• 윈도우를 오른쪽으로 밀면서, 덱에 인덱스 (또는 값) 를 내림차순으로 유지.
• 윈도우 밖으로 나간 인덱스는 front 에서 pop.
• 새 원소가 덱 back 의 원소보다 크면, back 을 pop (더 이상 최댓값 후보가 아니므로).
• 덱의 front 가 항상 현재 윈도우의 최댓값 인덱스.

invariant: 덱에는 윈도우 내 원소 중 “미래에 최댓값이 될 가능성이 있는 후보”만 남는다. 각 원소는 덱에 최대 1 번 push, 1 번 pop → 전체 O(N).

알고리즘

기본 연산

push_front(x):
    head 에 노드/블록 추가. O(1).

push_back(x):
    tail 에 노드/블록 추가. O(1).

pop_front():
    head 노드/블록 제거. O(1).

pop_back():
    tail 노드/블록 제거. O(1).

at(i):
    chunked array 방식이면 O(1). linked list 는 O(N).

Monotonic Deque (슬라이딩 윈도우 최대)

sliding_window_max(a, k):
    dq = empty deque (인덱스 저장)
    ans = []
    for i = 0..N-1:
        // 윈도우 밖 제거
        while !dq.empty() and dq.front() < i - k + 1:
            dq.pop_front()
        // 새 원소보다 작은 후보 제거 (back 에서)
        while !dq.empty() and a[dq.back()] <= a[i]:
            dq.pop_back()
        dq.push_back(i)
        if i >= k - 1:
            ans.append(a[dq.front()])
    return ans

구현

// C++ std::deque 로 슬라이딩 윈도우 최댓값 O(N)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k; cin >> n >> k;
  vector<int> a(n);
  for (auto& v : a) cin >> v;
  deque<int> dq; // 인덱스 저장
  vector<int> ans;
  for (int i = 0; i < n; i++) {
      // 윈도우 밖 제거
      while (!dq.empty() && dq.front() < i - k + 1)
          dq.pop_front();
      // 새 원소보다 작은 후보 제거
      while (!dq.empty() && a[dq.back()] <= a[i])
          dq.pop_back();
      dq.push_back(i);
      if (i >= k - 1)
          ans.push_back(a[dq.front()]);
  }
  for (int v : ans) cout << v << " ";
}

# collections.deque 로 monotonic deque
from collections import deque
import sys
input = sys.stdin.readline
​
n, k = map(int, input().split())
a = list(map(int, input().split()))
dq = deque()
ans = []
for i in range(n):
  # 윈도우 밖 제거
  while dq and dq[0] < i - k + 1:
      dq.popleft()
  # 새 원소보다 작은 후보 제거
  while dq and a[dq[-1]] <= a[i]:
      dq.pop()
  dq.append(i)
  if i >= k - 1:
      ans.append(a[dq[0]])
print(" ".join(map(str, ans)))

// Java ArrayDeque 로 monotonic deque
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int k = Integer.parseInt(st.nextToken());
      int[] a = new int[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++)
          a[i] = Integer.parseInt(st.nextToken());
      Deque<Integer> dq = new ArrayDeque<>();
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < n; i++) {
          while (!dq.isEmpty() && dq.peekFirst() < i - k + 1)
              dq.pollFirst();
          while (!dq.isEmpty() && a[dq.peekLast()] <= a[i])
              dq.pollLast();
          dq.offerLast(i);
          if (i >= k - 1)
              sb.append(a[dq.peekFirst()]).append(" ");
      }
      System.out.println(sb);
  }
}

7 3
1 3 -1 -3 5 3 6

3 3 5 5 6

복잡도

변형 / 활용

함정

1. 인덱스 vs 값

monotonic deque 에서 인덱스를 저장해야 윈도우 밖 제거가 가능. 값만 저장하면 “어느 게 윈도우 밖인지” 모른다.

2. <= vs < (중복 처리)

슬라이딩 윈도우 최댓값에서 같은 값 여러 개가 있을 때, 뒤쪽 인덱스를 덱에 남겨야 윈도우가 밀려도 안전. 그래서 a[dq.back()] <= a[i] 로 pop.

최솟값은 a[dq.back()] >= a[i] 로 반대.

3. STL deque 는 랜덤 접근 O(1) 이지만, vector 보다 느림

cache locality 가 나쁘다. 잦은 랜덤 접근 + 크기 변동 없으면 vector 가 낫다. deque 는 양쪽 끝 연산이 많을 때만.

4. Java Deque 는 인터페이스

구현체는 ArrayDeque (순환 배열) 또는 LinkedList (양방향 리스트). 보통 ArrayDeque 가 빠름.

BOJ 연습 문제

참고

• 큐
• 스택
• 0-1 BFS
• 슬라이딩 윈도우