## 定義
通常討論時會唸英文，但硬要說中文就是雙向佇列
在線性資料結構中，資料可以從任一端進入，也可以從任一端取出資料
基本上就是 stack 跟 queue 的結合，在功能上也可以取代它們兩個
雙向佇列通常會使用幾個基本的功能：push_front()、pop_front()、push_back()、pop_back()
還有 front()、back()、empty()、size()
* push_front() : 將資料推入 deque 的最前端
* pop_front() : 將 deque 最前端的資料取出(刪除)
* push_back() : 將資料推入 deque 的最後端
* pop_back() : 將 deque 最後端的資料取出(刪除)
* front() : 回傳 deque 最前端的資料
* back() : 回傳 deque 最後端的資料
* empty() : 回傳 deque 是否為空
* size() : 回傳 deque 的大小

## 實作
通常會有多個方法實作，不過競程的大部分題目只需要用到 STL 內建的 deque
實際競賽上不太會需要自己搓一個，所以這裡的做法參考就好，知道怎麼做就可以了
以下是陣列的做法，用比較偷懶的方式實作的

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

int D[100] ; // deque 大小最多為 100
int f = 0, r = 0 ; // f 目前最前端(左邊)的位置, r 目前最尾端(右邊)的位置

void bpush_front(int data) { // push_front() 為內建函式，故取他名迴避
    if ((r+1)%100 != f) {
        D[f] = data ;
        f = (f+99) % 100 ;
    }
    else
        cout << "The deque is already full." ; // 裝滿的 deque 沒辦法 push
    return ;
}

void bpush_back(int data) { // push_back() 為內建函式，故取他名迴避
    if ((r+1)%100 != f) {
        D[r] = data ;
        r = (r+1) % 100 ;
    }
    else
        cout << "The deque is already full." ; // 裝滿的 deque 沒辦法 push
    return ;
}

void bpop_front() { // pop_front() 為內建函式，故取他名迴避
    if (f != r) {
        D[f] = 0 ;
        f = (f+1) % 100 ;
    }
    else
        cout << "The deque is already empty." ; // 空 deque 沒辦法 pop
    return ;
}

void bpop_back() { // pop_back() 為內建函式，故取他名迴避
    if (f != r) {
        D[r] = 0 ;
        r = (r+99) % 100 ;
    }
    else
        cout << "The deque is already empty." ; // 空 deque 沒辦法 pop
    return ;
}

int bfront() {
    if (f != r)
        return D[(f+1)%100] ;
    cout << "The deque is already empty." ; // 空 deque 沒辦法 front
    return -1 ; // 回傳 -1 表示 error
}

int bback() {
    if (f != r)
        return D[(r+99)%100] ;
    cout << "The deque is already empty." ; // 空 deque 沒辦法 back
    return -1 ; // 回傳 -1 表示 error
}

bool bempty() { // empty() 為內建函式，故取他名迴避
    return f == r ;
}

int bsize() { // size() 為內建函式，故取他名迴避
    return (r-f+100)%100 ;
}

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

    int n, data ;
    cin >> n ; // 有 n 筆資料需要傳入 deque
    for (int i=0;i<n;i++) {
        cin >> data ;
        bpush_front(data) ;
        bpush_back(data) ;
    }

    while (!bempty()) { // 取出並輸出 deque 資料直到 deque 為空
        data = bfront() ;
        bpop_front() ;
        cout << data << ' ' ;
        data = bback() ;
        bpop_back() ;
        cout << data << ' ' ;
    }
    return 0 ;
}

---

以下是 Linked List 實作的方式

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

struct Node { // Linked List 的結構
    int data ;
    Node* next ;
    Node* prev ;
} ;

void bpush_front(Node* curr, int data) {
    Node* new_node = new Node ;
    new_node->data = data ;
    new_node->next = curr ;
    new_node->prev = curr->prev ;
    curr->prev->next = new_node ;
    curr->prev = new_node ;
    return ;
}

void bpush_back(Node* curr, int data) {
    Node* new_node = new Node ;
    new_node->data = data ;
    new_node->next = curr->next ;
    new_node->prev = curr ;
    curr->next->prev = new_node ;
    curr->next = new_node ;
    return ;
}

void bpop_front(Node* curr) {
    curr = curr->prev ;
    if (curr->data != -1) {
        Node* now = curr ;
        now->next->prev = now->prev ;
        now->prev->next = now->next ;
        delete now ;
    }
    else
        cout << "The deque is already empty." ; // 空 deque 沒辦法 pop
    return ;
}

void bpop_back(Node* curr) {
    curr = curr->next ;
    if (curr->data != -1) {
        Node* now = curr ;
        now->next->prev = now->prev ;
        now->prev->next = now->next ;
        delete now ;
    }
    else
        cout << "The deque is already empty." ; // 空 deque 沒辦法 pop
    return ;
}

int bfront(Node* curr) {
    curr = curr->prev ;
    if (curr->data != -1) // deque 非空
        return curr->data ;
    cout << "The deque is already empty." ; // 空 deque 沒辦法 front
    return -1 ; // 回傳 -1 表示 error
}

int bback(Node* curr) {
    curr = curr->next ;
    if (curr->data != -1) // deque 非空
        return curr->data ;
    cout << "The deque is already empty." ; // 空 deque 沒辦法 back
    return -1 ; // 回傳 -1 表示 error
}

int bsize(Node* curr) { // size() 為內建函式，故取他名迴避
    Node *now = curr->prev ;
    int len = 0 ;
    while (curr != now) {
        if (now->data != -1)
            len++ ;
        now = now->prev ;
    }
    return len ;
}

bool bempty(Node* curr) { // empty() 為內建函式，故取他名迴避
    return curr->prev->data == -1 ;
}


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

    // 初始化(next 向右、prev 向左)
    Node *head = new Node ; // 最右端
    Node *tail = new Node ; // 最左端
    head->data = -1 ;
    head->next = head->prev = tail ;
    tail->data = -1 ;
    tail->next = tail->prev = head ;

    int n, data ;
    cin >> n ; // 有 n 筆資料需要傳入 deque
    for (int i=0;i<n;i++) {
        cin >> data ;
        bpush_front(head, data) ;
        bpush_back(tail, data) ;
    }

    while (!bempty(head)) { // 取出並輸出 deque 資料直到 deque 為空
        data = bfront(head) ;
        bpop_front(head) ;
        cout << data << ' ' ;
        data = bback(tail) ;
        bpop_back(tail) ;
        cout << data << ' ' ;
    }
    return 0 ;
}

## STL deque

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

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

    deque<int> dq ; // 宣告一個儲存 int 的 deque

    int n, data ;
    cin >> n ;
    for (int i=0;i<n;i++) {
        cin >> data ;
        dq.push_front(data) ; // push data 進 dq
        dq.push_back(data) ; // push data 進 dq
    }

    while (!dq.empty()) { // 同 while (dq.size() > 0)
        cout << dq.front() << ' ' ; // 輸出 top
        dq.pop_front() ;            // 取出
        cout << dq.back() << ' ' ; // 輸出 top
        dq.pop_back() ;            // 取出
    }

    return 0 ;
}

## 總結
deque 可以同時做到 stack 跟 queue 的功能，但速度上會比較慢
之後在比較進階的演算法會用到 deque，但目前會用 STL 的 deque 就可以了