## 定義
通常討論時會唸英文，但硬要說中文就是堆疊，中國的網站應該會叫(堆)棧
在線性資料結構中滿足 LIFO(Last In First Out)，也就是後進先出(亦先進後出)
如果用比喻來說，最常見的例子就是疊盤子，如果每次放都是放最上面，拿也是拿最上面
那最早放的盤子一定是最晚拿出來了，越早放(越下面)就越晚拿出來，反之(越晚放)越早拿出來
堆疊通常會使用幾個基本的功能：push()、pop()、top()、empty()、size()
* push() : 將資料推入 stack 的最頂端
* pop() : 將 stack 最頂端的資料取出(刪除)
* top() : 回傳 stack 最頂端的資料
* empty() : 回傳 stack 是否為空
* size() : 回傳 stack 的大小

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

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

int S[100] ; // stack 大小最多為 100
int idx = 0 ; // 目前 top+1 的位置

void push(int data) {
    if (idx < 100)
        S[idx++] = data ;
    else
        cout << "The stack is already full." ; // 裝滿的 stack 沒辦法 push
    return ;
}

void pop() {
    if (idx)
        S[idx--] = 0 ;
    else
        cout << "The stack is already empty." ; // 空 stack 沒辦法 pop
    return ;
}

int top() {
    if (idx)
        return S[idx-1] ;
    cout << "The stack is already empty." ; // 空 stack 沒辦法 top
    return -1 ; // 回傳 -1 表示 error
}

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

int bsize() { // size() 為內建函式，故取他名迴避
    return idx ;
}

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

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

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

---

以下是 Linked List 實作的方式

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

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

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

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

int top(Node* curr) {
    if (curr->data != -1) { // 不是 head
        return curr->data ;
    }
    cout << "The stack is already empty." ; // 空 stack 沒辦法 top
    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->prev, len++ ;
    return len ;
}

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

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

    // 目前點
    Node *curr = head ;

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

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

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

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

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

    stack<int> stk ; // 宣告一個儲存 int 的 stack

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

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

    return 0 ;
}

## 例題-ZJ b923. stack 堆疊的模板題
[題目連結](https://zerojudge.tw/ShowProblem?problemid=b923)
題目解析 :
這題主要是為了讓你們熟悉 STL 裡面 stack 的用法

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

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

    int n ;
    cin >> n ;

    stack<int> stk ;
    for (int i=0, tmp;i<n;i++) {
        cin >> tmp ;
        if (tmp == 1) // 取出
            stk.pop() ;
        else if (tmp == 2) // 輸出最頂端
            cout << stk.top() << '\n' ;
        else {              // 放入
            cin >> tmp ;
            stk.push(tmp) ;
        }
    }

    return 0 ;
}

## 例題-ZJ b838. 104北二2.括號問題
[題目連結](https://zerojudge.tw/ShowProblem?problemid=b838)
解題思路 :
這題要輸入一個字串，裡面只有左括號或右括號，一個左括號需要配到一個右括號然後消除
持續消除直到全部括號都沒有了，消除的同時還要記錄有幾對括號，現在來看不正確的情況
1. "目前"左括號比右括號少
2. "最後"左括號比右括號多

如果用 stack 去儲存目前還沒被消除(沒有成對)的左括號，遇到右括號時就從 stack 拿出並消除
這樣重複操作就可以配對所有的括號，不過根據上面"不正確"的情況，我們需要注意幾個問題
若 stack 為空(目前左括號都成對了)，還找到右括號，就是第一個情況
若最後操作完發現 stack 非空(還有左括號沒成對)，就是第二個情況

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

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

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

        int ans = 0 ;
        stack<char> stk ;
        for (char &c: s) {
            if (c == '(')       // 多一個左括號
                stk.push('(') ;
            else {
                if (stk.empty()) { // 沒有左括號與右括號配對
                    ans = 0 ;
                    break ;
                }
                stk.pop() ; // 配對成功 -> 消除
                ans++ ;      // 配對成功組數+1
            }
        }
        if (!stk.empty()) // 還有左括號沒有被配對到
            ans = 0 ;
        cout << ans << '\n' ;
    }

    return 0 ;
}

