[바킹독] Deque 정리

바킹독 덱 정리

덱은 Restricted Structure의 끝판왕과 같은 느낌의 자료구조인데, 양쪽 끝에서 삽입과 삭제가 전부 가능합니다. 참고로 자료구조의 덱은 deque고 Double Ended Queue라는 뜻을 가지고 있습니다. 우리가 하스스톤이나 유희왕에서 얘기하는 덱은 Deck라서 발음은 둘 다 덱으로 똑같긴 해도 다른 단어입니다.

 

아무튼 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조이니 스택과 큐를 덱의 특수한 예시라고 생각해도 괜찮겠습니다.

 

-바킹독-

덱에서도 삽입, 삭제, 제일 앞/뒤 원소의 확인이 다 O(1)입니다. 그리고 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있습니다. STL stack, queue에서 불가능했던걸 생각하면 꽤 독특한 일입니다.

-바킹독-

...(중략) 하지만 덱에서는 양쪽에서 모두 삽입이 가능합니다. 그렇기 때문에 마치 여의봉처럼 양쪽으로 확장해야 합니다. 그러면 별 생각 없이 시작 지점이 0번지로 뒀을 경우 왼쪽으로 확장을 할 수가 없게 됩니다. 대신에 시작 지점을 배열의 중간으로 둬야 합니다. 중간으로 두면 중앙에서 양쪽으로 확장이 가능합니다. 그래서 배열의 크기는 2*MX+1이고 head와 tail의 초기값은 MX인 것입니다.

-바킹독-

 

직접 덱 구현해보기!

#include <iostream>

using namespace std;

const int MX = 1000005;
int dat[2 * MX + 1];
int head = MX, tail = MX;

void push_front(int x) {
	dat[--head] = x;
}

void push_back(int x) {
	dat[tail++] = x;
	
}

void pop_front() {
	head++;
}

void pop_back() {
	tail--;
}

int front() {
	return dat[head];
}

int back() {
	return dat[tail-1];
}

void test() {

}

int main(void) {
	test();
}

 

[Deque STL 사용하기]

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

int main(void) {
	deque<int> DQ;
	DQ.push_front(10);
	DQ.push_back(50); // 10 50
	DQ.push_front(24); // 24 10 50
	for (auto x : DQ) cout << x;
	cout << DQ.size() << '\n'; // 3
	if (DQ.empty()) cout << "DQ is empty\n";
	else cout << "DQ is not empty\n";
	DQ.pop_front(); // 10 50
	DQ.pop_back(); // 10
	cout << DQ.back() << '\n'; // 10
	DQ.push_back(72); // 10 72
	cout << DQ.front() << '\n'; // 10
	DQ.push_back(12); // 10 72 12
	DQ[2] = 17; // 10 72 17
	DQ.insert(DQ.begin() + 1, 33); // 10 33 72 17
	DQ.insert(DQ.begin() + 4, 60); // 10 33 72 17 60
	for (auto x : DQ) cout << x << ' ';
	cout << '\n';
	DQ.erase(DQ.begin() + 3); // 10 33 72 60
	cout << DQ[3] << '\n'; // 60
	DQ.clear(); // DQ의 모든 원소 제거
	return 0;
}

 

물론 STL에 덱이 있어서 그냥 가져다쓰면 되는데, STL deque은 매우 독특하게도 double ended queue라는 느낌보다는 vector랑 비슷한데 front에서도 O(1)에 추가와 제거가 가능한 느낌이 강합니다. pop_front, push_front, pop_back, push_front 함수야 당연히 덱이니 있어야 정상인데, 이외에도 19-25번째 줄을 보면 insert도 있고 erase도 있고 인덱스로 원소에 접근도 할 수 있습니다.

이와 같이 STL vector에서 제공되는 기능을 STL deque에서도 다 제공해주고 심지어 deque은 front에서도 O(1)에 추가와 제거가 가능하니 deque이 vector보다 상위호환이 아닌가 하는 생각이 들 수 있겠지만, vector와 달리 deque은 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않습니다. 구조에 대해 자세히 설명을 드리고 싶지만 강의의 난이도를 많이 벗어나는 내용인 것 같아서 궁금하시다면 스스로 c++ deque vs vector와 같은 검색으로 찾아보시면 되겠습니다.

 

다만 어떤 것 하나만 알고 가시면 되냐면, 앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요하면 당연히 STL deque을 사용하는게 효율적이지만 굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고싶을 땐 STL deque말고 STL vector를 쓰면 됩니다. 참고로 deque 레퍼런스 문서에도 4번째 문단에 "Both vectors and deques provide a very similar interface" 어쩌구저쩌구 하면서 관련 얘기가 나와있어서 한 번 읽어보시는 것도 좋습니다.(레퍼런스 링크, 예제 링크) - 링크는 바킹독님 블로그 가서....!

-바킹독-

 

BOJ 문제 풀기 10866 덱

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

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	deque<int> DQ;
	int n;
	cin >> n;
	while (n--) {
		string q;
		cin >> q;
		if (q == "push_back") {
			int val;
			cin >> val;
			DQ.push_back(val);
		}
		else if (q == "push_front") {
			int val;
			cin >> val;
			DQ.push_front(val);
		}
		else if (q == "pop_front") {
			if (DQ.empty())
				cout << -1 << '\n';
			else {
				cout << DQ.front() << '\n';
				DQ.pop_front();
			}
		}
		else if (q == "pop_back") {
			if (DQ.empty())
				cout << -1 << '\n';
			else {
				cout << DQ.back() << '\n';
				DQ.pop_back();
			}
		}

		else if (q == "size")
			cout << DQ.size() << '\n';
		else if (q == "empty")
			cout << DQ.empty() << '\n';
		else if (q == "front") {
			if (DQ.empty())
				cout << -1 << '\n';
			else
				cout << DQ.front() << '\n';
		}
		else{ // back
			if (DQ.empty())
				cout << -1 << '\n';
			else
				cout << DQ.back() << '\n';
		
		}
	}
}

 

출처) 바킹독 블로그 https://blog.encrypted.gg/935

[실전 알고리즘] 0x07강 - 덱