정의와 성질

덱은 Restricted Structure의 끝판왕과 같은 느낌의 자료구조. 양 끝에서 삽입과 삭제가 전부 가능하다.

스택과 큐와 마찬가지로 원소 추가/제거/앞뒤 원소 확인 모두 O(1).
그리고 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있다.

기능과 구현

여기서도 배열로 구현!
큐와 비슷하지만 차이점은 배열의 크기는 2MX+1,head와 tail의 초기값이 MX가 된다.



위 사진처럼 덱은 양 끝에 원소 삽입이 가능하다. 따라서 큐처럼 0에서 시작한다면 왼쪽에서 확장이 불가능해진다.
이를 해결하기 위해서는 시작 지점을 배열의 중간으로 두면 된다. 중앙에서 양쪽으로 확장이 가능해지므로, 배열의 크기는 2MX+1이고 head와 tail의 초기값은 MX가 된다.

push_front 함수

void push_front(int x){
	dat[--head]=x;
}

push_back 함수

void push_back(int x){
	dat[tail++]=x;
}

pop_front 함수

void pop_front(){
	head++;
}

pop_back 함수

void pop_back(){
	tail--;
}

front 함수

int front(){
	return dat[head];
}

back 함수

int back(){
	return dat[tail-1];
}

STL deque

STL deque은 독특하게도 STL vector와 유사하다. insert, erase 함수가 있어서 인덱스로 원소에 접근이 가능하다.
STL vector에서 제공되는 기능을 STL deque에서도 모두 제공하고, 심지어 deque은 front에서도 O(1)에 추가와 제거가 가능하니 deque이 vector보다 상위호환이 아닌가 하는 생각이 들 수 있겠지만, vector와 달리 deque은 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않다.
앞쪽과 뒷쪽에서의 추가/제거가 모두 필요하면 당연히 STL deque을 사용하는게 효율적이지만 굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고싶을 땐 STL vector를 쓰자.

연습문제

백준10866 덱

풀이

내 코드
<stl 풀이>

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    deque <int> dq;
    int N,x;
    string order;
    cin >> N;
    while(N--){
        cin >> order;
        if(order == "push_front"){
            cin >> x;
            dq.push_front(x);
        }
        else if(order == "push_back"){
            cin >> x;
            dq.push_back(x);
        }
        else if(order == "pop_front"){
            if(dq.empty()) cout << "-1\n";
            else {
                cout << dq.front() << "\n";
                dq.pop_front();
            }
        }
        else if(order == "pop_back"){
            if(dq.empty()) cout << "-1\n";
            else {
                cout << dq.back() << "\n";
                dq.pop_back();
            }
        }
        else if(order == "size"){
            cout << dq.size() <<"\n";
        } 
        else if(order == "empty") {
            cout << dq.empty() << "\n";
        }
        else if(order == "front"){
            if(dq.empty()) cout << "-1\n";
            else {
                cout << dq.front() << "\n";
            }
        }
        else {
            if(dq.empty()) cout << "-1\n";
            else {
                cout << dq.back()<< "\n";
            }
        }
    }

    return 0;
}

<구현 풀이>

#include <iostream>

using namespace std;

const int MX = 100001;
int dat[2*MX+1];

int head=MX;
int 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 empty(){
    if(tail==head) return 1;
    else return 0;
}

int main()
{
    int N,x;
    string order;
    cin >> N;
    while(N--){
        cin >> order;
        if(order == "push_front"){
            cin >> x;
            push_front(x);
        }
        else if(order == "push_back"){
            cin >> x;
            push_back(x);
        }
        else if(order == "pop_front"){
            if(tail-head == 0) cout << "-1\n";
            else {
                cout << front() << "\n";
                pop_front();
            }
        }
        else if(order == "pop_back"){
            if(tail-head == 0) cout << "-1\n";
            else {
                cout << back() << "\n";
                pop_back();
            }
        }
        else if(order == "size"){
            cout << tail-head <<"\n";
        } 
        else if(order == "empty") {
            cout << empty() << "\n";
        }
        else if(order == "front"){
            if(tail-head == 0) cout << "-1\n";
            else {
                cout <<front() << "\n";
            }
        }
        else {
            if(tail-head == 0) cout << "-1\n";
            else {
                cout <<back()<< "\n";
            }
        }
    }

    return 0;
}