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

0x00 정의와 성질\

정의

 

양쪽 끝에서 삽입과 삭제가 전부 가능하다. 덱은 deque고 Double Ended Queue라는 뜻이다.

 

 

 

 

성질

 

덱에서도 삽입, 삭제, 제일 앞/뒤 원소의 확인이 다 O(1).

 

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

 

 

 

 

 

 

 

 

0x01구현

 

1

2

 

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

 

일단 필요한 변수는 큐랑 똑같이 원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개이다. 이 때 head와 tail을 두는 방식도 큐와 똑같다. head는 가장 앞에 있는 원소의 인덱스이고 tail을 가장 뒤에 있는 원소의 인덱스 + 1이다.

 

그리고 head와 tail의 초기값이 0이 아니라 MX이다. 왜그러냐면 덱에서는 양쪽에서 모두 삽입이 가능하므로 1, 2 그림을 보면 마치 여의봉처럼 양쪽으로 확장해야 한다. 그래서 시작 지점을 0번지로 둘 경우 왼쪽으로 확장을 할 수가 없어, 시작 지점을 배열의 중간으로 둬야 양쪽으로 확장이 가능하다. 따라서 배열의 크기는 2*MX+1이고 head와 tail의 초기값음 MX이다.

 

아래 코드는 STL을 쓰지않고 덱을 구현해 본것이다.

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

 

 

 

 

 

 

 

0x02 STL deque

 

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

 

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

 

 

 

 

 

 

 

0x03 연습문제

BOJ 10866번:덱

 

#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 s;
        cin >> s;
        if( s == "push_front"){
            int val;
            cin >> val;
            DQ.push_front(val);
        }
        else if( s == "push_back"){
            int val;
            cin >> val;
            DQ.push_back(val);
        }
        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 == "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';
        }
        else if( s == "empty"){
            if(DQ.empty()) cout << 1 << '\n';
            else cout << 0 << '\n';
        }
        else cout << DQ.size() << '\n';
    }
}