deque (덱)

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

 

push_front(), push_back()으로 이름처럼 양방향으로 확장이 가능하다.

또한 리스트와는 다르게 원소에 임의 접근이 가능하다.

중간에 원소를 삽입하면 가까운 끝 방향으로 원소들을 이동한다. (이는 최대 n/2 시간 복잡도를 가짐)

 

#include <iostream>
#include <deque>

int main()
{
	std::deque<int> dq;
	dq = { 1, 2, 3, 4,5 };

	dq.push_front(0); // 0, 1, 2, 3, 4,5

	dq.push_back(6); // 0, 1, 2, 3, 4, 5, 6

	dq.insert(dq.begin() + 4, 9); // 0, 1, 2, 3, 9, 4, 5, 6

	dq.pop_back(); // 0, 1, 2, 3, 9, 4, 5

	dq.pop_front(); // 1, 2, 3, 9, 4, 5

	dq.erase(dq.begin() + 1); // 1, 3, 9, 4, 5

	dq.erase(dq.begin() + 3, dq.end()); // 1, 3, 9

	for (std::deque<int>::iterator itr = dq.begin(); itr != dq.end(); itr++) {
		std::cout << *itr << std::endl;
	} // 1, 3, 9
}