코테를 위한 알고리즘

덱(deque)

claire 2022. 1. 14. 14:54

덱은 Restricted Structure의 끝판왕 같은 느낌의 자료구조이다. 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 참고로 자료구조의 덱은 deque이고 Double Ended Queue라는 뜻을 가지고 있다. 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조이니 스택과 큐를 덱의 특수한 예시라고 생각해도 좋다. 

 

덱의 성질 

  1. 원소의 추가가 O(1)
  2. 원소의 제거가 O(1)
  3.  제일 앞/뒤의 원소 확인이 O(1)
  4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

STL deque에서는 인덱스로 원소에 접근할 수 있다. STL stack, queue에서 불가능했던 것을 생각하면 꽤 독특한 일이다. 

덱도 스택이나 큐처럼 배열 혹은 연결 리스트 둘 다를 가지고 구현할 수 있지만 배열을 이용하는 게 더 구현이 쉽기 때문에 배열을 이용한 구현을 다뤄보겠다. 

 

배열로 deque 구현

 

일단 필요한 변수는 큐랑 똑같이 원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가르키는 변수 두 개다. 이때 head와 tail을 두는 방식도 큐와 같다. head는 가장 앞에 있는 원소의 인덱스이고 tail은 가장 뒤에 있는 원소의 인덱스 +1이다. 그리고 head와 tail의 초기값이 0이 아니라 mx이다. 

큐에서는 앞쪽에서만 제거를 하고 뒤쪽에서는 삽입만 하다보니 배열 내에서 실제 큐에 들어간 원소들이 차지하는 공간이 점점 오른쪽으로 이동하면서 확장하는 모습이었다. 하지만 덱에서는 양쪽에서 모두 삽입이 가능하기 때문에 양쪽으로 확장해야 한다. 이때 별생각 없이 시작 지점을 0번지로 뒀을 경우 왼쪽으로는 확장이 불가능하다. 따라서 시작 지점을 배열의 중간으로 둬야 한다. 중간으로 두면 중앙에서 양쪽으로 확장이 가능하다. 그래서 배열의 크기는 2*mx+1이고 head와 tail의 초기값은 mx인 것이다. 

덱도 원형으로 구현할 수 있지만 코테에서는 배열을 충분히 크게 잡으면 되니까 그냥 선형으로 구현을 하겠다. 우리가 구현해야 할 함수는 push_front, push_back, pop_front, pop_back, front, back 함수이다. 

#include <bits/stdc++.h>
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();
}

 

STL deque

STL에 덱이 있어서 그냥 가져다 쓰면 되는데 STL deque는 매우 독특하게 double ended queue라는 느낌보다는 vector랑 비슷한데 front에서도 O(1)에 원소의 추가와 제거가 가능한 느낌이 강하다. pop_front, push_front, pop_back, push_back 함수는 당연히 덱이니 있어야 정상이지만 이외에도 insert와 erase가 있고 인덱스로 원소에 접근이 가능하기도 하다. 이와 같이 STL vector에서 제공되는 기능을 STL deque에서도 다 제공해주고 심지어 deque는 front에서도 O(1)에 추가와 제거가 가능하니 deque가 vector보다 상위 호환이 아닐까 하는 생각이 들 수도 있지만, vector와 달리 deque는 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않다. vector의 경우 공간이 부족하면 memory reallocate 과정을 거쳐야 하는데 deque의 경우 연속되지 않으니, 그냥 새로운 memory block을 하나 할당하면 되니 평균적인 성능을 보장한다. 이 둘의 차이점은 따로 공부해서 기록하도록 하겠다. 참고 : http://www.cplusplus.com/reference/deque/deque

 

알아가야 할 것은 앞쪽과 뒤쪽에서의 추가와 제거가 모두 필요하면 당연히 STL deque를 사용하는 게 효율적이지만 굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고 싶을 땐 STL deque 말고 STL vector를 쓰면 된다. 

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