[STL] deque

deque(double-ended queue)는 기존 STL vector의 단점을 보완하기 위해 만들어진 자료구조이다.

 

vector는 동적 배열이다. 즉 배열이라는 의미다.

 

그 말인 즉슨, vector는 기존 배열이 가진 장점과 단점을 대부분 가지고 있다.

 

배열은 데이터가 입력이 되면 기존에 존재하던 데이터의 배열 끝에 새로운 데이터가 입력이 된다. 이는 vector에서 push_back이라는 함수를 보면 알 수 있다.

 

지울 때도 마찬가지로 뒤에서부터 자료를 삭제한다. pop_back이 그 함수이다.

 

그렇다면 왜 push_front나 pop_front는 없을까?

 

이는 간단하다. 배열의 구조는 순차적이기 때문이다.

 

가령 맨 앞의 데이터를 지우고자 한다면 vector에선 어떻게 작동을 할까?

위 vector에서 0번 인덱스를 지우려고 한다. 함수를 이용해 데이터를 지우면 처음 모양은 다음과 같다.

 

여기서 끝나면 좋겠지만 그렇지 않다. vector는 동적 배열이다. 배열은 시작점에서부터 자신이 가지고 있는 데이터의 메모리 크기만큼 이동하여 인덱스를 구분한다.

 

제일 앞자리가 비워진다면 다음 데이터를 검색하기가 어렵다. 때문에 기존의 데이터들은 한 칸씩 앞으로 이동하게 된다.

 

이 경우 작은 크기의 배열이라면 문제가 발생하지 않겠지만 크기가 큰 배열의 경우 비용이 크게 들어가게 된다. 때문에 이를 보완하고자 나온 것이 바로 deque이다.

 

deque는 vector와 다르게 앞과 뒤 양쪽에서 삽입과 삭제가 가능하다. 때문에 앞쪽에서 일어나는 삭제 / 삽입에 대한 메모리 비용이 크게 들어가지 않는다는 장점이 있다.

출처 - https://blog.daum.net /coolprogramming/81

또한 배열의 공간이 가득 차게 되면 새로운 배열을 만들어 기존 데이터를 복사하고 기존 배열을 파괴하는 vector와 달리 deque는 그냥 새로운 배열 공간을 하나 더 만드는 것일 뿐이라 데이터 삽입에 대한 효율이 보다 뛰어나다.

 

출처 - https://blog.daum.net /coolprogramming/81