Restricted Structure_Deque(덱)

 

Deque 이란?

Restricted sturcture의 끝판왕인 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하다.

Deque 성질

• 원소의 추가 O(1)
• 원소의 제거 O(1)
• 최상단의 원소 확인 O(1)
• 최상단의 원소를 제외한 나머지 원소들은 확인 및 변경은 원칙적으로 불가능 하지만 STL을 통해 인덱스에 접근이 가능하다.

---

Deque 구현 

덱의 구현 방법에는 배열을 사용하여 구현하는 방법과 STL을 사용하는 방법이 있다.

배열을 사용한 구현

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

void push_front(int x){
    dat[head]=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];
}

• dat[2*MX+1] : head와 tail의 초기값 설정을 위해 크기를 저렇게 설정
• head, tail : 덱의 가장 앞/뒤 값. 덱은 큐와 다르게 양쪽에서 삽입/삭제가 가능해서 0번지를 초기값으로 잡게 될 경우, 삽입 삭제에 문제가 생기게 된다. 이 때문에 head,tail값을 배열의 중간값으로 설정해야한다. tail은 큐와 동일하게 맨 뒤 인덱스의 다음 위치를 가르킨다.

---

STL을 사용한 구현

#include <deque> 헤더파일을 포함해야 한다.

#include <iostream>
#include <deque>
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
  
  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덱은 인덱스의 중간값에 접근이 가능하다. 사용법을 보면 que보다는 오히려 벡터에 가까운 모습임을 알 수 있다. 벡터와 다르게 덱은 원소들이 메모리 상에 떨어진 상태로 배치되어있다.

 

 

 

출처:https://www.youtube.com/watch?v=0mEzJ4S1d8o&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=8