자료구조 : 덱(deque)

 

1. 덱의 정의

덱(deque, double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다.

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.

양 끝에서만 데이터를 넣고 양 끝에서 뺄 수 있는 자료구조

 

2. 덱의 함수

push_front : 덱의 앞에 데이터를 넣음

push_back : 덱의 뒤에 데이터를 넣음

pop_front : 덱의 앞에서 데이터를 뺌

pop_back : 덱의 뒤에서 데이터를 뻼

front : 덱의 가장 앞에 있는 데이터

back : 덱의 가장 뒤에 있는 데이터

 

3.덱의 구현

스택과 큐를 합친것과 같음

 

4.덱 관련 문제 풀이

백준 10866번 덱 : https://www.acmicpc.net/problem/10866

덱을 구현하는 문제

 

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

deque<int> d;

int main(void) {
	int t;
	cin >> t;
	while (t--) {
		string cmd;
		cin >> cmd;
		if (cmd == "push_front") {
			int num;
			cin >> num;
			d.push_front(num);
		}
		else if (cmd == "push_back") {
			int num;
			cin >> num;
			d.push_back(num);
		}
		else if (cmd == "pop_front") {
			if (!d.empty()) {
				cout << d.front() << endl;
				d.pop_front();
			}
			else cout << "-1" << endl;
		}
		else if (cmd == "pop_back") {
			if (!d.empty()) {
				cout << d.back() << endl;
				d.pop_back();
			}
			else cout << "-1" << endl;
		}
		else if (cmd == "size") {
			cout << d.size() << endl;
		}
		else if (cmd == "empty") {
			cout << d.empty() << endl;
		}
		else if (cmd == "front") {
			cout << (d.empty() ? -1 : d.front()) << endl;
		}
		else if (cmd == "back") {
			cout << (d.empty() ? -1 : d.back()) << endl;
		}
	}
}