deque(double-ended queue)는 「양쪽 끝에서 매우 빠른 추가·삭제가 가능한」 자료구조입니다.
리스트의 앞쪽 추가(insert(0, x))는 O(n) 시간이 들지만, deque는 양쪽 모두 O(1)입니다.
기본 사용.
from collections import deque.
d = deque([1, 2, 3]).
d.append(4) — 끝에 추가.
d.appendleft(0) — 앞에 추가.
d.pop() — 끝에서 꺼내기.
d.popleft() — 앞에서 꺼내기.
양방향 모두 한 줄로 빠르게 동작합니다.
활용 패턴 1: 큐(Queue).
FIFO(First-In-First-Out) 처리에 자연스럽습니다.
d.append(작업)으로 작업 추가, d.popleft()로 가장 오래 기다린 작업 꺼내기.
BFS(너비 우선 탐색) 알고리즘의 표준 자료구조입니다.
활용 패턴 2: 최근 N개 유지.
deque(maxlen=10)으로 만들면 「최근 10개만 유지」하는 자동 컬렉션이 됩니다.
11번째를 추가하면 가장 오래된 것이 자동으로 빠져나갑니다.
로그 버퍼·최근 사용 항목 추적에 편리합니다.
비유하자면 deque는 「양쪽이 다 열린 파이프」와 같습니다.
어느 쪽으로든 자유롭게 넣고 빼며, maxlen이 있으면 「길이 제한이 있는 호스에서 한쪽으로 새 물을 넣으면 다른 쪽으로 옛 물이 자동으로 빠지는」 식입니다.
BFS 알고리즘이나 슬라이딩 윈도우 패턴에서 결정적입니다.
한 줄 요약
deque는 양쪽 끝에서 O(1) 추가·삭제가 가능한 자료구조로, 큐·BFS·최근 N개 유지(maxlen) 같은 패턴에 결정적입니다.
리스트의 앞쪽 조작이 느릴 때 deque가 답입니다.
더 알아볼 것
- BFS 알고리즘 구현 예시
- Queue 모듈 vs deque
- Stack도 deque로 가능
