[덱]

덱

• 스택과 큐는 모두 덱의 일부라고 할 수 있다.
• 덱에서는 양쪽 끝에서 삽입과 삭제 모두 가능하다.
• O(1) 시간에 양쪽끝에서 삽입 삭제가 가능하다.

---

배열로 구현한 덱

#include <iostream>

using namespace std;

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;
}

void pop_front(){
    head++;
}

void pop_back(){
    tail--;
}

int front(){
    return dat[head];
}

int back(){
    return dat[tail-1];
}

void test(){
  push_back(30); // 30
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 30
  push_front(25); // 25 30
  push_back(12); // 25 30 12
  cout << back() << '\n'; // 12
  push_back(62); // 25 30 12 62
  pop_front(); // 30 12 62
  cout << front() << '\n'; // 30
  pop_front(); // 12 62
  cout << back() << '\n'; // 62
}

int main(void){
  test();
}

• 배열로 구현한 스택에서는 앞쪽에서만 삽입 삭제가 일어난다. 또한 배열로 구현한 큐에서는 앞쪽에서만 삭제, 뒤쪽에서만 삽입이 일어난다.
• 따라서 배열의 크기를 2*MX+1로 두고, head와 tail의 시작 인덱스를 MX로 두어 양쪽에 나머지 배열의 크기를 MX로 둘 수 있다.

---

STL deque

#include <bits/stdc++.h>
using namespace std;

int main(void){
  deque<int> DQ;
  DQ.push_front(10); // 10
  DQ.push_back(50); // 10 50
  DQ.push_front(24); // 24 10 50
  for(auto x : DQ)cout<<x;
  cout << DQ.size() << '\n'; // 3
  if(DQ.empty()) cout << "DQ is empty\n";
  else cout << "DQ is not empty\n"; // DQ is not empty
  DQ.pop_front(); // 10 50
  DQ.pop_back(); // 10
  cout << DQ.back() << '\n'; // 10
  DQ.push_back(72); // 10 72
  cout << DQ.front() << '\n'; // 10
  DQ.push_back(12); // 10 72 12
  DQ[2] = 17; // 10 72 17
  DQ.insert(DQ.begin()+1, 33); // 10 33 72 17
  DQ.insert(DQ.begin()+4, 60); // 10 33 72 17 60
  for(auto x : DQ) cout << x << ' ';
  cout << '\n';
  DQ.erase(DQ.begin()+3); // 10 33 72 60
  cout << DQ[3] << '\n'; // 60
  DQ.clear(); // DQ의 모든 원소 제거
}

• STL deque는 원소들이 연속적으로 구현되어 있지 않다. 따라서 삽입 삭제가 O(1) 시간에 가능하다.
• STL vector는 원소들이 연속적으로 구현되어 있어, 삽입과 삭제에 O(1) 시간이 소모된다.
• 자료의 삽입 삭제가 잦은 상활이라면 STL deque를 이용하는 게 유리하다.
• STL deque는 insert(), erase() 함수가 구현되어 있어, 원칙적으로 불가능하지만 원하는 인덱스에 삽입, 삭제가 가능하다.