덱 (Deque, Double-Ended Queue)

양쪽 끝이 전부 뚫려 있는 줄. 앞에서도, 뒤에서도 넣고 뺄 수 있다 — 게다가 둘 다 O(1). 스택처럼 한쪽만 쓰면 스택이 되고, 큐처럼 한쪽엔 넣고 반대쪽에서 빼면 큐가 된다.

1. 스택도 되고 큐도 되는 만능 줄

스택은 한쪽 끝(top)만 쓴다. 큐는 한쪽으로 넣고(rear) 반대쪽으로 뺀다(front). 덱은 앞(front)과 뒤(back) 모두에서 삽입·삭제가 가능한 자료구조다 — 이름 그대로 "Double-Ended Queue".

addFront / removeFront 만 쓰면 → 스택처럼 동작
addBack 으로 넣고 removeFront 로 빼면 → 큐처럼 동작
양쪽을 다 쓰면 → 스택·큐로는 못 하는 새로운 패턴(슬라이딩 윈도우 최댓값 등)이 가능

핵심 — "어느 쪽에서 넣고 뺄지"를 자료구조가 강제하지 않는다. 대신 사용하는 쪽이 규칙을 정한다. 그만큼 표현력이 크지만, 아무 데서나 넣고 빼면 오히려 로직이 헷갈리기 쉽다.

2. 직접 넣고 빼 보기

버튼 4개로 앞뒤에서 데이터를 넣고 빼보자. 어느 연산이든 맨 앞 또는 맨 뒤만 건드리므로 데이터 개수와 상관없이 항상 O(1)이다.

‹

›

FRONT (앞) — 비어 있음 size: 0 BACK (뒤) — 비어 있음

3. 구현 방식 두 가지

덱을 실제로 만드는 방법은 크게 두 갈래다.

방식	장점	단점
이중 연결 리스트 (doubly linked list)	앞/뒤 포인터만 있으면 끝. 노드를 새로 만들어 이어붙이기만 하면 되므로 삽입·삭제가 진짜 O(1), 크기 제한 없음	노드마다 prev/next 포인터를 따로 저장 → 메모리 오버헤드, 포인터를 따라가야 해서 캐시 지역성이 나쁨
원형 버퍼 기반 (동적 배열 + head/tail)	데이터가 메모리에 연속으로 붙어 있어 캐시 지역성이 좋음, 포인터 오버헤드 없음	배열이 가득 차면 더 큰 배열로 재할당하고 전부 복사해야 함(가끔 O(n), 평균은 상쇄되어 O(1))

원형 버퍼로 구현하면? — head/tail 두 인덱스를 양방향으로 움직이면 된다. addFront는 head = (head - 1 + cap) % cap, addBack은 tail = (tail + 1) % cap 처럼, 앞으로도 뒤로도 % 용량 연산 하나로 감아 돌린다. 실제로 Python의 collections.deque는 이중 연결 리스트와 비슷하되, 노드 하나에 여러 원소를 담는 블록 단위 연결 구조로 두 방식의 장점을 절충한다.

4. 실전 활용 — 슬라이딩 윈도우 최댓값 (모노토닉 덱)

배열에서 크기 k인 윈도우가 오른쪽으로 한 칸씩 이동할 때, 매번 윈도우 안의 최댓값을 구하는 문제 (슬라이딩 윈도우 참고). 매번 윈도우 안을 다 훑으면 O(nk)인데, 덱을 쓰면 전체 O(n)에 풀 수 있다.

핵심 아이디어: 덱에는 값이 아니라 인덱스를 저장하고, 항상 "덱 안의 값이 앞에서 뒤로 감소하는 순서"를 유지한다.

새 원소를 넣기 전, 덱 뒤쪽에서 새 값보다 작은 값들을 전부 pop한다 (그들은 앞으로 절대 최댓값이 될 수 없으므로 버려도 무방) → removeBack
남은 덱 뒤에 새 인덱스를 addBack
덱의 맨 앞(front)이 항상 현재 윈도우의 최댓값 인덱스다
맨 앞 인덱스가 윈도우 범위를 벗어나면 removeFront로 버린다

버튼을 눌러 한 칸씩 진행해보자. 보라색 칩이 현재 덱(왼쪽=front=현재 최댓값), 주황 테두리 칸이 현재 윈도우다.

덱 (인덱스, front → back / 감소하는 순서 유지):

시작 전. "한 칸 이동"을 눌러보세요.

지금까지의 윈도우별 최댓값:

5. Python `collections.deque`

파이썬은 표준 라이브러리 collections.deque로 양방향 O(1) 연산을 그대로 제공한다. 리스트의 insert(0, x)/pop(0)은 앞쪽 원소를 전부 밀어야 해서 O(n)이지만, deque는 애초에 이 용도로 설계됐다.

from collections import deque

dq = deque([2, 3, 4])

dq.append(5)        # 뒤에 추가 → [2, 3, 4, 5]      addBack
dq.appendleft(1)    # 앞에 추가 → [1, 2, 3, 4, 5]   addFront

dq.pop()             # 뒤에서 제거 → 5 반환         removeBack
dq.popleft()         # 앞에서 제거 → 1 반환         removeFront

# 슬라이딩 윈도우 최댓값 (모노토닉 덱)
def sliding_max(nums, k):
    dq, result = deque(), []   # dq에는 인덱스 저장
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] < x:
            dq.pop()                     # removeBack: 작은 값 버림
        dq.append(i)                     # addBack
        if dq[0] <= i - k:
            dq.popleft()                 # removeFront: 창 밖이면 버림
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

maxlen 옵션을 주면 deque(maxlen=N) 은 가득 찼을 때 반대쪽 원소를 자동으로 밀어내는 원형 버퍼처럼 동작한다.

한 줄 요약 — 덱은 앞·뒤 양쪽에서 O(1) 삽입·삭제가 되는 자료구조로, 이중 연결 리스트나 원형 버퍼로 구현하며, 한쪽만 쓰면 스택, 반대쪽에 넣고 빼면 큐가 되고, 양쪽을 함께 쓰면 슬라이딩 윈도우 최댓값 같은 문제를 O(n)에 풀 수 있다.