【C++】競程筆記（資料結構：Stack、Queue）
===
[TOC]
程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。
資料結構
---
這啥？就是：
> 在電腦科學中，資料結構（data structure）是電腦中儲存、組織資料的方式。
> From：Wikipedia
資料結構有兩種操作：
1. 修改操作
2. 查詢操作
修改就是可以在一個資料結構，像是陣列裡面新增或移除值。
查詢就是可以存取一個資料結構的元素，如 `a[0]`。
常見的資料結構有 stack（堆疊）、queue（佇列）、array（陣列）、vector（C++ STL 的動態陣列）、linked-list（鏈結串列）等等。
vector 的部分可以參照我先前寫的：https://hackmd.io/@LukeTseng/H1ZqX9RHkl
### 迭代器（iterator）
---
> 迭代器就是一個能枚舉資料結構的資料的物件。
然後迭代器跟指標很像，但實際上不太一樣，他是一種設計模式，用來逐個存取容器（如 array、set等）內的元素，而不需要顯示容器的內部結構。
用一句話概括就是：迭代器是一種提供通用介面來遍歷容器中元素的物件。
以下程式碼會印出 a 的每一項：
```cpp=
// 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 的每一項：
```cpp=
// 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 庫：
```cpp=
#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：
```cpp=
// 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 習題
---
1. Uva673：https://zerojudge.tw/ShowProblem?problemid=b304
原文 pdf：https://onlinejudge.org/external/6/673.pdf
```cpp=
#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;
}
```
2. 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 寫出的佇列程式碼：
```cpp=
#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 程式碼：
```cpp=
// 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;
}
}
```
環狀佇列：
```cpp=
// 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 習題
---
1. 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' 的話，則此行不應進行處理。
輸出說明：
對於輸入中的每個數字，請輸出兩行結果。第一行顯示被丟棄的牌的序列，第二行則顯示最後剩下的牌。每一行的開頭與結尾都不應有空格。參見範例以了解所受預期的格式。
範例輸入：
```
7
19
10
6
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
```
程式碼：
```cpp=
#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;
}
```
2. Uva 540：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=481
zerojudge：https://zerojudge.tw/ShowProblem?problemid=e564
```cpp=
#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 吧！這一次，需要支援四個操作：
1. POP_FRONT 和 POP_BACK，分別代表要從前面和後面拿出東西出來並輸出拿出來的東西的值，如果沒有東西可以拿的話，那就輸出 empty!。
2. PUSH_FRONT $x$ 和 PUSH_BACK $x$ ，分別代表要從前面和後面插入一個值為 $x$ 的物體。並且保證總共不會超過 $N$ 個操作。
:::spoiler 條件限制
* $N \leq 10^{5}$
:::
```cpp=
// 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;
}
}
```
上述這些函數，在 C++ 中 STL 也可做到。
使用前需要引入標頭檔 `#include <deque>`，建立 deque 方式與前面建立 queue 相同。
基本操作如下：
* push_back()：將資料堆入雙端佇列尾端。
* push_front()：將資料堆入雙端佇列前端。
* pop_back()：移除雙端佇列最後一個元素。
* pop_front()：移除雙端佇列最前面的元素。
* insert()：插入元素於雙端佇列中。
* erase()：移除某個位置的元素，也可移除某一段範圍的元素。
* clear()：清空容器裡所有元素。
* empty()：回傳雙端佇列是否為空。
* size()：回傳雙端佇列目前的長度。
* front()：存取並回傳雙端佇列最前面的元素。
* back()：存取並回傳雙端佇列尾端的元素。
Sign in with Wallet
Connect another wallet