공부/개념 & 유용한 내용
Deque란?
ENUM01
2020. 6. 10. 10:39
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