Deque

덱의 성질

1. 앞, 뒤에서 원소 추가/제거가 O(1)로 가능
2. 앞, 뒤의 원소 확인이 O(1)
3. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능
   그러나, C++ STL에서는 이를 지원

덱

덱은 제일 처음부터 앞, 뒤에서 추가와 제거가 가능합니다.
따라서, head와 tail의 초기값을 덱의 역할을 하는 dat배열의 중간 인덱스로 합니다.

덱 https://github.com/Geniemo/PracticalAlgo/blob/master/Deque.cpp

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

bool isEmpty() {
    return head == tail;
}

void test() {
    push_front(1);
    push_front(2);
    push_back(3);
    push_back(4);
    while (!isEmpty()) {
        cout << front() << " ";
        pop_front();
    }
    cout << "\n\n";
    
    push_front(1);
    push_front(2);
    push_back(3);
    push_back(4);
    while (!isEmpty()) {
        cout << back() << " ";
        pop_back();
    }
}

int main(void) {
    test();
    return 0;
}

활용 예제

백준 10866번 https://www.acmicpc.net/problem/10866

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

const int MX = 10005;
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];
}

bool isEmpty() {
    return head == tail;
}

int size() {
    return tail - head;
}

int N;
string command;
int item;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> command;
        if (command == "push_front") {
            cin >> item;
            push_front(item);
        }
        else if (command == "push_back") {
            cin >> item;
            push_back(item);
        }
        else if (command == "pop_front") {
            if (isEmpty()) {
                cout << -1 << "\n";
                continue;
            }
            cout << front() << "\n";
            pop_front();
        }
        else if (command == "pop_back") {
            if (isEmpty()) {
                cout << -1 << "\n";
                continue;
            }
            cout << back() << "\n";
            pop_back();
        }
        else if (command == "size") {
            cout << size() << "\n";
        }
        else if (command == "empty") {
            cout << isEmpty() << "\n";
        }
        else if (command == "front") {
            if (isEmpty()) {
                cout << -1 << "\n";
                continue;
            }
            cout << front() << "\n";
        }
        else if (command == "back") {
            if (isEmpty()) {
                cout << -1 << "\n";
                continue;
            }
            cout << back() << "\n";
        }
    }
    return 0;
}