[바킹독의 실전 알고리즘] 0x07강 - 덱

1. 정의와 성질

 

정의

 

양쪽 끝에서만 삽입과 삭제가 전부 가능한 자료구조. Restricted Structure의 끝판왕!

 

*참고로 스택과 큐를 덱의 특수한 예시라고 생각해도 무관함.

 

성질

 

1) 원소 추가 시간복잡도 O(1)2) 원소 제거 시간복잡도 O(1)3) 제일 앞/뒤의 원소 확인이 O(1)4) 제일 앞/뒤가 아닌 나머지 원소들의 확인 및 변경이 원칙적으로 불가능....하지만! STL deque는 stack, queue와 달리 인덱스로 특정 원소로 접근할 수 있음. 구체적인 활용 사례는 마지막에서 볼 수 있겠지만, stack과 queue에서는 구현을 하지 않았던 것을 생각하면 꽤 독특한 일:)

 

2. 기능과 구현

 

직접 구현

 

덱도 역시 배열 혹은 연결 리스트 둘 다를 가지고 구현할 수 있지만 배열을 통해 구현하는 것이 더 쉽기 때문에 배열로 구현할 예정!

 

필요한 변수는 원소를 담은 배열 dat[2*MX+1], 초기값이 MX로 설정된 head와 tail임. 이때, head는 가장 앞에 있는 원소의 인덱스이고 tail은 가장 뒤에 있는 원소의 인덱스+1임!!

 

head와 tail 초기값이 왜 갑자기 MX로 설정이 되었냐면, 덱의 경우 중앙에서 시작해 양옆으로 쭉쭉 확장하는 꼴이기 때문에, 총 배열의 길이를 2*MX+1로 설정하고 중앙값인 MX를 시작 지점으로 잡았음.

 

물론 덱도 원형으로 구현을 할 수 있지만 배열을 크게 잡으면 되므로 선형으로 구현함.

 

❓ pop_front()나 pop_back()에서 나는 head와 tail이 서로 교차되는 순간이 발생하지 않을 때 head++을 해줘야 하지 않냐고 생각했는데.. 그런 예외사항은 생각하지 않는걸까..?

#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; //한 칸 앞으로 가서 추가해줘야 하므로 --head
}

void push_back(int x){
  dat[tail++] = x;//추가를 해준 뒤에 이동해야하므로 tail++
}

void pop_front(){
  head++; //나는 head와 tail이 서로 교차되는 순간이 발생하지 않을 때 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();
}

 

3. STL deque

 

STL deque는 vector와 느낌이 비슷함. 그 이유는 물론 덱에서 쓰는 push_front(), push_back(), pop_front(), pop_back() 함수들은 당연히 있지만, 아래 코드에서 보듯이 insert 함수도 있고 erase 함수도 있으며, 인덱스로 원소에 접근을 할 수가 있어 vector와 느낌이 비슷함.

 

하지만 vector와 다르게 deque은 메모리 상에 연속하게 배치되어있지 않다는 점에서 차이가 있음. 그래서 어떤 경우에 무엇을 써야하냐라고 묻는다면

 

🎃 앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요하면 당연히 deque / 그렇지 않고 배열과 같은 느낌으로 사용하고 싶을 때 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의 모든 원소 제거
}

 

📌 deque 참고 자료

https://cplusplus.com/reference/deque/deque/