C++:: 덱

참고 내용

https://blog.encrypted.gg/935

정의와 성질

https://soft.plusblog.co.kr/24

덱(Deque, Double Ended Queue) :  양쪽 끝에서 삽입과 삭제 모두 가능

1. 원소 추가 / 제거 / 맨 앞, 뒤 원소 확인 O(1)

2. 맨 앞, 뒤가 아닌 나머지 원소들 확인/변경 원칙적으로 불가능

(STL deque에서는 인덱스 접근 가능)

구현

head : 맨 앞 원소를 가리킴 

tail : 맨 뒤 + 1 위치를 가리킴

const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;

 

1) push_front 함수

void push_front(int x){
  dat[--head] = x;
}

2) push_back 함수

void push_back(int x){
  dat[tail++] = x;
}

3) pop_front 함수

void pop_front(){
  head++;
}

4) pop_back 함수

void pop_back(){
  tail--;
}

5) front 함수

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

6) back 함수

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

STL예제

#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의 모든 원소 제거
}