Today I learned : 바킹독 덱
바킹독의 실전 알고리즘 : 덱
덱은 큐의 진화형. 양쪽으로 넣다 빼기 가능.
정의와 성질
양쪽 끝에서 삽입 삭제 전부 가능한 자료구조이다. Double Ended Queue라고 큐의 진화형 느낌이다.
큐의 성질
- 원소의 추가가 O(1)
- 원소의 제거가 O(1)
- 제일 앞/뒤 원소 확인이 O(1)
- 앞뒤 외의 원소들은 원칙적으로 확인/변경 불가능
다만 STL deque에서는 인덱스로 원소 접근이 가능하다.
기능과 구현
const int MX=100005;
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 덱은 아래 참고.
#include <bits/stdc++.h>
using namespace std;
int main(void){
deque<int> DQ;
DQ.push_front(10);
DQ.push_back(20);
DQ.size();
DQ.empty();
DQ.insert(DQ.begin()+1,33);
}
STL의 덱은 pop,push front, back 말고도 insert, erase도 가능하다. 원소 접근이 가능하다. vector와 비슷하게 느껴질 수 있으나 STL이 제공하는 Deque은 모든 원소들이 메모리상에 연속 배치되어 있지 않다(벡터는 연속 배치)