정의
양쪽 끝에서 삽입과 삭제가 전부 가능하다.
성질
- 원소의 추가/제거 : O(1)
- 제일 앞/뒤의 원소 확인 : O(1)
- 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하지만 STL deque에서는 인덱스로 내부 원소에 접근하는 기능을 제공한다.
구현
배열을 이용하여 덱을 직접 구현해보자.
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; }
int pop_front() { head++; }
void pop_back() { tail--; }
int front() { return dat[head]; }
int back() { return dat[tail - 1]; }
// 배열 속 원소들을 가리키며 이동하면서 데이터를 변경/삭제하지 않고도 해당 기능을 구현할 수 있다.- 큐에서의 head, tail과 같은 기능을 한다.
- 큐와 다르게 양쪽에서 삽입/삭제가 가능하기 때문에 head와 tail을 배열의 중간으로 설정하고 배열의 크기를 홀수로 만들어 덱에서 양방향으로 확장 가능하게 한다.
STL deque
- STL vector가 제공하는 기능들과 겹친다.
- vector와 달리 deque은 모든 원소들이 메모상에 연속하게 배치되어 있지 않다.
- 앞쪽과 뒷쪽에서의 추가/제거 기능이 모두 필요하면 STL deque, 필요하지 않다면 STL vector를 사용하는 것이 효율적이다.
