덱은 양쪽에서 삽입과 삭제가 가능한 자료구조다.
스택과 큐를 덱의 일종이라고 생각할 수 있다.
이름인 Deque는 Double Ended Queue를 줄인 것이다.
Restricted Structure의 끝판왕같은 자료구조라 할 수 있다.
덱의 성질
- 원소의 추가: O(1)
- 원소의 제거: O(1)
- 제일 앞/뒤의 원소 확인: O(1)
- 그 외의 원소 확인 원칙적으로 불가능(독특하게도 STL deque에서는 인덱스로 접근할 수 있다.)
덱을 배열로 구현할 때는 시작지점을 중간으로 둬야 한다.
큐와는 달리 왼쪽으로도 확장이 가능하기 때문이다.
'algorithm & data structure > 자료구조' 카테고리의 다른 글
| 그래프(Graph) (0) | 2022.11.16 |
|---|---|
| 우선순위 큐(Priority Queue) (0) | 2022.11.13 |
| 큐(Queue) (0) | 2022.10.29 |
| 스택(Stack) (0) | 2022.10.28 |
| 트리 (0) | 2022.10.23 |