Deque (Double-ended queue)

이름에서 알 수 있다시피, queue인데 앞/뒤 양쪽에서 원소를 추가/제거 가능함.

앞/뒤 원소 추가/제거에 대해선 굉장히 효율적이라고 함.

 

	deque	vector
크기 변경 가능	O	O
앞에 삽입, 삭제 용이	O	X
뒤에 삽입, 삭제 용이	O	O
중간 삽입, 삭제 용이	X	X
순차 접근 가능	O	O
랜덤 접근 가능	O	X

[표 1] deque와 vector의 차이 (출저 : 한빛소프트 About STL C++ STL 프로그래밍)

 

 

Q. 그럼 벡터랑 다를게 뭐냐?

→ 벡터는 contiguous memory에 원소 저장, deque는 일정 block 단위로 엮어서 저장한다는 구조적 차이.

그리고 이에서 오는 operation의 overhead가 다름.

stackoverflow.com/questions/5345152/why-would-i-prefer-using-vector-to-deque

Why would I prefer using vector to deque

추가로, deque가 queue의 완전 상위 개념인지 궁금해서 찾아보았다.

stackoverflow.com/questions/2247982/c-deque-vs-queue-vs-stack

c++ deque vs queue vs stack

std::stack, std::queue 는 실제로 데이터를 담는 container가 아닌, 인터페이스만 제공해주는 container adapter라는거고, 이걸 실제 구현하기 위해 다른 실제 container들이 (ex. std::deque, std::list, std::vector) 필요한 것 같다.

en.cppreference.com/w/cpp/container

Containers library - cppreference.com