【C++】競程筆記（資料結構：Stack、Queue）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

資料結構

這啥？就是：

在電腦科學中，資料結構（data structure）是電腦中儲存、組織資料的方式。
From：Wikipedia

資料結構有兩種操作：

修改操作
查詢操作

修改就是可以在一個資料結構，像是陣列裡面新增或移除值。

查詢就是可以存取一個資料結構的元素，如 a[0]。

常見的資料結構有 stack（堆疊）、queue（佇列）、array（陣列）、vector（C++ STL 的動態陣列）、linked-list（鏈結串列）等等。

vector 的部分可以參照我先前寫的：https://hackmd.io/@LukeTseng/H1ZqX9RHkl

迭代器（iterator）

迭代器就是一個能枚舉資料結構的資料的物件。

然後迭代器跟指標很像，但實際上不太一樣，他是一種設計模式，用來逐個存取容器（如 array、set等）內的元素，而不需要顯示容器的內部結構。

用一句話概括就是：迭代器是一種提供通用介面來遍歷容器中元素的物件。

以下程式碼會印出 a 的每一項：

// from NTUCPC Guide
vector<int>::iterator p = a.begin();
while (p != a.end()) {
    cout << *p << endl;
    p = next(p);
}

a.begin() 是指向 a 這個 vector 的第一項，a.end() 為指向 a 這個 vector 的最後一項的下一項物件。

指向迭代器的下一項用：next()
上一項：prev()

以下程式碼也會印出 a 的每一項：

// from NTUCPC Guide
auto p = a.begin();
while (p != a.end()) {
    cout << *p << endl;
    p = p + 1;
}

有時候不太知道要定義成什麼樣的資料型態，所以會用到 auto 讓編譯器自動去判斷他的資料型態。

而這支程式碼將 p = next(p) 更換成 p = p + 1，原因為 vector 是跟 array 差不多的東西，都是在記憶體中的一個連續空間。同理，p = prev(p) 也可換成 p = p - 1。

堆疊（Stack）

Stack 是一種先進後出（FILO：First In Last Out）的資料結構。

可以想像他是一個垂直地板而立的桶子，然後已經滿了，我們要搜尋最底下的東西，勢必要將其上層的物品一個一個拿走，最終才能取得最底下的物品。

stack 練習：https://neoj.sprout.tw/problem/36/

可以直接使用 C++ 的 STL 庫：

#include <iostream>
#include <stack>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    stack <int> mystack;
    for (int i = 0;i < T;i++){
        int state = 0;
        int num = 0;
        cin >> state;
        if (state == 1){
            cin >> num;
            mystack.push(num);
        }
        else if (!mystack.empty()){
            cout << mystack.top() << "\n";
            mystack.pop();
        }
        else{
            cout << "empty!" << "\n";
        }
    }
    return 0;
}

使用前需要引入 <stack> 標頭檔。

push()、pop() 分別用於「將元素堆入堆疊內」、「移除堆疊頂端的元素」。

由於 pop() 是沒有回傳值的，所以可以先用 top() 取得頂端的值，再用 pop() 把它移除掉。

這邊有個細節，必須注意使用 pop() 時，要避免 stack 裡面是空的，否則會產生 undefined behavior。

筆者提供了 STL 的寫法，以下是 NTUCPC Guide 用基本的 array 實作 stack：

// from NTU CPC Guide
int Stack[maxn], tot = 0;
void PUSH(int x) {
    Stack[tot++] = x;
}
void POP(){
    if(tot == 0)
        cout << "stack is empty!\n";
    else
        cout << Stack[--tot] << endl;
}

以下是 stack STL 中基本操作：

push() 可以將資料放入堆疊的頂部；
pop() 將頂端元素刪除；
top() 查詢堆疊頂端元素；
size() 查詢目前還位於堆疊中的資料數；
empty() 回傳堆疊是否為空。

實際上 stack 在競賽中不會直接使用到其 STL，通常使用 vector 替代。

stack 習題

Uva673：https://zerojudge.tw/ShowProblem?problemid=b304

