정의
덱(Deque, Double‑Ended Queue)은 양쪽 끝에서 원소의 삽입과 삭제가 모두 가능한 선형 자료 구조를 의미한다. 전통적인 큐(queue)가 하나의 끝(front)에서 삭제하고 다른 끝(rear)에서 삽입하는 반면, 덱은 앞(front)과 뒤(rear) 양쪽 모두에서 삽입(push)과 삭제(pop)가 가능하다.
주요 연산
| 연산 | 설명 | 시간 복잡도(평균) |
|---|---|---|
push_front(x) |
앞쪽에 원소 x 삽입 | O(1) |
push_back(x) |
뒤쪽에 원소 x 삽입 | O(1) |
pop_front() |
앞쪽 원소 삭제 및 반환 | O(1) |
pop_back() |
뒤쪽 원소 삭제 및 반환 | O(1) |
front() |
앞쪽 원소 조회 (삭제는 안 함) | O(1) |
back() |
뒤쪽 원소 조회 (삭제는 안 함) | O(1) |
size() |
현재 원소 개수 반환 | O(1) |
empty() |
비어 있는지 여부 반환 | O(1) |
구현 방식
-
배열 기반
- 원형 버퍼(circular buffer)를 이용해 고정 크기의 배열에 원소를 저장한다.
- 인덱스를 앞·뒤 두 방향으로 이동시키며 삽입·삭제를 수행한다.
- 고정 크기이므로 필요 시 재할당을 통해 동적 확장이 가능하다.
-
연결 리스트 기반
- 이중 연결 리스트(doubly linked list)를 사용한다.
- 각 노드가 앞·뒤 이웃을 가리키므로 삽입·삭제가 포인터 교체만으로 O(1) 시간에 이루어진다.
- 동적 메모리 할당이 필요하므로 메모리 사용량이 배열 기반보다 다소 높다.
사용 사례
- 알고리즘: 슬라이딩 윈도우(max/min) 문제, BFS에서 레벨 구분 등
- 시스템: 운영체제의 작업 스케줄러, 프린터 스풀링, 네트워크 패킷 버퍼
- 프로그래밍 언어 라이브러리:
- C++:
std::deque - Python:
collections.deque - Java:
ArrayDeque,LinkedList(Deque 인터페이스 구현)
- C++:
장점 및 단점
| 장점 | 단점 |
|---|---|
| 양쪽 끝에서 O(1) 삽입·삭제 가능 | 중간 원소에 대한 접근은 O(n) |
| 배열 기반 구현 시 연속된 메모리 사용 → 캐시 친화적 | 고정 크기 배열일 경우 용량 초과 시 재할당 필요 |
| 연결 리스트 기반은 크기 제한이 없고 삽입·삭제가 자유로움 | 포인터 관리 오버헤드와 메모리 파편화 위험 |
관련 자료 구조
- 스택(Stack): 한쪽 끝에서만 삽입·삭제가 가능한 LIFO 구조. 덱의
push_back/pop_back을 이용해 구현 가능. - 큐(Queue): 한쪽 끝에서 삽입, 다른 쪽 끝에서 삭제가 가능한 FIFO 구조. 덱의
push_back/pop_front을 이용해 구현 가능. - 원형 버퍼(Circular Buffer): 고정 크기 배열을 원형으로 활용한 구조로, 덱의 배열 기반 구현 중 하나.
참고
- 기본적인 자료 구조 및 알고리즘 교재(예: "Introduction to Algorithms", Cormen 외)에서 덱은 “double‑ended queue”로 기술된다.
- 각 프로그래밍 언어 표준 라이브러리 문서에서도
deque혹은Deque인터페이스에 대한 상세 설명을 제공한다.
이 문서는 공개된 신뢰할 수 있는 자료(학술 서적, 표준 라이브러리 문서 등)에 기반하여 작성되었습니다.