不過這題其實可以用整數(不用 stack)處理，因為我們只需要知道"目前"和"最後"的左括號數量

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

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

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

        int ans = 0, cnt = 0 ;
        for (char &c: s) {
            if (c == '(')   // 多一個左括號
                cnt++ ;
            else {
                if (cnt == 0) { // 沒有左括號與右括號配對
                    ans = 0 ;
                    break ;
                }
                cnt-- ; // 配對成功 -> 消除
                ans++ ; // 配對成功組數+1
            }
        }
        if (cnt) // 還有左括號沒有被配對到
            ans = 0 ;
        cout << ans << '\n' ;
    }
    return 0 ;
}

## 例題-ZJ f698. 後序運算式求值
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f698)
解題思路 :
後序運算式是運算子放在運算元的後面，也就是說如果我遇到一個新運算子，需要先取出兩個運算子
計算完後再把運算元放回去，這樣將最晚輸入的兩個值取出，然後計算完再放進去，就是 stack
所以我們遇到運算元的時候先放到 stack 裡面，如果遇到一個運算子，先從 stack 取出兩個數字
注意這裡數字的前後關係，因為先拿出來的數字應該放在運算式的後方，後拿出來的數字放在前方
比如我先拿出 $6$，然後拿出 $3$，要做除法運算，那應該是 $6 \div 3 = 2$

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

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

    string str ;
    stack<int> stk ;
    while (cin >> str) {
        // 遇到運算子
        if (str == "+" || str == "-" || str == "*" || str == "/") {
            int b = stk.top() ; // 較後方的數字
            stk.pop() ;
            int a = stk.top() ; // 較前方的數字
            stk.pop() ;
            if (str == "+") stk.push(a + b) ;      // 相加
            else if (str == "-") stk.push(a - b) ; // 相減
            else if (str == "*") stk.push(a * b) ; // 相乘
            else if (str == "/") stk.push(a / b) ; // 相除
        }
        else // 遇到運算元
            stk.push(stoi(str)) ; // 將字串變數字後放入 stack
    }
    cout << stk.top() << "\n" ; // 輸出最後結果
    return 0 ;
}

## 例題-ZJ c123. 00514 - Rails
[題目連結](https://zerojudge.tw/ShowProblem?problemid=c123)
解題思路 :
這題簡單可以簡單理解成 A、B、中間車站 X 三個點，A 的車預設都是從左到右 $1,2,...$
先進入 X 的車會比較晚出來，或著說晚進入 X 的車會比較早出來，先進入 B 的車會在左邊
其實 X 就是 stack，接下來我們模擬一下測資，假設 B 需要為 $4,5,3,7,6,2,1$
我們先整理一下，A 應該是 $1,2,3,4,5,6,7$，這時候因為 B 最左邊(最先進去 B) 的是 $4$ 車
所以 A 的車應該要開 $1,2,3,4$ 進入 X，然後 $4$ 再從 X 進入 B
接著需要 $5$ 車，一樣 A 開 $5$ 進入 X，然後 $5$ 再從 X 進入 B
接著需要 $3$ 車，因為 X 車站最上方(可以最先開出去的)剛好是 $3$，所以直接開去 B
接著需要 $7$ 車，從 A 開 $6,7$ 進入 X，然後 $7$ 再從 X 進入 B
接著需要 $6$ 車，因為 X 車站最上方(可以最先開出去的)剛好是 $6$，所以直接開去 B
接著需要 $2$ 車，因為 X 車站最上方(可以最先開出去的)剛好是 $2$，所以直接開去 B
接著需要 $1$ 車，因為 X 車站最上方(可以最先開出去的)剛好是 $1$，所以直接開去 B

經過上面的模擬，你應該可以發現如果要將車開到 B 點，我們會有兩種方式
1. 從 A 開車，直到你所需的車被開到 X，然後再開到 B
2. 從 X 開車，只有 X 最上方的車能被開到 B

所以如果這兩種方式都沒有辦法開到所需的車，那就代表不可能開到你所需的車，就輸出 "No"
然後做一些小優化，因為 A 一開始只會是 $1,2,3,...$，所以可以用一個整數表示目前最左邊的車

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

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

    int n ;
    while (cin >> n && n) {
        while (true) {
            vector<int> num(n) ;
            cin >> num[0] ;
            if (!num[0]) break ;
            for (int i=1;i<n;i++)
                cin >> num[i] ;

            int idx, cnt = 1 ; // idx 是 num 的 index, cnt 目前 A 最左邊的車
            stack<int> stk ;
            for (idx=0;idx<n;idx++) {
                if (!stk.empty() && stk.top() == num[idx]) // 中間車站直接開到 B
                    stk.pop() ;
                else if (num[idx] >= cnt) { // 需要 num[idx] 號車
                    for (int j=cnt;j<num[idx];j++) // 要開車直到 num[idx] 到中間車站
                        stk.push(j) ;
                    cnt = num[idx]+1 ; // 更新 A 最左邊的車
                }
                else break ; // 兩種方式都不行
            }

            if (idx == n) // 全部車都開完了
                cout << "Yes\n" ;
            else            // 所需車開不了
                cout << "No\n" ;
        }
        cout << '\n' ;
    }
    return 0 ;
}