原文 pdf：https://onlinejudge.org/external/6/673.pdf

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    cin.ignore(); // 因為 cin 會讀到 "\n", 後面又有 getline 所以必須先清除 "\n"

    for (int i = 0; i < n; i++) {
        string s;
        getline(cin, s);

        stack<char> stk;
        bool isValid = true; // 判斷是否為有效的運算式

        for (char c : s) {
            if (c == '(' || c == '[') {
                stk.push(c);
            } else if (c == ')') {
                if (stk.empty() || stk.top() != '(') {
                    isValid = false;
                    break;
                } else {
                    stk.pop();
                }
            } else if (c == ']') {
                if (stk.empty() || stk.top() != '[') {
                    isValid = false;
                    break;
                } else {
                    stk.pop();
                }
            }
        }

        if (isValid && stk.empty()) {
            cout << "Yes" << "\n";
        } else {
            cout << "No" << "\n";
        }
        
    }

    return 0;
}

Rails：https://tioj.ck.tp.edu.tw/problems/1012

這題我真的看得不是很懂，就交給各位解題了XD。

佇列（Queue）

佇列又可稱為隊列，就像是一群人在排隊一樣，是一種先進先出（FIFO）的資料結構。

queue 的 push 跟 pop 操作如下：

push：從最後面加入某元素。
pop：從最前面刪除某元素。

queue 練習：https://neoj.sprout.tw/problem/37/

以下是筆者使用 C++ STL 寫出的佇列程式碼：

#include <iostream>
#include <queue>

using namespace std;

int main(){
    int T;
    cin >> T;
    queue <int> q;
    for (int i = 0;i < T;i++){
        int state, num;
        cin >> state;
        if (state == 1){
            cin >> num;
            q.push(num);
        }
        else if (!q.empty()){
            cout << q.front() << "\n";
            q.pop();
        }
        else{
            cout << "empty!";
        }
    }
    return 0;
}

q.push() - 堆入某元素於佇列尾端
q.pop() - 移除某元素於佇列頂端
q.front() - 回傳佇列頂端的值
q.back() - 回傳佇列尾端的值
q.size() - 回傳佇列長度
q.empty() - 檢查佇列是否為空

以下是 NTUCPC Guide 依照實作原理製作的 queue 程式碼：

// from NTUCPC Guide
int Queue[maxn], Front = 0, Back = 0;
void PUSH(int x) {
    Queue[Back++] = x;
}
void POP() {
    if (Front == Back)
        cout << "empty!\n";
    else {
        cout << Queue[Front++] << endl;
    }
}

環狀佇列：

// from NTUCPC Guide
int Queue[maxn], Front = 0, Back = 0;
void PUSH(int x) {
    Queue[Back] = x;
    if (++Back >= maxn) Back -= maxn;
}
void POP() {
    if (Front == Back)
        cout << "empty!\n";
    else {
        cout << Queue[Front] << endl;
        if (++Front >= maxn) Front -= maxn;
    }
}

queue 習題

Uva 10935：https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1876

zerojudge：https://zerojudge.tw/ShowProblem?problemid=e155

題目翻譯：

給定一副有序的牌組，共有 $n$ 張牌，牌面編號從 $1$ 到 $n$ ，其中編號 $1$ 的牌位於最上方，編號 $n$ 的牌位於最下方。

只要牌組中至少還有兩張牌，就執行以下操作：

將最上方的牌丟棄，然後把現在位於最上方的牌移到牌組的最下方。

你的任務是找出被丟棄的牌的順序，以及最後剩下的那張牌。

:::info
順便說一下英文文法XD，原文：

Your task is to find the sequence of discarded cards and the last, remaining card.

and the last 後面的逗號 , 代表同位語當作 and the last 名詞片語的補充說明。
:::

輸入說明：

每一行輸入（最後一行除外）包含一個數字 $n$ ≤ $50$ 。最後一行為 ‘0’ 的話，則此行不應進行處理。

輸出說明：

對於輸入中的每個數字，請輸出兩行結果。第一行顯示被丟棄的牌的序列，第二行則顯示最後剩下的牌。每一行的開頭與結尾都不應有空格。參見範例以了解所受預期的格式。

範例輸入：

範例輸出：

