# 【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;
}
};
```
Sign in with Wallet
Connect another wallet