정의와 성질

양쪽 끝에서 삽입 삭제 전부 가능한 자료구조이다. 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은 모든 원소들이 메모리상에 연속 배치되어 있지 않다(벡터는 연속 배치)

coding