[CS300 #045] 덱 — 양쪽 끝을 모두 O(1) 로 다루는 큐

컴퓨터공학 300 주제 시리즈의 045번째 글이다. 전체 지도는 여기.

한 줄 요약

덱(deque, double-ended queue)은 앞과 뒤 양쪽에서 넣고 빼는 것을 모두 O(1) 로 허용하는 구조로, 스택과 큐를 한 몸에 담은 일반형이다.

왜 필요한가

스택은 한쪽 끝, 큐는 넣는 끝과 빼는 끝이 정해져 있다. 그런데 실제 문제는 그 경계가 흐린 경우가 많다. 작업 스케줄러는 평소엔 큐처럼 뒤에 쌓다가 급한 일은 앞에 끼워 넣고 싶다. 슬라이딩 윈도 알고리즘은 창 밖으로 나간 원소를 앞에서 버리고, 쓸모없어진 원소를 뒤에서 버린다. 0-1 BFS 는 비용 0 짜리 간선은 앞에, 비용 1 짜리는 뒤에 넣는다. 일 훔치기(work stealing) 스케줄러는 자기 일은 한쪽 끝에서, 남의 일은 반대쪽 끝에서 가져간다.

이 모든 경우에 필요한 것은 “양쪽 끝이 다 싸다”는 성질 하나다. 동적 배열은 뒤쪽만 싸고, 단일 연결 리스트는 앞쪽만 싸다. 덱은 둘 다 싸다.

핵심 개념

연산

연산	파이썬 `deque`	자바 `ArrayDeque`	비용
뒤에 넣기	`append`	`addLast` / `offerLast`	O(1)
앞에 넣기	`appendleft`	`addFirst` / `offerFirst`	O(1)
뒤에서 빼기	`pop`	`pollLast`	O(1)
앞에서 빼기	`popleft`	`pollFirst`	O(1)
양 끝 보기	`d[-1]`, `d[0]`	`peekLast`, `peekFirst`	O(1)
가운데 인덱스 접근	`d[i]`	(지원 안 함)	구현에 따라 다름

덱을 스택으로 쓰려면 한쪽 끝만, 큐로 쓰려면 반대쪽 끝 두 개를 쓰면 된다. 그래서 현대 표준 라이브러리는 스택과 큐를 따로 두기보다 덱 하나를 권한다. 자바 ArrayDeque 문서는 이 클래스가 스택으로 쓸 때 Stack 보다, 큐로 쓸 때 LinkedList 보다 빠를 가능성이 높다고 적는다(Java SE 21 ArrayDeque).

구현 방법 1: 크기가 늘어나는 원형 버퍼

앞 글의 원형 큐에 “앞에 넣기”를 더하면 덱이 된다. head 를 하나 줄이면(나머지 연산으로 감아서) 앞에 넣을 칸이 생긴다. 꽉 차면 동적 배열처럼 2배 배열로 이사한다. 이사할 때는 원형으로 감긴 내용을 논리 순서대로 펴서 새 배열의 앞부터 채운다.

cap=8, head=6, size=4   논리 순서: A B C D

  idx:  0   1   2   3   4   5   6   7
      [ C ][ D ][   ][   ][   ][   ][ A ][ B ]
                                    ▲ head

appendleft(Z): head = (6 - 1) % 8 = 5
      [ C ][ D ][   ][   ][   ][ Z ][ A ][ B ]

러스트 VecDeque 는 문서 첫 줄부터 “크기가 늘어나는 링 버퍼로 구현된 양방향 큐”라고 정의한다(Rust VecDeque). 자바 ArrayDeque 도 “크기 조절 배열 구현”이며 용량 제한 없이 필요에 따라 커진다고 적는다. 이 방식의 장점은 메모리가 연속이라 캐시에 유리하다는 것이다. 단점은 이사할 때 순간적으로 O(n) 이 든다는 것(분할 상환하면 O(1))과, 이사 뒤에는 원소의 주소가 바뀐다는 것이다.

구현 방법 2: 고정 크기 블록들의 목록

C++ std::deque 와 CPython 의 collections.deque 는 다른 길을 택했다. 고정 크기 블록(작은 배열)을 여러 개 두고, 블록들을 잇는다. 앞쪽이 차면 앞에 블록을 하나 더 붙이고, 뒤쪽이 차면 뒤에 붙인다. 기존 원소는 옮기지 않는다.

 블록 목록 (맵)
 ┌────┬────┬────┐
 │ ●  │ ●  │ ●  │
 └─┼──┴─┼──┴─┼──┘
   ▼    ▼    ▼
 [..AB][CDEF][GH..]

cppreference 는 std::deque 에 대해 양 끝 삽입·삭제가 나머지 원소의 포인터나 참조를 무효화하지 않으며, vector 와 달리 원소가 연속으로 저장되지 않고 보통 따로 할당된 고정 크기 배열들의 연속으로 구현되어 인덱스 접근에 포인터 역참조가 두 번 든다고 설명한다(cppreference — std::deque).

인덱스 접근은 공짜가 아니다

파이썬 문서는 deque 가 양쪽 끝에서 대략 같은 O(1) 성능으로 넣고 뺄 수 있다고 하면서도, “인덱스 접근은 양 끝에서는 O(1) 이지만 가운데로 갈수록 O(n) 으로 느려진다. 빠른 임의 접근이 필요하면 리스트를 쓰라”고 명시한다(Python collections.deque). 블록 연결 구조라서 가운데 블록까지 따라가야 하기 때문이다. 덱은 “양 끝 전용”으로 쓰고, 가운데를 자주 본다면 다른 구조를 고르는 게 맞다.

길이 제한 덱

파이썬 deque(maxlen=n) 은 꽉 찬 상태에서 한쪽에 넣으면 반대쪽 끝 원소가 자동으로 버려진다. “최근 n 개만 보관”이 한 줄로 끝난다. tail -n 같은 동작이나 이동 평균 계산에 편하다.

직접 해 보기

덱의 대표 응용인 슬라이딩 윈도 최댓값을 푼다. 길이 n 배열에서 크기 k 창을 한 칸씩 밀며 각 창의 최댓값을 구한다. 매번 max 를 부르면 O(nk) 지만, 덱을 쓰면 O(n) 이다.

아이디어는 이렇다. 덱에는 “아직 최댓값이 될 가능성이 있는” 인덱스만, 값이 감소하는 순서로 둔다.

새 원소 x 가 오면, 덱 뒤에서 x 보다 작거나 같은 것을 모두 버린다. 그것들은 x 보다 먼저 창을 떠나면서 x 보다 작으니 앞으로 최댓값이 될 일이 없다.
덱 앞의 인덱스가 창 밖으로 나갔으면 버린다.
그러면 덱 앞이 항상 현재 창의 최댓값이다.

from collections import deque

def sliding_max(nums, k):
    dq = deque()            # 인덱스를 담는다. 값은 앞→뒤로 감소
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:   # 뒤에서: 나보다 작은 건 영영 최대가 못 된다
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:                # 앞에서: 창 밖으로 나간 인덱스 제거
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

nums = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_max(nums, 3))

