Deque

Deque

정의와 성질

• 양쪽 끝에서 삽입과 삭제가 가능
• 원소 추가: O(1)
• 원소 제거: O(1);
• 제일 앞/뒤의 원소 확인: O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
• STL Deque에서는 인덱스로 원소 접근 가능

  구현

• 배열 혹은 연결리스트로 구현 가능
• 배열로 구현
• 그냥 구현을 하면 data를 삭제할 때 마다 앞에 쓸모없는 공간이 생김
• 원형 큐로 만들면 해결 가능

  #include<iostream>
  using namespace std;
  const int MX = 1000005;
  int dat[2*MX+1];
  int head=MX, tail=MX; // head는 가장 앞의 원소의 index, tail은 가장 뒤에 있는 원소의 index+1
  // 양쪽으로 확장하기 때문에 시작점을 중간으로
  void push_front(int x){
    dat[head-1]=x;
    head--;
  }
  void push_back(int x){
    dat[tail]=x;
    tail++;
  }
  void pop_front(){
    head++;
  }
  void pop_back(){
    tail--;
  }
  int front(){
    return dat[head];
  }
  int back(){
    return dat[tail-1];
  }
  void test(){
    push_back(10); // 10
    cout<<front()<<'\n'; // 10
    push_front(25); // 25 10
    push_back(12); // 25 10 12
    cout<<back()<<'\n'; // 12
  }
  int main(void){
    test();
    return 0;
  }
  

  STL Deque

  #include<iostream>
  #include<deque>
  using namespace std;
  int main(void){
    deque<int> DQ;
    DQ.push_front(10); // 10
    DQ.push_back(20); // 10 20
    cout<<DQ.size()<<'\n'; // 2
    for(auto x : DQ){
        cout<<x<<'\n';
    }
    DQ.pop_front(); // 20
    DQ.pop_back(); // 
    if(DQ.empty()){
        cout<<"Empty\n";
    }
    DQ.push_front(10); // 10
    DQ.push_back(20); // 10 20
    DQ[0]=3; // 3 20
    DQ.insert(DQ.begin()+1, 22); // 3 22 20
    DQ.erase(DQ.begin()+1); // 3 20
    for(auto x : DQ){
        cout<<x<<'\n';
    }
    return 0;
  }
  

  Tip

• vector와 달리 deque는 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않음.