[C++] Deque

Deque는 Queue와 Stack이 자료를 한 방향에서만 처리할 수 있는 것과는 다르게

앞과 뒤에서 모두 데이터를 삽입, 제거할 수 있다.

Deque의 삽입과 제거는 Queue, Stack 과 같이 모두 O(1)의 시간이 소요된다.

Deque와 비슷한 자료구조로는 List가 있는데 List의 경우 앞 or 뒤에서 데이터를 처리할 경우

O(n)의 시간이 소요되므로 경우에 따라서는 Deque의 성능이 압도적으로 좋아질 수 있다.

 

C++에서의 Deque 사용법

 

1) deque를 헤더파일에 추가한다.

#include <deque>

 

2) deque 선언

deque <자료형> 이름;

 

3) deque의 여러 기능

deque <int> dq로 선언 이후

dq.push_front(원소) : dq의 첫 번째 원소 앞에 삽입

dq.push_back(원소) : dq의 마지막 원소 뒤에 삽입

dq.pop_front() : dq의 첫번째 원소 제거

dq.pop_back() : dq의 마지막 원소 제거

dq.size() : dq의 크기를 참조

dq.empty() : dq가 비어있다면 true 비어있지 않다면 false

dq.clear() : dq의 모든 원소 제거

dq.begin() : dq의 첫번째 원소를 가리킨다.

dq.end() : dq의 마지막 원소를 가리킨다.

dq.insert(a, b) : a번째 위치에 b를 삽입한다.

 

Deque 예제

백준 Onlie Judge 10866번 덱

https://www.acmicpc.net/problem/10866

10866번: 덱

코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

/*


*/
int main() {
	int n, a;
	deque <int> dq;
	string str;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str;
		if (str == "push_front") {
			cin >> a;
			dq.push_front(a);
		}
		else if (str == "push_back") {
			cin >> a;
			dq.push_back(a);
		}
		else if (str == "front") {
			if (dq.empty()) {
				cout << -1 << endl;
			}
			else {
				cout << dq.front() << endl;
			}		
		}
		else if (str == "back") {
			if (dq.empty()) {
				cout << -1 << endl;
			}
			else {
				cout << dq.back() << endl;
			}
		}
		else if (str == "empty") {
			if (dq.empty()) {
				cout << 1 << endl;
			}
			else {
				cout << 0 << endl;
			}
		}
		else if (str == "size") {
			cout << dq.size() << endl;
		}
		else if (str == "pop_front") {
			if (dq.empty()) {
				cout << -1 << endl;
			}
			else {
				cout << dq.front() << endl;
				dq.pop_front();
			}
		}
		else if (str == "pop_back") {
			if (dq.empty()) {
				cout << -1 << endl;
			}
			else {
				cout << dq.back() << endl;
				dq.pop_back();
			}
		}
		
	}
}