덱

stl vector에서 제공해주는 기능을 stl deque에서도 대부분 제공 +push_front
앞쪽에서의 추가 제거가 필요하지 않으면 굳이 deque 쓸 필요 없음

배열로 구현하는 덱 

#include <iostream>


using namespace std;

const int MX = 1000005; 
int dat[2 * MX + 1];
int head = MX, tail = MX; 
// 앞으로도 뒤로도 확장 가능해야 하기 때문에 인덱스의 초기값을 중간으로 세팅함
// head 는 맨 앞의 원소를 가리키고 tail은 맨 뒤의 원소 하나 뒤를 가리킴

void push_front(int x) {
	// 아니 암만 정신 없을 때 풀었어도 그렇지 이게 뭐니 
	// dat[head--];
	dat[--head] = x;
}

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

void pop_front() {
	// 이거 할 필요 없대 if (head < 2 * MX + 1) 
	head++;
}

void pop_back() {
	// 마찬가지 if (tail > 2 * MX + 1) 
	tail--;
}

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

int back() {
	return dat[tail-1];
	// tail은 마지막 원소 +1 을 가리키니까 -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();
}