덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조다. 스택과 큐의 기능을 모두 가지며, 슬라이딩 윈도우 최댓값 같은 알고리즘에 핵심적으로 사용된다.
연산
Front ◄──────────────────────► Rear
append_left append_right
pop_left pop_right
구현
python
from collections import deque
dq = deque()
# 오른쪽 삽입/삭제
dq.append(1) # [1]
dq.append(2) # [1, 2]
dq.pop() # [1] → 2 반환
# 왼쪽 삽입/삭제
dq.appendleft(0) # [0, 1]
dq.popleft() # [1] → 0 반환
# 크기 제한 덱
dq = deque(maxlen=3)
for i in range(5):
dq.append(i)
print(dq) # deque([2, 3, 4], maxlen=3)
시간 복잡도
| 연산 | 복잡도 |
|---|
| 양끝 삽입/삭제 | O(1) |
| 중간 접근 | O(n) |
슬라이딩 윈도우 최댓값 예시
python
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # 인덱스 저장
result = []
for i, n in enumerate(nums):
# 범위 밖 제거
while dq and dq[0] < i - k + 1:
dq.popleft()
# 현재보다 작은 원소 제거
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]
관련 개념
- •스택 — 한쪽 끝만 사용
- •큐 — 한쪽으로 넣고 반대쪽으로 꺼냄
- •슬라이딩 윈도우 — 덱을 활용한 알고리즘
참고문헌
- •Cormen et al. Introduction to Algorithms
