---
# System prepended metadata

title: 【C++】競程筆記：Stack 考題總整理
tags: [資料結構, C++, 競程, CP]

---

# 【C++】競程筆記：Stack 考題總整理

[TOC]

Stack in STL：

- 先引入標頭檔 `<stack>`。
- 建立一個堆疊：`stack <T> st;`。T 為資料型態。
- 堆入堆疊：`st.push(123);`。根據當初宣告的資料型態丟入對應值。
- 存取堆疊頂端：`st.top();`。回傳堆疊頂端的值。
- 移除堆疊頂端的值：`st.pop();`。
- 檢查堆疊是否為空：`st.empty();`。
- 回傳堆疊大小：`st.size()`。

:::info
需要特別注意的點：每次要做 `pop()` 的時候，都要檢查 stack 是否為空，否則會 segmentation fault。
:::

## 1. 基礎操作

### 輔助堆疊：155. Min Stack

Problem Source：https://leetcode.com/problems/min-stack/description/

題目有個函式叫做 `getMin()`，除 `top()` 要回傳頂端值外， `getMin()` 也要回傳堆疊中的最小值。

解法：在現有堆疊 s 的基礎上再多加一個堆疊 ms，表示要存放最小值的堆疊。

在實作 `push(int val)` 時，先 push 進去 s，之後檢查 ms 是否為空，或是 `ms.top()` 頂端值比當前 val 還大，才將 val push 進去 ms。

實作 `pop()` 時，檢查 `s.top()` 是否跟 `ms.top()` 相等（檢查要丟掉的值是否為當前最小值），是的話就做 `ms.pop()`。

`getMin()` 直接回傳 `ms.top()` 即可。

Code：

```cpp=
class MinStack {
private:
    stack <int> s, ms;
public:
    MinStack() {
        
    }
    
    void push(int val) {
        s.push(val);
        if (ms.empty() || val <= ms.top()){ // <= 也要處理重複最小值
            ms.push(val);
        }
    }
    
    void pop() {
        if (s.top() == ms.top()){
            ms.pop();
        }
        s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return ms.top();
    }
};
```

### 844. Backspace String Compare

Problem Source：https://leetcode.com/problems/backspace-string-compare/

這題用字串模擬 stack 會更好，主要利用兩個操作：

- `s.push_back()`
- `s.pop_back()`

```cpp=
class Solution {
public:
    string build(string str){
        string result = "";
        for (char c : str){
            if (c != '#'){
                result.push_back(c);
            }
            else{
                if (!result.empty()){
                    result.pop_back();
                }
            }
        }
        return result;
    }
    bool backspaceCompare(string s, string t) {
        return build(s) == build(t);
    }
};
```

## 2. （經典必考題）符號配對與消除

只要一看到題目是有關「括號匹配」、「相鄰消除」的題目，一定要想到 Stack！！！
只要一看到題目是有關「括號匹配」、「相鄰消除」的題目，一定要想到 Stack！！！
只要一看到題目是有關「括號匹配」、「相鄰消除」的題目，一定要想到 Stack！！！

很重要所以說三次XD（老梗

主要的解題思路：

1. 遇到左括號或元素：放入 Stack。
2. 遇到右括號或相同元素：檢查 Stack 頂端是否匹配。若匹配則 `pop()`，不匹配則報錯或繼續堆疊。

### 20. Valid Parentheses

最經典的括號配對必考題。其他題你可以不刷，但這題必須刷起來。

Problem Source：https://leetcode.com/problems/valid-parentheses/description/

先碰左括號，將所有左括號 push 進去 stack。

之後要分別判斷三種右括號，但基本上模式都一樣，先看 stack 是不是空的，再來看頂端是否為相應的左括號。

Code：

```cpp=
class Solution {
public:
    bool isValid(string s) {
        stack <char> st;
        for (char c : s){
            if (c == '(' || c == '{' || c == '['){
                st.push(c);
            }
            else if (c == ')'){
                if (st.empty() || st.top() != '('){
                    return false;
                }
                st.pop();
            }
            else if (c == '}'){
                if (st.empty() || st.top() != '{'){
                    return false;
                }
                st.pop();
            }
            else if (c == ']'){
                if (st.empty() || st.top() != '['){
                    return false;
                }
                st.pop();
            }
        }
        return st.empty();
    }
};
```

### 1047. Remove All Adjacent Duplicates In String

Problem Source：https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/description/

這題屬於消除相鄰問題，若相鄰元素是相同的則消除。

解題思路是用字串當作 stack，程式中會用到的操作如下：

- `str.empty();`：檢查是否為空。
- `str.back();`：作用同 `st.top();`。
- `str.push_back(x);`：作用同 `st.push(x);`。
- `str.pop_back();`：作用同 `st.pop();`。

若遇到相同的元素，也就是當 `str.back() == c`，那麼就 `pop()`。

反之，遇到不同元素就直接 `push()` 即可。

Code：

