## 定義
通常討論時會唸英文，但硬要說中文就是佇列
在線性資料結構中滿足 FIFO(First In First Out)，也就是先進先出(亦後進後出)
如果用比喻來說，最常見的例子就是火車過山洞，車頭先進山洞也先出，車尾後進山洞也後出
佇列通常會使用幾個基本的功能：push()、pop()、front()、empty()、size()
* push() : 將資料推入 queue 的最後端
* pop() : 將 queue 最前端的資料取出(刪除)
* front() : 回傳 queue 最前端的資料
* empty() : 回傳 queue 是否為空
* size() : 回傳 queue 的大小

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

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

int Q[100] ; // queue 大小最多為 100
int f = 0, r = 0 ; // f 目前最前端的位置, r 目前最尾端的位置

void push(int data) {
    if ((r+1)%100 != f) {
        Q[r] = data ;
        r = (r+1) % 100 ;
    }
    else
        cout << "The queue is already full." ; // 裝滿的 queue 沒辦法 push
    return ;
}

void pop() {
    if (f != r) {
        Q[f] = 0 ;
        f = (f+1) % 100 ;
    }
    else
        cout << "The queue is already empty." ; // 空 queue 沒辦法 pop
    return ;
}

int bfront() {
    if (f != r)
        return Q[f] ;
    cout << "The queue is already empty." ; // 空 queue 沒辦法 front
    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 筆資料需要傳入 queue
    for (int i=0;i<n;i++) {
        cin >> data ;
        push(data) ;
    }

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

---

以下是 Linked List 實作的方式

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

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

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

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

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

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

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

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

    // 初始化
    Node *head = new Node ;
    head->data = -1 ;
    head->prev = head->next = head ;

    // 最尾端
    Node *curr = head ;

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

    curr = head->prev ;
    while (!bempty(curr)) { // 取出並輸出 queue 資料直到 queue 為空
        data = bfront(curr) ;
        curr = pop(curr) ;
        cout << data << ' ' ;
    }
    return 0 ;
}

## STL queue 使用方法
其實最主要的還是競賽時的使用，通常都是使用 STL 內建的 queue 來操作，以下是實際用法範例

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

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

    queue<int> que ; // 宣告一個儲存 int 的 queue

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

    while (!que.empty()) { // 同 while (que.size() > 0)
        cout << que.front() << ' ' ; // 輸出 top
        que.pop() ;                 // 取出
    }

    return 0 ;
}

## 例題-ZJ e447. queue 練習
[題目連結](https://zerojudge.tw/ShowProblem?problemid=e447)
解題思路 :
主要是幫助各位練習 STL 裡面的 queue 怎麼使用

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

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

    int n ;
    cin >> n ;

    queue<int> que ;
    for (int i=0, k;i<n;i++) {
        cin >> k ;
        if (k == 1) { // 推入 k
            cin >> k ;
            que.push(k) ;
        }
        else if (k == 2) {
            if (que.empty()) // 沒元素輸出 -1
                cout << "-1\n" ;
            else              // 輸出最頂端
                cout << que.front() << '\n' ;
        }
        else {
            if (!que.empty()) // 有元素才可刪除
                que.pop() ;
        }
    }



    return 0 ;
}

## 例題-ZJ e155. 10935 - Throwing cards away I
[題目連結](https://zerojudge.tw/ShowProblem?problemid=e155)
解題思路 :
題目說只要兩張牌以上，就要丟掉最上方的牌，次高的牌放到牌堆最下方，直接模擬出來就好

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

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

    int n ;
    while (cin >> n && n) {
        cout << "Discarded cards: " ;
        queue<int> que ;
        for (int i=1;i<=n;i++)
            que.push(i) ;
        while (que.size() > 1) { // 至少兩張才能開始丟
            cout << que.front() ;
            que.pop() ; // 最上方的丟掉
            que.push(que.front()) ; // 次上方的保留放到最後
            que.pop() ;
            if (que.size() > 1) // 只要兩張以上就還能丟棄
                cout << ", " ;
            else break ; // 剩下一張所以無法丟棄
        }
        cout << "\nRemaining card: " << que.front() << '\n' ;
    }


    return 0 ;
}

