데크 (deque)

데크 (deque - Double Ended Queue)

• 양쪽 끝에서 삽입, 삭제 모두 가능함

시간 복잡도

1. 원소추가 : O(1)
2. 원소제거 : O(1)
3. 가장 앞/뒤 원소 확인 : O(1)
4. 가장 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
   => STL queue 에서는 인덱스로 원소에 접근이 가능

STL deque

STL vector 와의 유사함

공통점

• STL vector 에서 제공되는 기능을 STL stack 에서도 다 제공

• 인덱싱도 가능

차이점

• 연속된 메모리에 배치되어 있지 않다.

=> deque 는 front 에서도 O(1) 에 추가와 제거가 가능하므로,
deque 가 vector 보다 상위호환이라는 생각이 들 수 있지만,
vector 와 달리 deque 는 원소들이 메모리 상에 연속하게 배치되어 있지않다.

• 연속적인 메모리 공간이 아니므로, vector 에서 가능했던 원소들간 포인터 연산이 불가능하다.

앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요하면 STL deque 를 사용하고,
굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고 싶다면 STL vector 를 쓰자 !

메소드 종류

• 인덱싱 가능 ex) dq[2] = 17;
• push_front() => vector에 없는 기능
• push_back()
• pop_front() => vecto에 없는 기능
• empty()
• size()
• insert()
• erase()
• clear()
• begin()

예제

#include <iostream>
#include <deque>
using namespace std;

int main(void)
{
	deque<int> dq;

	dq.push_front(10);
	dq.push_back(50);
	dq.push_front(24);

	for (auto data : dq)
		cout << data;

	if (dq.empty())
		cout << "dq is empty" << "\n";
	else
		cout << "dq is not empty" << "\n";

	dq.pop_front();
	dq.pop_back();

	cout << dq.back() << "\n";

	dq.push_back(72);
	dq.push_back(12);

	cout << dq.front() << "\n";

	dq[2] = 17;

	dq.insert(dq.begin() + 1, 33);
	dq.insert(dq.begin() + 4, 60);

	dq.erase(dq.begin() + 3); 

	dq.clear(); // 모든 원소 제거
}