덱(Deque, Double-Ended Queue)

개요

덱(Deque, Double-Ended Queue)은 양쪽 끝(front, rear) 모두에서 삽입과 삭제가 가능한 선형 자료구조이다. 일반 큐는 FIFO, 스택은 LIFO 원칙만 따르지만, 덱은 스택과 큐의 기능을 모두 갖춘 유연한 자료구조로, 양방향에서 데이터를 처리할 수 있다. 파이썬에서는 collections.deque 모듈을 통해 효율적인 덱을 구현할 수 있다.

---

1. 개념 및 정의

구성 요소	설명
front	덱의 앞쪽 끝, 요소 삽입/삭제 가능
rear	덱의 뒤쪽 끝, 요소 삽입/삭제 가능
연산	append, appendleft, pop, popleft, peek

덱은 입력 제한 덱(Input-Restricted Deque), 출력 제한 덱(Output-Restricted Deque) 등으로 확장 가능하다.

---

2. 주요 연산 예시

from collections import deque

dq = deque()
dq.append(10)        # rear 삽입
dq.appendleft(5)     # front 삽입
print(dq.pop())      # rear 삭제 → 10
print(dq.popleft())  # front 삭제 → 5

---

3. 시간 및 공간 복잡도

연산	시간 복잡도
append / appendleft	O(1)
pop / popleft	O(1)
peek	O(1)

deque는 양쪽에서 빠른 삽입/삭제를 제공하는 자료구조다.

---

4. 덱 vs 큐 vs 스택 비교

항목	스택	큐	덱
입출력 방향	한쪽(LIFO)	양쪽(FIFO)	양쪽 모두 가능
삽입 위치	Top	Rear	Front & Rear
삭제 위치	Top	Front	Front & Rear
사용 예시	함수 호출, 수식 계산	BFS, 이벤트 처리	슬라이딩 윈도우, 캐시 구현

---

5. 덱의 활용 사례

분야	활용 예시
슬라이딩 윈도우 최댓값	최대값/최솟값을 O(1)로 유지하며 계산
캐시 알고리즘	LRU 캐시 (front에 삽입, rear에서 제거 등)
문자열 처리	회문 판별 (앞뒤에서 비교)
게임 개발	캐릭터 이동 히스토리 저장/복원
알고리즘 문제풀이	0-1 BFS, 스택-큐 통합 구조 구현

---

6. 구현 구조

덱은 내부적으로 이중 연결 리스트 또는 원형 배열을 기반으로 구현될 수 있다.

구현 방식	설명	특징
이중 연결 리스트	앞뒤 포인터로 구성	삽입/삭제 유연, 메모리 사용 ↑
원형 배열 기반	front/rear 인덱스 순환 사용	고정 크기, 빠른 성능

파이썬의 collections.deque는 C로 구현된 원형 이중 연결 리스트 기반이다.

---

7. 파이썬 덱 메서드 정리

메서드	설명
append(x)	뒤에 x 추가
appendleft(x)	앞에 x 추가
pop()	뒤 요소 제거 및 반환
popleft()	앞 요소 제거 및 반환
extend(iter)	뒤에 여러 개 추가
extendleft(iter)	앞에 여러 개 추가
rotate(n)	요소를 n만큼 회전

---

8. 결론

덱은 큐와 스택의 장점을 결합한 유연한 자료구조로, 양방향 삽입/삭제가 모두 필요한 경우 매우 유용하다. deque는 알고리즘 문제풀이뿐 아니라, 캐시 구조, 윈도우 계산, 이벤트 처리 등 다양한 실무 환경에서도 활용 가능하며, 자료구조 학습의 필수 개념 중 하나다.