## 例題-ZJ e564. 00540 - Team Queue
[題目連結](https://zerojudge.tw/ShowProblem?problemid=e564)
解題思路 :
這題比較複雜，我們先把結構拆開來說，Team Queue 其實就是 queue 裡面放 queue
所以在 push 元素的時候，要判斷有沒有同 team 的成員在 Team queue 裡面
如果有就將該元素放在同 team 的成員後方，其實 team 在 Team queue 裡就是 queue
只要找到有同成員的 queue，就將元素 push 進這個 queue 中
至於 pop 元素的部分，因為整個 team queue 是由很多 queue 組成的
所以會從最前方的 queue 取值，如果最前方的 queue 取完值後是空的，那這個 queue 也要被 pop
不過這種模擬實作起來會有點麻煩，所以我們把 Team queue 拆成兩個部分
1. Team queue 有哪些 team (需要照順序儲存，所以用 queue)
2. 在 Team queue 裡的 team 有哪些成員目前在 Team queue 中

這樣我們在 push 的時候，判斷有沒有同 team 的成員，只要看 2. 就行
pop 的時候也可以先從 1. 知道最前方的 team，然候從 2. 取出值，再判斷 team 成員是不是都跑了
(注意這裡因為有多組測資，所以結構用完後需要清除裡面的資料)

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

int t, n, x, k = 0 ;
int id[1000005] ;       // id[a] = b, 數字 a 在隊伍 b
queue<int> team[1005] ; // team[a] = {b} 隊伍 a 有 b 在 queue 中
queue<int> que ;        // que 不同隊伍在 queue 中的順序

int main() {
    ios::sync_with_stdio(0), cin.tie(0) ;
    while (cin >> t && t) {
        cout << "Scenario #" << ++k << '\n' ;
        for (int i=1;i<=t;i++) {
            cin >> n ;
            for (int j=0;j<n;j++) {
                cin >> x ;
                id[x] = i ; // 數字 x 在隊伍 b
            }
        }
        string s ;
        while (cin >> s && s != "STOP") { // 輸入直到 STOP
            if (s == "ENQUEUE") { // push
                cin >> x ;
                if (team[id[x]].empty()) // 沒有同隊伍的在 queue 中
                    que.push(id[x]) ;       // 放到最後端
                team[id[x]].push(x) ;       // 放到同隊伍中
            }
            else {
                int now = que.front() ; // 最前方的 team
                cout << team[now].front() << '\n' ;
                team[now].pop() ;
                if (team[now].empty()) que.pop() ; // 全部都出去、queue 已無該隊伍
            }
        }
        cout << '\n' ;
        while (!que.empty()) { // 清除資料
            int now = que.front() ;
            while (!team[now].empty()) team[now].pop() ;
            que.pop() ;
        }
    }

    return 0 ;
}

## 特殊概念-用兩個 stack 模擬 queue
其實兩個 stack 能夠模擬出 queue 的功能，因為 stack1 將所有資料到另一個 stack2
最上方的元素就是變到最下方，所以原本最先進入 stack1 的資料就可以最先出去，也就是 queue
不過如果要把資料 push 進去，要先把 stack2 的資料先丟回 stack1，不然順序會出問題

#include<bits/stdc++.h>
using namespace std ;
typedef stack<int> STK ;

STK stk1, stk2 ;
void bpush(int data) {
    while (!stk2.empty()) {
        stk1.push(stk2.top()) ;
        stk2.pop() ;
    }
    stk1.push(data) ;
    return ;
}

void btop_and_pop() {
    while (!stk1.empty()) {
        stk2.push(stk1.top()) ;
        stk1.pop() ;
    }
    cout << stk2.top() << '\n' ;
    stk2.pop() ;

    return ;
}

int main() {
    // 測試資料
    bpush(1) ;
    bpush(2) ;
    bpush(3) ;
    btop_and_pop() ;
    bpush(4) ;
    bpush(5) ;
    btop_and_pop() ;
    bpush(6) ;
    btop_and_pop() ;
    btop_and_pop() ;
    btop_and_pop() ;
    btop_and_pop() ;
    btop_and_pop() ;

    return 0 ;
}

其實還有其他方式，只要可以做出 queue 就可以了

## 總結
之後還有其他演算法會用到 queue，這裡只是拿一些簡單的例題讓各位更了解 queue
唯一比較難的就是 Team queue 那題，因為模擬的複雜度比較高，但其實就是類二維 queue