덱

양쪽 끝에서 삽입과 삭제가 가능.

deque 이면서 Double Ended Queue라는 뜻을 지니고 있다함

일반적으로 아는 deck이랑은 다른 단어임

 

1. 원소의 추가가 O(1)

2. 원소의 제거가 O(1)

3. 제일 앞/뒤의 원소 확인이 O(1)

4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

 

덱에서도 삽입,삭제,제일 앞/뒤 원소의 확인이 O(1)이다.

제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다는데

특이하게도 STL deque에서는 인덱스로 원소에 접근할 수 있음.

STL stack, queue에서는 불가능했던 거라 특이함.

 

배열로 구현한다 치면,

가운데 인덱스에서 시작하는게 좋음

 

STL deque에 insert와 erase도 있고 front에서도 O(1)의 속도를 보이니

vector의 상위호환인가 싶지만,

vector와 달리 deque의 원소들은 메모리 상에 연속하게 배치되어 있지 않다.

 

둘을 굳이 짧게 비교하자면,

앞쪽에서의 추가,제거가 필요하면 deque를,

그렇지 않고 배열느낌으로 쓸거면 vector가 낫다는 듯.