## stack 應用-括號配對進階
上面那個題目只有小括號，而實際上有小括號、中括號和大括號，以下是三種括號正確配對的程式碼

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

int main() {
//    ios::sync_with_stdio(0), cin.tie(0) ;
    string s ;
    cin >> s ;

    int ans = 0 ; // (): +1, []: +2, {}: +3
    stack<char> stk ;
    for (char &c: s) {
        if (c == '(')       // 多一個小括號
            stk.push('(') ;
        else if (c == '[')       // 多一個中括號
            stk.push('[') ;
        else if (c == '{')       // 多一個大括號
            stk.push('{') ;
        else {
            bool error = stk.empty() ;
            if (c == ')') {
                if (stk.top() == '(') {
                    stk.pop() ; // 配對成功 -> 消除
                    ans += 1 ;      // 配對成功+1
                }
                else error = true ;
            }
            else if (c == ']') {
                if (stk.top() == '[') {
                    stk.pop() ; // 配對成功 -> 消除
                    ans += 2 ;      // 配對成功+2
                }
                else error = true ;
            }
            else if (c == '}') {
                if (stk.top() == '{') {
                    stk.pop() ; // 配對成功 -> 消除
                    ans += 3 ;      // 配對成功+3
                }
                else error = true ;
            }
            if (error) break ;
        }
    }
    if (!stk.empty()) // 還有任一種左括號沒有被配對到
        ans = 0 ;

    cout << ans << '\n' ;
    return 0 ;
}

## stack 應用-模擬遞迴
stack 可以模擬遞迴，但大多數時候不需要用到 stack，這裡只是幫助各位更理解 stack
比如下方就是一個 $n$ 階乘的例子

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

int factorial(int n) {
    if (n == 0 || n == 1) return 1 ;

    stack<int> stk ;
    int ans = 1 ;
    stk.push(n) ;

    while (!stk.empty()) { // n * (n-1) * (n-2) * ...
        int now = stk.top() ;
        stk.pop() ;
        if (now == 1) // end cul
            continue ;

        ans *= now ; // ...(now+2)*(now+1) *= now
        stk.push(now-1) ; // now -> now-1
    }

    return ans ;
}

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

    int n ;
    cin >> n ;
    cout << "n! = " << factorial(n) << '\n' ;
    return 0 ;
}

從以上的例子可以看出只要將傳遞的參數放到 stk 中搭配 while 就可以實現遞迴
下方還有一個費氏數列的例子，可以看到一層遞迴中多個呼叫與記憶優化的操作

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

int fibonacci(int n) {
    if (n == 0 || n == 1) return n ;

    stack<int> stk ;
    vector<int> mp(n+1, 0) ; // memory
    stk.push(n) ;

    mp[0] = 0, mp[1] = 1 ;
    while (!stk.empty()) { // f(n) = f(n-1) + f(n-2) ;
        int now = stk.top() ;
        if (mp[now] != 0 || now <= 1) { // use memory
            stk.pop () ;
            continue ;
        }
        // f(n) after f(n-1) and f(n-2)
        if (mp[now-1] != 0 && mp[now-2] != 0 || now == 2) {
            mp[now] = mp[now-1] + mp[now-2] ;
            stk.pop() ;
        }
        else { // f(n-1), f(n-2)
            stk.push(now-1) ;
            stk.push(now-2) ;
        }
    }

    return mp[n] ;
}

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

    int n ;
    cin >> n ;
    cout << "f(" << n << ") = " << fibonacci(n) << '\n' ;
    return 0 ;
}

以上程式碼就可以看出，如果一層遞迴需要兩個以上的呼叫，一樣直接 push 進去 stack 就好
還有記憶優化就使用一個獨立的 array 去處理就好，而如果在同一層呼叫後還需要執行其他指令
在 stack 的概念中需要考慮 pop 的必要性，比如想要處理 $f(4)$，因為 $f(3)$ 還未知
所以在 push $3$ 進入 stack 的時候，不用先 pop $4$，因為在 $3$ 計算完被 pop 掉後
還需要重新回到 $4$ 去計算 $f(4)$，所以結論就是在計算之前不用 pop，計算完就 pop 掉

