#.5 Deque

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 비교를 해봐야겠다.

참고자료

https://leonkong.cc/posts/python-deque.html

https://dongdongfather.tistory.com/72