자료구조
#.5 Deque
Haksae
2022. 3. 9. 04:15
Deque (Double-ended-queue)
- 덱(deque)은 double-ended queue의 줄임말이다.
- rear로만 데이터를 삽입했던 큐와 달리, front와 rear에서 삽입과 삭제가 모두 가능한 양방향 큐이다.
- 연속적인 메모리를 기반으로 하는 시퀀스 컨테이너이고, 선언 이후 크기를 줄이거나 늘릴 수 있는 가변적 크기를 갖는다.
- 또한 중간에 데이터가 삽입될 떄 다른 요소들을 앞, 뒤로 밀 수 있다. 중간 삭제시 성능이 그리 좋진 않다.
- 삽입 삭제 연산은 O(1)의 시간 복잡도를 가지고, 스택&큐와 달리 index를 통해 요소들에 탐색이 가능하므로 검색 또한 O(1)의 시간복잡도를 가진다.
- 장점
- 구현자의 편의에 따라 deque는 stack처럼 사용할 수도 있고, queue처럼 사용할 수 있다.
- 크기가 가변적이다.
- 앞 뒤 양쪽에서 요소를 추가하거나 제거할 수 있고, 이에 대한 시간 복잡도는 O(1)이다.
- 검색 또한 인덱스를 활용하므로 시간 복잡도가 O(1)이다.
- 새로운 원소 삽입시, 메모리를 재할당하거나 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.
- 단점
- 중간에서의 삽입 삭제가 어렵다.
- 스택, 큐에 비해 비교적 구현이 어렵다.
- 추후에 vector와 deque, list 비교를 해봐야겠다.
참고자료