```cpp=
class Solution {
public:
    string removeDuplicates(string s) {
        string result = "";
        for (char c : s){
            if (!result.empty() && result.back() == c){
                result.pop_back();
            }
            else{
                result.push_back(c);
            }
        }
        return result;
    }
};
```

## 3. 單調堆疊（Monotonic Stack）

當題目的問題是「右邊第一個比它大的數」或「左邊第一個比它小的數」時，就是單調堆疊了。

主要解題思路：保持 Stack 內的元素是遞增或遞減。當新 push 進去的元素破壞了這個順序，就找到了某個邊界或目標值。

### 739. Daily Temperatures

Problem Source：https://leetcode.com/problems/daily-temperatures/description/

這題被認為是練習單調堆疊的入門題。

題目給你一個陣列叫 temperatures，裡面放的是每天不同的溫度，然後求在第 i 天時，要幾天後天氣才會回溫？然後回傳一個 answer 陣列。

這題的 stack 要專門存放 index，因為題目問的是要等幾天，而不是什麼溫度之類的，所以這是一個計算距離的問題（`currIndex - prevIndex`）。

演算法流程主要跑一個 for loop，遍歷 temperatures，每次檢查 stack 是否不為空，並且今天的溫度大於 `Stack.top()`，如果成立就表示那天回溫了，然後就把那天 `pop()`、計算天數差、繼續檢查 stack 下個元素。

Code：

```cpp=
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();

        vector <int> ans(n, 0);

        stack <int> st;

        for (int i = 0; i < n; ++i){
            while (!st.empty() && temperatures[i] > temperatures[st.top()]){
                int prevIndex = st.top();
                st.pop();

                ans[prevIndex] = i - prevIndex;
            }
            st.push(i);
        }
        
        return ans;
    }
};
```

### 496. Next Greater Element I

Problem Source：https://leetcode.com/problems/next-greater-element-i/description/

這題也是單調堆疊的經典題。

題目給你兩個陣列 `num1` 跟 `num2`，`num1` 的元素會對應到 `num2`，對應完後，如果那個元素的下一個元素比他大，則回傳那個比他大的元素。~~這可能解釋的蠻爛的~~，沒關係，例子就在範例測資裡面。

`num1 = [4, 1, 2], num2 = [1, 3, 4, 2]`

首先從 4 開始，對應到 `num2[2]`，他的下一個元素是 2，沒有比他大，輸出 -1。

接下來是 1，很明顯 3 > 1，所以輸出 3。

最後是 2，而 2 沒有下一個元素，也輸出 -1。

最後得到輸出陣列 `[-1, 3, -1]`。

解題思路：

建立 `stack <int> stk` 跟 `unordered_map <int, int> nextGreater`。

`stk` 用來維護單調堆疊，在這題是單調遞減堆疊（從底部到頂部越來越小）。

`nextGreater` 用來快速建立一個查詢表，因為題目有兩個陣列，一個是專門拿來查詢的 `num1`，另一個是被查詢、拿來計算的 `num2`。

只要將有找到下個較大值的 `num`（`num1` 中的元素）紀錄在表中，之後透過 `nextGreater.count(num)` 查詢數量是否 >= 1，就可以表示有沒有該元素。

在維護單調堆疊的思路是：

- 遇到小的數：直接 `push`，因為沒遇到比它大的。
- 遇到大的數：新的數是 Stack 頂部那些小數的 Next Greater Element。
    - 把比目前這個數小的都 `pop`。
    - 最後再把這個新的大數 `push` 進去。

Code：

若有找到下一個較大值 $x_2$ ，則將較小的值 $x_1$ 映射到那個下一個較大值 $x_2$ 。以利後續查表使用。

```cpp=
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack <int> stk;
        unordered_map <int, int> nextGreater;
        for (int num : nums2){
            while (!stk.empty() && stk.top() <= num){
                int smallerVal = stk.top();
                stk.pop();
                nextGreater[smallerVal] = num;
            }
            stk.push(num);
        }
        vector <int> result;
        for (int num : nums1){
            result.push_back(nextGreater.count(num) ? nextGreater[num] : -1);
        }
        return result;
    }
};
```

### 503. Next Greater Element II

Problem Source：https://leetcode.com/problems/next-greater-element-ii/description/

是上一題的進階題，題目中從原本兩個陣列換成一個陣列，但這一個陣列是循環陣列，如 `[1, 2, 1]` 接下來會是 `[1, 2, 1, 1, 2, 1]` 結束。

遇到循環就要想到 `%` 運算子，透過 `nums[i % n]` 來存取這個循環陣列，也讓迴圈遍歷 $2 \times n$ 遍。

這邊堆疊改成堆入 index 的方式做。

Code：

`if (i < n) stk.push(i);` 只將前 n 個元素的 index 放進 stack，因為第二輪的目的是從剩下的元素找答案。

```cpp=
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        stack <int> stk;
        vector <int> result(n, -1);
        for (int i = 0; i < 2 * n; ++i){
            int num = nums[i % n];
            while (!stk.empty() && nums[stk.top()] < num){
                int index = stk.top();
                stk.pop();
                result[index] = num;
            }
            if (i < n) stk.push(i);
        }
        return result;
    }
};
```

