덱 (Deque)

JayJi·2026년 4월 10일

목록 보기

6/30

문제	난이도	핵심
10866번 — 덱	실버 IV	덱 기본 구현
1021번 — 회전하는 큐	실버 III	덱 시뮬레이션
5430번 — AC	골드 V	방향 전환 최적화
11003번 — 최솟값 찾기	플래티넘 V	슬라이딩 윈도우 최솟값
2346번 — 풍선 터뜨리기	실버 III	덱 시뮬레이션

1. 개념

덱(Deque, Double-Ended Queue)은 앞(front)과 뒤(rear) 양쪽 모두에서 삽입과 삭제가 가능한 자료구조다.

스택과 큐를 합친 형태다.

         앞(front)          뒤(rear)
offerFirst →  [ 1 | 2 | 3 ]  ← offerLast
 pollFirst ←  [ 1 | 2 | 3 ]  → pollLast

스택처럼도, 큐처럼도 쓸 수 있어 유연하다.

2. 동작 과정

5430번 AC 예시: 배열 [1, 2, 3, 4, 5]에 명령 "RRD" 적용

단계	명령	동작	덱 상태	방향
초기	—	—	`[1, 2, 3, 4, 5]`	정방향
1	R	방향 전환	`[1, 2, 3, 4, 5]`	역방향
2	R	방향 전환	`[1, 2, 3, 4, 5]`	정방향
3	D	정방향이므로 앞 삭제	`[2, 3, 4, 5]`	정방향

결과: [2, 3, 4, 5]

실제로 배열을 뒤집지 않고, 방향 플래그만 바꿔서 앞/뒤 중 어디서 꺼낼지 결정하는 것이 핵심이다.

3. 스택 / 큐 / 덱 비교

	스택	큐	덱
삽입 위치	뒤(top)	뒤	앞 / 뒤 모두
삭제 위치	뒤(top)	앞	앞 / 뒤 모두
순서	LIFO	FIFO	자유
Java 구현체	`ArrayDeque`	`ArrayDeque`	`ArrayDeque`

셋 모두 Java에서 ArrayDeque 하나로 구현할 수 있다.

4. 핵심 포인트 2가지

슬라이딩 윈도우 최솟값에 덱을 쓴다

크기 L인 윈도우를 이동하면서 최솟값을 구할 때, 덱으로 O(N)에 해결할 수 있다.
덱에 인덱스를 저장하고, 새 원소보다 크거나 같은 값을 뒤에서 제거하며 단조 증가를 유지한다.
윈도우를 벗어난 인덱스는 앞에서 제거한다.

단조 덱 = 앞에서 범위 벗어난 원소 제거 + 뒤에서 조건 안 맞는 원소 제거

방향 전환이 필요한 문제는 reverse 대신 플래그를 써라

배열을 실제로 뒤집으면 O(N)이 매번 발생한다.
덱과 방향 플래그를 조합하면 방향 전환을 O(1)에 처리할 수 있다.

5. 코드

기본 연산

Deque<Integer> deque = new ArrayDeque<>();

// 삽입
deque.offerFirst(1);   // 앞에 추가
deque.offerLast(2);    // 뒤에 추가

// 확인 (꺼내지 않음)
int front = deque.peekFirst();   // 앞 값 확인
int back  = deque.peekLast();    // 뒤 값 확인

// 삭제
int f = deque.pollFirst();   // 앞에서 꺼내기
int b = deque.pollLast();    // 뒤에서 꺼내기

boolean empty = deque.isEmpty();
int size = deque.size();

슬라이딩 윈도우 최솟값 패턴

// 크기 L인 윈도우에서 각 구간의 최솟값 구하기
static void slidingWindowMin(int[] arr, int L) {
    int N = arr.length;
    Deque<Integer> deque = new ArrayDeque<>();  // 인덱스 저장

    for (int i = 0; i < N; i++) {
        // 윈도우 범위를 벗어난 인덱스 앞에서 제거
        while (!deque.isEmpty() && deque.peekFirst() <= i - L) {
            deque.pollFirst();
        }

        // 현재 값보다 크거나 같은 값 뒤에서 제거 (단조 증가 유지)
        while (!deque.isEmpty() && arr[deque.peekLast()] >= arr[i]) {
            deque.pollLast();
        }

        deque.offerLast(i);

        // 윈도우가 L 이상 됐을 때부터 최솟값 출력
        if (i >= L - 1) {
            System.out.println(arr[deque.peekFirst()]);
        }
    }
}

방향 플래그 패턴

Deque<Integer> deque = new ArrayDeque<>();
boolean reversed = false;  // false: 정방향, true: 역방향

// 방향 전환 — O(1)
void rotate() {
    reversed = !reversed;
}

// 앞 원소 삭제 — 방향에 따라 앞/뒤 결정
int removeFirst() {
    return reversed ? deque.pollLast() : deque.pollFirst();
}

6. 시간복잡도

연산	시간복잡도
offerFirst / offerLast	O(1)
pollFirst / pollLast	O(1)
peekFirst / peekLast	O(1)
슬라이딩 윈도우 최솟값 (전체)	O(N)

슬라이딩 윈도우에서 각 원소는 최대 한 번 추가되고 한 번 제거되므로 전체 O(N)이다.

7. 주의사항

poll/peek 전에 isEmpty() 확인을 습관화하라. 빈 덱에서 호출하면 null을 반환하고, int로 받으면 NullPointerException이 발생한다.
메서드 이름 혼동 주의. push/pop은 스택 방식(앞 기준), offer/poll은 큐 방식(뒤 기준)이다. 하나의 덱에서 두 방식을 섞어 쓰면 의도치 않은 방향에서 원소가 나온다.
슬라이딩 윈도우 덱에는 값이 아닌 인덱스를 저장한다. 범위 체크(i - L)를 위해 위치 정보가 반드시 필요하다.
ArrayDeque는 null을 저장할 수 없다. null을 넣으면 NullPointerException이 발생하므로 sentinel 값이 필요하다면 다른 방법을 써야 한다.