[STL] deque

시퀀스 컨테이너(Sequence Container)
데이터가 삽입 순서대로 나열되는 형태로
vector, list, deque가 있다

 

deque(double-ended queue)란?
양쪽 끝에서의 삽입과 삭제를 효율적으로 지원하는 자료 구조이다

deque는 큐(queue)와 벡터(vector)의 결합체로,

큐와 마찬가지로 FIFO(First-In-First-Out)의 특성을 가지고 있으면서도

벡터처럼 임의의 위치에서의 접근이 가능합니다.

deque는 블록(block)으로 구성되어 있으며,

각 블록은 일정 개수(일반적으로는 4개)의 요소를 저장하고

내부적으로 블록 간의 참조를 조정하여 삽입과 삭제를 효율적으로 수행할 수 있다

 

deque vs. vector
deque는 capacity가 존재하지 않는다
데이터가 추가될 때마다 que 블록이 추가되기 때문이다

 

그리고 아래의 코드를 통해 비교하면,

vector<int> v(4, 1);
deque<int> dq(4, 1);

v.push_back(2);
dq.push_back(2);

v.push_front(0);
dq.push_front(0);

 

1) push_back

vector의 경우 capacity를 초과해서 push_back을 하면

새로운 공간을 할당해서 전체 이동이 이루어진다

 

deque의 경우 현재 블록을 초과해서 push_back을 하면

새로운 블록을 할당해서 추가된 데이터만 그 블록에 들어간다  

 

2) push_front

vector의 경우 push_front을 하면

모든 데이터를 한 칸씩 뒤로 민다

 

deque의 경우 push_front을 하면

새로운 공간을 할당해서 추가된 데이터만 그 공간에 들어간다  

 

deque의 효율
1) 중간 삽입/삭제
중간에 데이터가 삽입/삭제될 때,
vector처럼 모든 데이터를 앞으로 뒤로 한 칸씩 다 당겨야 하기 때문에
매우 비효율적이다

2) 처음/끝 삽입/삭제
처음/끝에서 삽입은
que 블록을 맨 앞쪽/뒤쪽에 추가해 주면 된다

처음/끝에서 삭제는
que 블록의 맨 앞/맨 뒤 데이터만 지워주면 된다
이처럼 매우 효율적이다

3) 임의 접근
임의 접근을 할 때, 
모든 데이터들은 블록과 오프셋이 정해져 있기 때문에 
인덱스를 통해 쉽게 접근이 가능하다