## 4. 運算原理

### 150. Evaluate Reverse Polish Notation

Problem Source：https://leetcode.com/problems/evaluate-reverse-polish-notation/description/

Reverse Polish Notation（逆波蘭表示式），簡稱 RPN。一般人在寫運算式的時候，通常會用的叫做中綴表示式（Infix Notation），就是 $3 \times 3$ ，運算子會放在兩數之間。

但是對於電腦而言，中綴表示式是比較麻煩的事情。因為有**括號**和**運算優先級**（先乘除後加減）的問題。如 $(1 + 2) \times 3$ ，電腦必須先找到括號，算完裡面的，再算外面的。

RPN 就是要解決這個問題，讓電腦好運算。RPN 的寫法就是會將運算子放在後面：`3 3 +`，就是看到 `3` 跟另一個 `3`，最後有個 `+` 就知道要把它們加起來。

而 `(1 + 2) * 3` 會寫成 `1 2 + 3 *`，就是看到 1 跟 2，後面有個 `+`，將 1 跟 2 加起來，變成 3，變成 3 之後又遇到一個 3，後面有個 `*` ，最後把兩個 3 乘起來得到 9。

RPN 的優點就是不需要括號、不需要考慮優先級，由左讀到右，看到符號就計算，因此可用 stack 實作。

解題思路：

建立 `stack <int> stk`，遍歷 `tokens`，如果遇到數字，就直接 push 進去，然後記得 `stoi(s)` 轉成整數，反之，遇到運算子就做計算，做完之後再把它 push 回去。

在最後 `return stk.top()` 即可。

Code：

記得 stack 的先進後出（FILO）特性：

```cpp=
long long num2 = stk.top(); 
stk.pop();
long long num1 = stk.top();
stk.pop();
```

```cpp=
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack <int> stk;
        for (auto& s : tokens){
            if (s == "+" || s == "-" || s == "*" || s == "/"){
                long long num2 = stk.top(); 
                stk.pop();
                long long num1 = stk.top();
                stk.pop();

                if (s == "+") stk.push(num1 + num2);
                else if (s == "-") stk.push(num1 - num2);
                else if (s == "*") stk.push(num1 * num2);
                else if (s == "/") stk.push(num1 / num2);
            }
            else{
                stk.push(stoi(s));
            }
        }
        return stk.top();
    }
};
```

### 224. Basic Calculator

Problem Source：https://leetcode.com/problems/basic-calculator/description/

在不使用內建函式如 `eval()` （Python 的函式，可以計算字串中的運算式）的情況下，求加減、括號運算。

因為只有加減法，沒有乘除法優先級的問題，可把整個算式看成是一連串的數字加總。

比較難的地方在於**括號**跟**正負號**的問題。如 `1 - (2 + 3)`，2 + 3 的結果是正的，但括號前面有負號，所以又變成負的。

解題思路：

用兩個全域變數 `result` 跟 `sign`，分別表示計算結果跟正負符號的表示。

`sign = -1` 是負的，`sign = 1` 為正。（設成這樣是為了要讓計算結果正確）

接下來如果遇到數字，就根據 `sign` 去做運算：`result += sign * num`

若遇到 `+` 或 `-`，就更新 `sign` 變數。

遇到左括號 `(`，就先把目前的 `result` 跟 `sign` push 進去 stack，然後重置 `result = 0, sign = 1`。

遇到右括號 `)`，就表示括號裡面的算完了，而現在的 `result` 結果是括號內的計算結果，再從 stack 中取出先前存好的狀態，然後對 `result` 做相加。

Code：

以下這段是專門處理數字的部分，如果不加 while 迴圈，遇到 `s="1234+....."` 這個字串的話，會變成 `1 + 2 + 3 + 4`，而不是要專門拿來處理的 `1234` 這個數字。

最後 `i--` 是因為 while 迴圈的 `i++` 會停在運算子的位置，要把它移回來，好讓下一次 for 迴圈能判斷到。

```cpp=
if (isdigit(c)){
    long long num = 0;
    while (i < s.length() && isdigit(s[i])){
        num = num * 10 + (s[i] - '0');
        i++;
    }
    i--;
    result += num * sign;
}
```

```cpp=
class Solution {
public:
    int calculate(string s) {
        stack <int> stk;
        int result = 0, sign = 1;
        for (int i = 0; i < s.length(); ++i){
            char c = s[i];
            
            if (isdigit(c)){
                long long num = 0;
                while (i < s.length() && isdigit(s[i])){
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                i--;
                result += num * sign;
            }
            else if (c == '+'){
                sign = 1;
            }
            else if (c == '-'){
                sign = -1;
            }
            else if (c == '('){
                stk.push(result);
                stk.push(sign);
                
                result = 0;
                sign = 1;
            }
            else if (c == ')'){
                int prev_sign = stk.top(); stk.pop();
                int prev_result = stk.top(); stk.pop();
                result = prev_result + (result * prev_sign);
            }
        }
        return result;
    }
};
```