[바킹독 알고리즘] 0x07강:Deque

덱 Deque : 양쪽 끝에서 삽입과 삭제 모두 가능

성질

1. 원소의 추가,제거 O(1)

2. 제일 앞/뒤 원소 확인 O(1)

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

구현

덱의 Head와 Tail의 초기값이 MX인 이유는 헤드와 테일에서 모두 삽입삭제가 가능하기 때문이다.

위 이미지와같이 삽입/삭제가 일어나기 때문에 H가 0 일경우 더이상 왼쪽으로 삽입 할 수 없어서 MX로 잡아둔다. (선형으로 구현)

#include <iostream>
using namespace std;

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

void push_front(int x)
{
	dat[--head] = x; //앞에다 삽입하는거는 head++가 아님을 명심
}

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

void pop_front() {
	head++;
}

void pop_back() {
	tail--;  //뒤에있는 값을 pop할때는 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() {
	test();
}

STL deque

vector와 비슷한 모양새를 갖고 있다. 인덱스로 원소를 접근 할 수 있고, push_back 등의 메서드를 제공한다.

하지만 벡터에서는 불가능한 push_front()도 있다는 점이 차이이다.

더 낫다고 생각할 수 있으나 덱은 원소가 연속적으로 위치해있지 않는다.

=> 따라서 앞뒤로의 삽입/삭제가 필요한 경우에는 덱을 사용하나, front에서 삽입/삭제만 할 경우 vector를 사용하는게 더 낫다

문제현황

연습 문제  ✔	10866	덱	정답 코드
기본 문제  ✔	1021	회전하는 큐	정답 코드
응용 문제 ✔	5430	AC	정답 코드, 별해 1
응용 문제	11003	최솟값 찾기	정답 코드, 별해 1