Deque란?

Deque 

STL 컨테이너 중 하나로, 리스트의 양쪽 끝에서 삽입과 삭제를 모두 사용 가능하다.

(pop_front, pop_back,push_front,push_back 등 사용 가능)

스택과 큐의 자료구조를 복합한 형태라고 볼 수 있다.

 

Deque를 사용하는 경우

1. 앞과 뒤에서 삽입 또는 삭제를 할 경우.

2. 저장할 데이터 개수가 가변적일 경우.

3. 데이터 접근을 랜덤하게 하고 싶을 경우.

etc..

 

Vector 와 Deque의 차이점

1. Deque는 저장 원소가 많고 메모리 할당량이 큰 경우 , Vector에 비해 확장 비용이 절감된다.

2. Deque는 Vector와 달리 포인터 연산이 불가능하다.

 

장점

1. 개별 원소를 index로 접근할 수 있다.

2. 원소를 컨테이너의 끝 뿐 아니라, 앞에서도 삽입과 삭제 연산이 빠르다.

3. 어떠한 순서로도 원소들을 순회할 수 있다 (앞->뒤 or 뒤->앞)

4. 동적으로 컨테이너의 크기의 확장, 축소를 편하게 할 수 있다.

 

단점

1. 컨테이너의 끝이나 시작 위치가 아닌 , 중간 지점에서 삽입 / 삭제 시, 성능이 Vecotr보다 떨어진다.

2. 확장시의 재분배 비용이 크다. (reallocation)

 

 

참고 블로그 : https://includecoding.tistory.com/45