[STL 컨테이너] deque (+ 다른 자료구조들과의 차이점)

🚀 deque 컨테이너 소개

#include <deque>

double ended queue 컨테이너의 맨 앞과 맨 뒤에서 삽입/제거를 빠르게 할 수 있다는 것이 대표적 특징이다. 스택(LIFO)과 큐(FIFO)를 합쳐놓은 것이라고 생각하면 될 것 같다.

맨 앞 원소와 맨 뒤 원소 삽입/제거가 빈번하다면 deque를 고려하는 것이 좋겠다.

🔥 deque 의 특징 (다른 자료구조들과의 비교)

• vector 처럼 원소들을 [] 인덱스를 사용하여 Random Access 가 가능하다.
  • stack 과 queue 와 차별화된 강점
• vector 처럼 원소들을 어떤 순서로든 앞로든 뒤 원소들을 순회할 수 있다.
• vector 가 capacity 가 고갈되면 전체 메모리 크기의 이상을 재할당 받는 것과 달리 deque 는 일정 크기를 가지는 chunk 단위로 메모리가 확장된다.
  • vector 보다 확장 비용이 절감된다.
• vector 와 달리 연속 메모리 공간이 아니다.
  • 따라서 vector와 달리 포인터 연산이 불가능하다.
• list 처럼 연속 메모리 공간이 아니다.
• stack, vector, list 처럼 맨 뒤에서 삽입/제거 하는 것이 빠르다.
  • queue 은 오직 맨 앞에서만 제거가 가능하지만 deque 는 맨 뒤에서도 제거가 가능
  • stack 과 queue 가 deque 로 구현 가능한 이유.
• queue, list 처럼 맨 앞에서 삽입/제거 하는 것이 빠르다.
  • vector 와 차별화된 강점
  • stack 은 오직 맨 뒤에서만 제거가 가능하지만 deque 는 맨 앞에서도 제거가 가능
  • stack 과 queue 가 deque 로 구현 가능한 이유.
• list 와 달리 맨 뒤, 맨 앞이 아닌 **중간 원소를 삽입/제거 하는 것은 느리다.</u**

🚀 함수

vector 와 다르게 맨 앞 원소를 삭제하는 pop_front, 맨 앞에 추가하는 push_front 함수가 있다. 이것 빼고는 vector 의 멤버들과 같다. [STL 컨테이너] vecto

🚀 참고 및 출처

• 수까락의 프로그래밍 이야기 http://egloos.zum.com/sweeper/v/2817817
• 한빛출판네트워크 https://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS3942847236

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

STL 카테고리 내 다른 글 보러가기