[자료구조/선형구조] 덱

Deque (Double Ended Queue)

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

덱의 성질

1. 원소의 추가 → O(1)
2. 원소의 제거 → O(1)
3. 제일 앞/뒤의 원소 확인 → O(1)
4. 제알 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

구현

const int MX = 1000005;
int dat[2*MX+1]; //앞뒤로 다 삽입이 가능해서 양쪽으로 확장하기 때문에 배열의 크기는 2*MX+1
int head=MX, tail=MX;