## stack 應用-逆波蘭表示法
定義為將運算子放到運算元之後的算術表達，基礎的四則運算，不需括號，也不需考慮加減乘除順序
最簡單的方式，就是用後序運算式求值，前面也說過辦法了，以下是比較廣泛的作法

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

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

    vector<string> post ;
    string str ;
    stack<int> stk ;
    while (cin >> str) {
        post.push_back(str) ;
        // 遇到運算子
        if (str == "+" || str == "-" || str == "*" || str == "/") {
            int b = stk.top() ; // 較後方的數字
            stk.pop() ;
            int a = stk.top() ; // 較前方的數字
            stk.pop() ;
            if (str == "+") stk.push(a + b) ;      // 相加
            else if (str == "-") stk.push(a - b) ; // 相減
            else if (str == "*") stk.push(a * b) ; // 相乘
            else if (str == "/") stk.push(a / b) ; // 相除
        }
        else // 遇到運算元
            stk.push(stoi(str)) ; // 將字串變數字後放入 stack
    }
    
    for (string &it: post)
        cout << it << ' ' ;
    cout << '\n' ;
    cout << stk.top() << '\n' ; // 輸出最後結果
    return 0 ;
}

接下來比較進階一點，就是要將一般的四則運算轉換成逆波蘭表示法
這裡最重要的點就是要區分運算子的優先級，一般的優先級為: 括號 $>$ 乘除 $>$ 加減
其實已經有一個完整的演算法可以提供給我們使用 Shunting-yard algorithm
先簡單說明這個演算法在只有加減乘除和括號的處理規則
1. 遇到數字(運算元)就直接輸出
2. 如果遇到運算子，需要考慮到優先級和上一個運算子的優先級
3. 若當前運算子比 stack top 優先級高或相同，將 stack top 輸出，將當前放入 stack
4. 重複 3. 直到優先級低或 stacl 為空，或是 stacl top 為左括號
5. 如果遇到左括號，直接放入 stack
6. 如果遇到右括號，重複輸出直到遇到左括號，然後左括號取出但不輸出
7. 若整個算式結束，將 stack 中的所有運算子依序輸出

其實理解起來不難，我舉個例子，假設算式最開始為 $1+3...$，後方是未知的算式
此時 $+$ 能直接用嗎，很明顯不行，假設是 $1+3*2$，這樣 $+$ 很明顯不能第一時間計算
但如果是 $1+3*2/3$ 呢，因為在掃到 $/$ 的時候，我們已經知道可以做 $3*2$ 了
所以同優先級與較高的優先級都可以處理，接著就是括號的概念，括號其實相當於另外一個算式
把左括號直接放入 stack，右括號重複處理直到左括號，就相當於獨立開一個算式，以下是程式碼

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

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

    vector<string> post ; // 逆波蘭表示法
    string s ;
    stack<char> stk ;

    map<char, int> mp ; // 優先級定義
    mp['*'] = 3 ;
    mp['/'] = 3 ;
    mp['+'] = 2 ;
    mp['-'] = 2 ;

    while (cin >> s) {
        if (s[0] == '(') // 遇到左括號
            stk.push('(') ;
        else if (s[0] == ')') { // 遇到右括號
            // 重複直到遇到左括號
            while (stk.top() != '(') {
                string tmp(1, stk.top()) ;
                post.push_back(tmp) ;
                stk.pop() ;
            }
            stk.pop() ;
        }
        else if (s[0]-'0' >= 0 && s[0]-'0' <= 9) { // 數字
            post.push_back(s) ;
        }
        else { // 加減乘除
            char now = s[0] ;
            // 重複直到空、左括號、優先級低
            while (!stk.empty() && stk.top() != '(' && mp[now] <= mp[stk.top()]) {
                string tmp(1, stk.top()) ;
                post.push_back(tmp) ;
                stk.pop() ;
            }
            stk.push(s[0]) ;
        }
    }
    // 剩餘的直接依序輸出
    while (!stk.empty()) {
        string tmp(1, stk.top()) ;
        post.push_back(tmp) ;
        stk.pop() ;
    }
    
    // show Reverse Polish Notation 
    for (string &it: post)
        cout << it << ' ' ;
    cout << '\n' ;

    return 0 ;
}

## 總結
之後還有其他演算法會用到 stack，這裡只是拿一些簡單的例題讓各位更了解 stack