std::deque

덱(deque)은 양방향 큐(double-ended queue)의 약자입니다.

 

덱의 필요조건

push_pront(), pop_front(), push_back(), push_pop_back() 동작이 o(1)의 시간 복잡도로 동작해야 합니다.

 

모든 원소에 대해 임의 접근 동작이 o(1) 시간 복잡도로 동작해야 합니다.

 

덱 중간에서 원소 삽입 또는 삭제는 o(n) 시간 복잡도로 동작해야 하며, 실제로는 최대 n/2 단계로 동작합니다. n은 덱의 크기입니다.

 

덱을 이용한 삽입 삭제

#include <iostream>
#include <deque>

int main()
{
	std::deque<int> deq = { 1,2,3,4,5 }; 
	// 맨 뒤에 0 추가
	deq.push_front(0);
	// 맨 뒤에 6 추가
	deq.push_back(6);
	// 맨 앞에서 2칸 뒤에 10 추가
	deq.insert(deq.begin() + 2, 10);
	// 맨 뒤 원소 삭제
	deq.pop_back();
	// 맨 앞 원소 삭제
	deq.pop_front();
	// 맨 앞 + 1 위치에 있는 값 삭제
	deq.erase(deq.begin() + 1);
	// 맨 앞 + 3 위치부터 끝까지 있는 값 삭제
	deq.erase(deq.begin() + 3, deq.end());

}