Double Ended Queue
: 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조

덱의 성질

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제일 앞/뒤의 원소 확인이 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
5. STL deque에서는 인덱스로 원소에 접근 가능 (cf. STL stack, queue에서는 불가능)

덱의 구현

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];
}

STL deque

• vector와 비슷한데 front에서도 O(1) 만에 추가와 제거가 가능한 느낌
• deque은 원소들이 메모리 상에 연속하게 배치되어 있지는 않음
• 굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고 싶을 때는 vector를 쓸 것

#include <deque>

int main(void){
  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;
  cout << DQ.size() << '\n'; // 3
  if(DQ.empty()) cout << "DQ is empty\n";
  else cout << "DQ is not empty\n"; // DQ is not empty
  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의 모든 원소 제거
}

0-1 BFS 알고리즘

가중치가 0과 1로만 주어질 때 최단 경로를 찾을 수 있는 알고리즘
(다익스트라 대신)

• 가중치가 0인 노드를 큐의 맨앞에 추가 (push_front())
• 나머지는 큐의 맨뒤에 추가 (push_back())