덱

덱, Deque

Double Ended Queue

양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조

 

덱의 성질

원소의 추가, 제거, 확인이 O(1)

제일 앞/뒤가 아닌 나머지 원소들의 확인과 변경이 원칙적으로 불가

단, STL deque에서는 인덱스로 원소에 접근 가능

 

구현

head는 앞쪽 포인터, tail은 뒤쪽 + 1 빈공간 포인터

덱은 가운데에서 앞/뒤로 모두 늘어나므로 크기를 2 * MX + 1로 지정하고 head와 tail의 초기값으로 MX를 넣어줘야 한다.

#include <bits/stdc++.h>
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() {
	push_back(30); // 30
	cout << front() << '\n'; // 30
	cout << back() << '\n'; // 30
	push_front(25); // 25 30
	push_back(12); // 25 30 12
	cout << back() << '\n'; // 12
	push_back(62); // 25 30 12 62
	pop_front(); // 30 12 62
	cout << front() << '\n'; // 30
	pop_front(); // 12 62
	cout << back() << '\n'; // 62
}

int main(void) {
	test();
}

덱의 크기는 tail - head로 계산

 

STL deque

#include <bits/stdc++.h>
using namespace std;

int main() {

	deque<int> DQ;

	DQ.push_front(10); // 10
	DQ.push_back(50); // 10, 50
	DQ.push_front(24); // 24, 10, 50

	for (auto x : DQ) cout << x << " "; // 24 10 50
	cout << "\n";

	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 << " "; // 10 33 72 17 60
	cout << "\n";

	DQ.erase(DQ.begin() + 3); // 10 33 72 60
	cout << DQ[3] << "\n"; // 60
	
	DQ.clear();

	return 0;

}

 

deque<int> DQ;

DQ.push_front(x);
DQ.push_back(x);
DQ.pop_front();
DQ.pop_back();

DQ.front();
DQ.back();

DQ.size();
DQ.empty();

for (auto x : DQ) cout << x << " ";

DQ[x] = y;

DQ.insert(DQ.begin() + x, y);
DQ.erase(DQ.begin() + x);

DQ.clear();

 

vector와 같은 연산을 모두 제공하고, push_front(), pop_front()가 O(1)이니까 vector 대신 써도 되지않나?

deque은 vector와 다르게 모든 원소들이 메모리 공간에 연속해있지않다.

앞에서 추가/제거할 일이 없고 배열처럼 사용하고 싶으면 vector를 쓴다.