Discarded cards: 1, 3, 5, 7, 4, 2
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 8, 12, 16, 2, 10, 18, 14
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8
Remaining card: 4
Discarded cards: 1, 3, 5, 2, 6
Remaining card: 4

程式碼：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

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

    while (true) {
        int n;
        cin >> n;
        
        if (n == 0) break;

        queue<int> q;
        
        for (int i = 1; i <= n; ++i) {
            q.push(i);
        }

        vector<int> discarded;
        if (n > 1) {
            while (q.size() > 1) {
                // 把最上面的牌丟掉:
                discarded.push_back(q.front()); 
                q.pop();
                // 再把目前最上面的牌移到最後面
                int top = q.front();
                q.pop();
                q.push(top);
            }
        }

        cout << "Discarded cards:";
        if (!discarded.empty()) {
            cout << ' ';
            for (size_t i = 0; i < discarded.size(); ++i) {
                cout << discarded[i];
                if (i + 1 < discarded.size()) {
                    cout << ", ";
                }
            }
        }
        cout << "\n";

        cout << "Remaining card: " << q.front() << "\n";
    }

    return 0;
}

Uva 540：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=481

zerojudge：https://zerojudge.tw/ShowProblem?problemid=e564

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int scenario = 1;
    
    while (true) {
        
        int t;
        cin >> t;
        
        if (t == 0) break;
        
        unordered_map<int, int> elementToTeam;
        
        for (int i = 1; i <= t; ++i) {
            
            int n;
            cin >> n;
            
            for (int j = 0; j < n; ++j) {
                
                int x;
                cin >> x;
                elementToTeam[x] = i;
                
            }
        }
        
        cout << "Scenario #" << scenario << "\n";
        scenario++;
        
        unordered_map<int, queue<int>> teamQueues;
        queue<int> teamOrder;
        
        string command;
        
        while (cin >> command) {
            
            if (command == "STOP") break;
            
            if (command == "ENQUEUE") {
                
                int x;
                cin >> x;
                
                int team = elementToTeam[x];
                
                if (teamQueues[team].empty()) {
                    teamOrder.push(team);
                }
                
                teamQueues[team].push(x);
                
            } else if (command == "DEQUEUE") {
                
                int frontTeam = teamOrder.front();
                
                cout << teamQueues[frontTeam].front() << "\n";
                
                teamQueues[frontTeam].pop();
                
                if (teamQueues[frontTeam].empty()) {
                    teamOrder.pop();
                }
                
            }
        }
        
        cout << "\n";
    }
    return 0;
}

雙端佇列（Deque）

deque（double-ended queue）唸作 [dɛk]，並不唸作 [di:kju:]，因為會很容易跟 dequeue 搞混，dequeue 是指將元素從 queue 中移除，與雙端佇列的 deque 差多了。

deque 有點像是 stack 和 queue 的結合體，因為它可以從頭尾放入跟移除元素。

:::info
Deque 練習

來實作 Deque 吧！這一次，需要支援四個操作：

POP_FRONT 和 POP_BACK，分別代表要從前面和後面拿出東西出來並輸出拿出來的東西的值，如果沒有東西可以拿的話，那就輸出 empty!。
PUSH_FRONT $x$ 和 PUSH_BACK $x$ ，分別代表要從前面和後面插入一個值為 $x$ 的物體。並且保證總共不會超過 $N$ 個操作。

:::spoiler 條件限制

$N \leq 10^{5}$
:::

// from NTU CPC Guide
int deq[maxn], Front = 0, Back = 0;
void PUSH_FRONT(int x) {
    if (--Front < 0) Front += maxn;
    deq[Front] = x;
}
void PUSH_BACK(int x) {
    if (++Back >= maxn) Back -= maxn;
    deq[Back] = x;
}
void POP_FRONT(){
    if (Front == Back)
        cout << "empty!\n";
    else {
        if (++Front >= maxn) Front -= maxn;
        cout << deq[Front] << endl;
    }
}
void POP_BACK(){
    if (Front == Back)
        cout << "empty!\n";
    else {
        if (--Back < 0) Back += maxn;
        cout << deq[Back] << endl;
    }
}