#5 코테준비 - 덱(Deque)

덱(Deque)

- 양쪽끝에서 삽입/삭제가 가능한 자료구조

- 큐,스택,덱을 합쳐서 Restricted Structure라고 부름.

- Deque / Double Ended Queue라는 뜻을 가지고 있다.

 

- 원소의 추가/제거 O(1)

- 제일 앞/뒤의 원소 확인이 O(1)

 

---

C++ STL - Deque

 

Deque의 문서를 보면 앞쪽에 원소를 추가/제거 할 수 있다는 것만 빼면 Vector와 상당히 유사한것을 알 수 있다.

자료구조의 Deque은 앞/뒤가 아니면 확인이 불가능하지만 STL의 Deque는 인덱스로도 접근이 가능하다.

 

C++ stl vector vs deque 를 검색하면 많은 글들이 나오니 차이점들은 나중에 파보기로 하고,

코테에서 Vector와 deque중에 어떤걸 쓸지 판단하는 기준은 '앞/뒤 전부 추가/제거가 필요할 때' Deque를 쓰면 된다고 한다.

stl의 Vector는 배열처럼 연속한 메모리 공간을 가지지만, deque는 연속된 메모리 공간을 가지지 않는다.

 

연속한 메모리 공간을 가지면 삽입/삭제할때 그만큼의 연속된 공간을 찾아서 할당해야 하기때문에 이점도 생각할 부분이다.

---

문제 풀어보기 - 10866번: 덱 (acmicpc.net)

10866번: 덱

 

 

이것도 스택/큐의 문제와 똑같이 명령어대로 실행시키면 되는 문제다.

stl의 deque를 사용했다.

 

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

int main(void) {

	ios::sync_with_stdio(0);
	cin.tie(0);


	deque<int> myDeque;

	int n = 0;

	cin >> n;

	while (n--)
	{
		string s;
		cin >> s;

		if (s == "push_front")
		{
			int temp = 0;
			cin >> temp;
			myDeque.push_front(temp);
		}
		else if (s == "push_back")
		{
			int temp = 0;
			cin >> temp;
			myDeque.push_back(temp);
		}
		else if (s == "pop_front")
		{
			if (myDeque.empty()) cout << -1 << '\n';
			else
			{
				cout << myDeque.front() << '\n';
				myDeque.pop_front();
			}
		}
		else if (s == "pop_back")
		{
			if (myDeque.empty()) cout << -1 << '\n';
			else
			{
				cout << myDeque.back() << '\n';
				myDeque.pop_back();
			}
		}
		else if (s == "size")
		{
			cout << myDeque.size() << '\n';
		}
		else if (s == "empty")
		{
			if (myDeque.empty()) cout << 1 << '\n';
			else cout << 0 << '\n';
		}
		else if (s == "front")
		{
			if (myDeque.empty()) cout << -1 << '\n';
			else cout << myDeque.front() << '\n';
		}
		else
		{
			if (myDeque.empty()) cout << -1 << '\n';
			else cout << myDeque.back() << '\n';
		}
	}

	return 0;

}