# 검증: 단순 O(nk) 방식과 비교
import random
for _ in range(1000):
    a = [random.randint(-50, 50) for _ in range(random.randint(1, 40))]
    k = random.randint(1, len(a))
    assert sliding_max(a, k) == [max(a[i:i+k]) for i in range(len(a)-k+1)]
print("무작위 1000회 검증 통과")

last3 = deque(maxlen=3)
for line in ["a", "b", "c", "d", "e"]:
    last3.append(line)
print(list(last3))

[3, 3, 5, 5, 6, 7]
무작위 1000회 검증 통과
['c', 'd', 'e']

각 인덱스는 덱에 한 번 들어가고 많아야 한 번 나온다. 그래서 while 이 안에 있어도 전체는 O(n) 이다. 이것도 분할 상환 분석이다. 그리고 단순한 방식과 무작위 입력으로 대조해 정답을 확인했다. 알고리즘을 직접 짤 때는 이런 대조 검증을 같이 쓰는 습관이 실수를 크게 줄인다.

현업에서는

파이썬 작업 큐. list.pop(0) 을 deque.popleft() 로 바꾸는 것은 가장 흔하고 효과 큰 성능 수정 중 하나다. BFS, 이벤트 처리 루프, 생산자·소비자 버퍼 모두 해당한다.
최근 N 개 보관. 요청 지연 시간 최근 1000건, 최근 로그 몇 줄을 들고 있는 모니터링 코드에 deque(maxlen=...) 이 자주 보인다. 메모리 상한이 자동으로 걸린다.
일 훔치기 스케줄러. 자바 Fork/Join 이나 여러 언어의 태스크 런타임은 워커마다 덱을 두고, 자기 덱은 한쪽 끝에서 쓰고 놀고 있는 워커는 남의 덱 반대쪽 끝에서 일을 훔쳐 가는 구조를 쓴다. 양 끝의 경합을 분리하는 것이 핵심이다.
포인터 안정성. C++ 에서 원소의 주소를 다른 곳에 저장해 두어야 한다면 vector 보다 deque 가 안전할 수 있다. 양 끝 삽입이 기존 원소 참조를 무효화하지 않기 때문이다. 다만 가운데 삽입은 예외다.

확인 문제

덱 하나로 스택과 큐를 각각 흉내 내려면 어떤 연산 쌍을 쓰면 되는가?
원형 버퍼 덱에서 cap = 8, head = 0 일 때 appendleft 를 하면 새 head 는?
파이썬 deque 에서 d[len(d)//2] 가 리스트보다 느린 이유는?
슬라이딩 윈도 최댓값 알고리즘이 안쪽 while 루프에도 불구하고 O(n) 인 이유는?
deque(maxlen=3) 에 appendleft 로 4개를 넣으면 어느 쪽 원소가 버려지는가?

풀이

스택: append + pop (같은 끝). 큐: append + popleft (반대 끝).
(0 - 1) % 8 = 7.
CPython deque 는 고정 크기 블록을 이은 구조라 가운데 블록까지 따라가야 한다. 문서도 가운데 인덱스 접근은 O(n) 으로 느려진다고 적는다.
각 인덱스가 덱에 한 번 들어가고 많아야 한 번 나오므로 pop 의 총 횟수가 n 이하다.
오른쪽(뒤쪽) 끝 원소가 버려진다. 넣는 반대쪽이 밀려난다.

더 읽을거리 (References)

Python Documentation, collections — deque objects
The Rust Standard Library, VecDeque
cppreference.com, std::deque
Oracle, Java SE 21 API — ArrayDeque