특징
Deque(Double Ended Queue)은 일반적인 큐와 마찬가지로 데이터의 삽입 삭제를 수행하는 자료구조이다.
큐는 rear에서 삽입이 일어나고 front에서 삭제가 발생한다면, 덱은 rear와 front 어느 곳에서든 삽입 삭제가 모두 이루어 질 수 있다.
덱의 약간 변형된(?) 종류에는 2가지 덱이 존재한다.
- 입력제한덱(Scroll)
- 출력제한덱(Shelp)
입력제한덱은 덱에서의 데이터 삽입을 한쪽으로만 제한해둔 덱이다.
입력을 제한둿다 하여 입력제한덱(Input restricted deque) 혹은 스크롤(Scroll)이라고 불린다.
출력제한덱은 덱에서의 데이터 삭제를 한쪽으로만 제한해둔 덱이다.
출력을 제한둿다 하여 출력제한덱(Output restricted deque) 혹은 셸프(Shelf)라고 불린다.
연산
덱의 연산은 크게 push(데이터 삽입), pop(데이터 삭제)으로 나눌 수 있다.
push()
덱의 삽입은 Queue와 같은 형태로 데이터를 덱에 삽입하는 연산이다.
다만 Depue는 양쪽으로 데이터 삽입이 가능하기에 rear와 front 어느 쪽에서든지 원하는 곳으로 데이터를 삽입할 수 있다.
pop()
삭제 역시 데이터를 덱에서 삭제하는 연산이다.
rear와 front 모두에서 데이터를 삭제할 수 있다.
시간복잡도
| 연산 | 복잡도 |
|---|---|
| push | O(1) |
| pop | O(1) |
| selection | O(1) |
삽입 연산인 push의 경우, 데이터를 rear로 삽입하든 front의 삽입하든 즉시 데이터를 넣는 것이므로 O(1)이다.
삭제 연산 또한 rear로 삭제하든 front로 삭제하든 삭제하는 시간은 똑같이 O(1)이 된다.
검색 연산의 경우는 덱에 있는 데이터를 인덱스로 접근하기 때문에 시간복잡도는 O(1)이 된다.
장단점
장점
- 크기가 가변적이다.
- 데이터의 삽입, 삭제가 빠르다.
- 원하는 요소에 바로 접근이 가능하다.
단점
- 구현이 어렵다.
- 데이터 중간의 삽입, 삭제가 용이하지 않다.
사용사례
사실 덱이 자주 쓰이는 편은 아니다.
덱은 주로 앞, 뒤 모두에서 삽입, 삭제가 이루어질 때 사용된다.
또한 덱은 데이터가 가변적일 때 일반적으로 사용된다.
Reference
