[0x07] 덱

정의와 성질

정의 double-ended queue

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

성질

• 원소의 추가와 제거 : O(1)
• 제일 앞/뒤의 원소 확인 : O(1)
• 제일 앞/뒤이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
  • 인덱스로 원소 접근 가능

기능과 구현

const int MAX = 1e7;
int data[2*MAX + 1];
int head = MAX, tail = MAX; // 시작 지점을 배열의 중간으로 : 앞뒤로 확장
// head : 시작. tail : 다음에 들어갈 원소의 자리

void push_front(int x)  data[--head] = x;
void push_back(int x)   data[tail++] = x;
void pop_front() head++;
void pop_back()  tail--;
int front() return data[head];
int back() return data[tail-1];

STL deque

vector와 다르게 deque은 값이 연속적으로 배치되어 있지 않음

dq[idx] = val;
dq.insert(dq.begin() + idx, val);
dq.erase(dq.begin() + idx);