[알고리즘/C++] 덱(deque)

출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

- 덱(deque, double ended queue)

https://www.javatpoint.com/post/cpp-deque

  - 양 끝에서 삽입/삭제가 가능한 자료구조

- 덱의 성질
  - 원소의 추가, 제거, 맨 앞/뒤 원소 확인 시 O(1)
  - 맨 앞/뒤 원소 외의 자료구조 확인이 불가

- 덱의 구현
  - 배열을 이용한 구현

const int MAX = 100000;
int data[2 * MAX + 1];
int head = MAX, tail = MAX;
//큐는 한 쪽으로만 데이터가 추가하므로 인덱스가 증가하는 방향으로만 구현
//덱의 경우 양쪽으로 데이터가 이동하므로 크기를 2배로 하고, 인덱스 시작점을 배열 중앙에 설정

//데이터 추가
int push_front(int x){
  data[--head] = x;
}
int push_back(int x){
  data[tail++] = x;
}
//데이터 제거
int pop_front(){
  head++;
}
int pop_back(){
  tail--;
}
//데이터 확인
int front(){
  return data[head];
}
int back(){
  return data[tail-1];
}

  - STL deque를 이용한 구현 - 벡터와 유사하게 동작

//https://github.com/encrypted-def/basic-algo-lecture-metarial/blob/master/0x07/deque_example.cpp
#include <deque>

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