[Data Structure] Deque 사용법

• c++ STL 중 하나인 Deque에 대한 설명입니다.

Deque

• Deque는 Double-ended queue의 약자로 양쪽 어디에서든 추가, 삭제가 가능한 구조인 큐입니다.

• Queue 에서는 원소를 접근하기 위해서 front를 통해 하나씩 가져왔다면, Deque는 iterator와 index 접근이 모두 가능합니다. push_back, push_front, pop_back, pop_front와 같은 API를 사용하여 어디에서든 추가가 가능하고 front, back 함수를 통해 원소를 쉽게 가져올 수 있습니다.

• API 형태나 index 접근이 가능한것만 보면 Queue 보다는 Vector의 형태처럼 보이고, 오히려 vector보다 양쪽 끝 원소는 쉽게 가져올 수 있기 때문에 상위호환처럼 보일 수 있습니다.

• 하지만, Deque와 Vector와의 차이점음 명확하게 존재하고 취업 면접 시 CS(Computer Science) 질문으로 나올 수 있어서 미리 알아두면 유용합니다.

Deque vs Vector

• Deque는 시퀀스의 끝 부분 뿐만 아니라 앞 부분에서도 추가, 삭제가 효율적입니다.

• Vector는 배열처럼 연속된 메모리 공간을 차지하는 반면, Dequeue는 모든 원소들이 연속된 공간에 저장되지 않습니다. 그만큼 주소공간에 offset을 두어서 접근할 수 없고, Cache 적용 시에도 Cache hit율이 떨어질 수밖에 없습니다.

• 반대로, vector는 시퀀스를 증가시키기 위해서는 배열 자체적으로 재할당해야 하는 경우가 있지만 Deque는 chunk 단위로 메모리가 흩어져 있기 때문에 길이가 긴 시퀀스일 경우는 Deque가 효율적일 수 있습니다.

• 자세한 내용은 레퍼런스를 참조하면 좋습니다.

API

• operator= : 대입연산자가 정의되어 있어 새로운 deque 인스턴스에 대입이 가능

• Iterators : begin, end, rbegin, rend와 같은 iterator로 원소들 접근 가능

• size : deque의 size 반환하는 함수

• empty : deque의 원소 유무 확인하는 함수

• operator[] : 연산자가 정의되어 있어서 index로 접근 가능

• front : deque의 앞 부분의 원소를 반환하는 함수

• back : deque의 뒷 부분의 원소를 반환하는 함수

• push_back : deque의 뒷 부분에 원소 추가하는 함수

• push_front : deque의 앞 부분에 원소 추가하는 함수

• pop_back : deque의 뒷 부분 원소 삭제하는 함수

• pop_front : deque의 앞 부분 원소 삭제하는 함수

• insert : 매개변수 iterator에 원소 추가하는 함수

• erase : 매개변수 iterator의 원소 삭제하는 함수

• clear : 초기화하는 함수

Example

	#include<iostream>
	#include<deque>
	using namespace std;
	int main(){
	deque<int> dq;
	dq.push_back(1); // 1
	dq.push_back(2); // 1 2
	dq.push_front(3); // 3 1 2
	dq.push_front(4); // 4 3 1 2
	for(int i=0;i<dq.size();i++){
	cout<<dq[i]<<' ';
	}
	cout<<endl;
	dq.pop_back(); // 4 3 1
	dq.pop_front(); // 3 1
	for(int elem : dq){
	cout<<elem<<' ';
	}
	cout<<endl;
	deque<int> copydq = dq; // 3 1
	for(int elem : copydq){
	cout<<elem<<' ';
	}
	cout<<endl;
	dq.insert(dq.begin()+1, 2); // 3 2 1
	for(int elem : dq){
	cout<<elem<<' ';
	}
	cout<<endl;
	dq.erase(dq.begin()); // 2 1
	for(int elem : dq){
	cout<<elem<<' ';
	}
	cout<<endl;
	}

view raw deque.cpp hosted with ❤ by GitHub

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.