[실전 알고리즘] 덱

정의와 성질

 

덱: 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조

Double Ended Queue.

덱의 성질

1. 원소의 추가와 제거가 모두 O(1)

2. 제일 앞/뒤의 원소 확인이 O(1)

3. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

 

 

기능과 구현

1. 배열로 구현

#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();
}

 

2. STL로 구현

- 벡터랑 비슷함

- 앞, 뒤에서 모두 추가 제거가 필요할 때 : 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의 모든 원소 제거
}

 

 

연습문제

10866번: 덱 (acmicpc.net)

 

 

 

- STL 사용

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  deque<int> DQ;
  int n;
  cin >> n;
  while (n--) {
    string q;
    cin >> q;
    if (q == "push_back") {
      int val;
      cin >> val;
      DQ.push_back(val);
    }
    else if (q == "push_front") {
      int val;
      cin >> val;
      DQ.push_front(val);
    }
    else if(q == "pop_front"){
      if(DQ.empty()) cout << -1 << '\n';
      else{
        cout << DQ.front() << '\n';
        DQ.pop_front();
      }
    }
    else if(q == "pop_back"){
      if(DQ.empty()) cout << -1 << '\n';
      else{
        cout << DQ.back() << '\n';
        DQ.pop_back();
      }
    }
    else if (q == "size")
      cout << DQ.size() << '\n';
    else if (q == "empty")
      cout << DQ.empty() << '\n';
    else if (q == "front") {
      if(DQ.empty()) cout << -1 << '\n';
      else cout << DQ.front() << '\n';
    }
    else { // back
      if(DQ.empty()) cout << -1 << '\n';
      else cout << DQ.back() << '\n';
    }
  }
}

 

- 직접 구현

#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];
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  while (n--) {
    string q;
    cin >> q;
    if (q == "push_back") {
      int val;
      cin >> val;
      push_back(val);
    }
    else if (q == "push_front") {
      int val;
      cin >> val;
      push_front(val);
    }
    else if(q == "pop_front"){
      if(tail==head) cout << -1 << '\n';
      else{
        cout << front() << '\n';
        pop_front();
      }
    }
    else if(q == "pop_back"){
      if(tail==head) cout << -1 << '\n';
      else{
        cout << back() << '\n';
        pop_back();
      }
    }
    else if (q == "size")
      cout << tail-head << '\n';    
    else if (q == "empty")
      cout << (tail==head) << '\n';
    else if (q == "front") {
      if(tail==head) cout << -1 << '\n';
      else cout << front() << '\n';      
    }
    else { // back
      if(tail==head) cout << -1 << '\n';
      else cout << back() << '\n';      
    }
  }
}

 

 

 

출처

BaaaaaaaarkingDog | [실전 알고리즘] 0x07강 - 덱 (encrypted.gg)