[실전 알고리즘] 0x07강 - 덱

1. 정의와 성질

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

덱은 Restricted Structure의 끝판왕과 같은 느낌의 자료구조인데, 양쪽 끝에서 삽입과 삭제가 전부 가능하다. 자료구조의 덱은 deque고 Double Ended Queue라는 뜻을 가진다. 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조로 스택과 큐를 덱의 특수한 경우이다.

덱의 성질

1. 원소의 추가 - O(1)

2. 원소의 제거 - O(1)

3. 제일 앞/뒤의 원소 확인 - O(1)

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

 

그리고 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다. STL stack, queue에서 불가능했던 것과는 차이가 있다.

---

2. 기능과 구현

덱도 배열이나 연결 리스트를 이용해서 구현 가능하다. 배열을 이용하는 게 더 쉽다. 배열로 구현 시 원소를 담은 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개가 필요하다. head와 tail을 각각의 변수라고 할 때 head는 가장 앞에 있는 원소의 인덱스이고 tail은 가장 뒤에 있는 원소의 인덱스 + 1이다. 여기서 큐와 다른 점은 head와 tail의 초기값이 0이 아니라 MX이고 배열의 크기는 2*MX + 1이다.

 

왜 저렇게 두는거냐면, 큐에서는 앞쪽에서는 제거만 발생하고 뒷쪽에서는 삽입만 발생하다보니 배열 내에서 실제 큐에 들어간 원소들이 차지하는 공간이 점점 오른쪽으로 이동하면서 확장하는 모양이었다.

 

하지만 덱에서는 양쪽에서 모두 삽입이 가능하기 때문에 양쪽으로 확장해야 한다. 만약 시작 지점을 0번지로 뒀을 경우 왼쪽으로는 확장을 할 수가 없게 되기 때문이다. 따라서 시작 지점을 배열의 중간으로 둬야 한다. 중간으로 두면 중앙에서 양쪽으로 확장이 가능하다. 그래서 배열의 크기는 2*MX+1이고 head와 tail의 초기값은 MX인 것이다.

 

 

전체 코드

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

 

---

3. STL stack

레퍼런스 링크

http://www.cplusplus.com/reference/deque/deque/

queue - C++ Reference

 

예제

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

STL deque은 매우 독특하게도 double ended queue라는 느낌보다는 vector랑 비슷한데 front에서도 O(1)에 추가와 제거가 가능한 느낌이 강하다. pop_front, push_front, pop_back, push_front 함수 뿐 아니라 이외에도 insert도 있고 erase도 있고 인덱스로 원소에 접근도 할 수 있다.

 

STL vector에서 제공되는 기능을 STL deque에서도 다 제공해주고 심지어 deque은 front에서도 O(1)에 추가와 제거가 가능하니 deque이 vector보다 상위호환이 아닌가 하는 생각이 들 수 있겠지만, vector와 달리 deque은 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않다. c++ deque vs vector와 같은 검색으로 찾아보기를 추천한다.

 

다만 앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요하면 당연히 STL deque을 사용하는게 효율적이지만 굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고싶을 땐 STL deque말고 STL vector를 쓰면 된다는 것만 잘 알고가자. 참고로 deque 레퍼런스 문서에도 4번째 문단에 "Both vectors and deques provide a very similar interface" 어쩌구저쩌구 하면서 관련 얘기가 나와있어서 한 번 읽어보시는 것도 좋습니다.

 

+) c++ deque vs vector

https://blog.naver.com/PostView.nhn?blogId=sssang97&logNo=221405464057&parentCategoryNo=&categoryNo=15&viewDate=&isShowPopularPosts=true&from=search 

[C++] vector와 deque

http://egloos.zum.com/sweeper/v/2817817

vector, deque, list 간단 비교 정리

https://imksh.com/13

[C++] vector가 꼭 정답일까? vector, deque, list 비교

---

4. 연습문제

BOJ 10866번: 덱

10866번: 덱

 

STL deque 이용

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, x;
    string s;
    deque<int> dq;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        if (s == "push_front")
        {
            cin >> x;
            dq.push_front(x);
        }
        else if (s == "push_back")
        {
            cin >> x;
            dq.push_back(x);
        }
        else if (s == "pop_front")
        {
            if (dq.empty())
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << dq.front() << "\n";
                dq.pop_front();
            }
        }
        else if (s == "pop_back")
        {
            if (dq.empty())
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << dq.back() << "\n";
                dq.pop_back();
            }
        }
        else if (s == "size")
        {
            cout << dq.size() << "\n";
        }
        else if (s == "empty")
        {
            if (dq.empty())
            {
                cout << 1 << "\n";
            }
            else
            {
                cout << 0 << "\n";
            }
        }
        else if (s == "front")
        {
            if (dq.empty())
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << dq.front() << "\n";
            }
        }
        else if (s == "back")
        {
            if (dq.empty())
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << dq.back() << "\n";
            }
        }
    }

    return 0;
}

STL 이용 X

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

int dq[2 * MX + 1];
int head = MX, tail = MX;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, x;
    string s;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        if (s == "push_front")
        {
            cin >> x;
            dq[--head] = x;
        }
        else if (s == "push_back")
        {
            cin >> x;
            dq[tail++] = x;
        }
        else if (s == "pop_front")
        {
            if (tail - head <= 0)
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << dq[head++] << "\n";
            }
        }
        else if (s == "pop_back")
        {
            if (tail - head <= 0)
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << dq[--tail] << "\n";
            }
        }
        else if (s == "size")
        {
            cout << tail - head << "\n";
        }
        else if (s == "empty")
        {
            if (tail - head <= 0)
            {
                cout << 1 << "\n";
            }
            else
            {
                cout << 0 << "\n";
            }
        }
        else if (s == "front")
        {
            if (tail - head <= 0)
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << dq[head] << "\n";
            }
        }
        else if (s == "back")
        {
            if (tail - head <= 0)
            {
                cout << -1 << "\n";
            }
            else
            {
                cout << dq[tail - 1] << "\n";
            }
        }
    }

    return 0;
}

 

---

참고자료

[실전 알고리즘] 0x07강 - 덱

[실전 알고리즘] 0x07강 - 덱