棧（Stack）是一種基于先進(jìn)后出（Last In, First Out，LIFO）原則的數(shù)據(jù)結(jié)構(gòu)。棧具有兩個(gè)主要的操作：

1. 壓棧（Push）：將元素添加到棧的頂部。
2. 出棧（Pop）：從棧的頂部移除元素。

棧常常用于需要反轉(zhuǎn)操作順序的場(chǎng)景，或者在需要記錄操作歷史的情況下。在算法中，棧的應(yīng)用廣泛，以下是一些典型的棧算法：

1. 括號(hào)匹配問(wèn)題：使用棧來(lái)檢查表達(dá)式中的括號(hào)是否匹配，例如檢查 ()、[]、{} 是否正確嵌套。
2. 逆波蘭表達(dá)式求值：通過(guò)棧來(lái)實(shí)現(xiàn)對(duì)逆波蘭表達(dá)式的求值，其中操作數(shù)和操作符都存儲(chǔ)在棧中。
3. 函數(shù)調(diào)用棧：在編程語(yǔ)言中，函數(shù)調(diào)用時(shí)的執(zhí)行過(guò)程通常使用函數(shù)調(diào)用棧（Call Stack）來(lái)管理。
4. 深度優(yōu)先搜索（DFS）：在圖或樹(shù)的遍歷過(guò)程中，使用棧來(lái)實(shí)現(xiàn)深度優(yōu)先搜索。
5. 迭代法求解二叉樹(shù)的前序、中序、后序遍歷：通過(guò)棧來(lái)模擬遞歸過(guò)程，實(shí)現(xiàn)二叉樹(shù)的不同遍歷方式。
6. 表達(dá)式求值：將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后使用棧求解后綴表達(dá)式的值。
7. 迷宮求解：通過(guò)棧來(lái)記錄路徑，實(shí)現(xiàn)對(duì)迷宮的求解過(guò)程。

棧的特性使其在某些問(wèn)題場(chǎng)景中非常有效和方便。在算法設(shè)計(jì)和實(shí)現(xiàn)中，棧通常用于臨時(shí)存儲(chǔ)數(shù)據(jù)、回溯操作、深度優(yōu)先搜索等。

01.刪除字符串中的所有相鄰重復(fù)項(xiàng)

題目鏈接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/

給出由小寫(xiě)字母組成的字符串 S，重復(fù)項(xiàng)刪除操作會(huì)選擇兩個(gè)相鄰且相同的字母，并刪除它們。

在 S 上反復(fù)執(zhí)行重復(fù)項(xiàng)刪除操作，直到無(wú)法繼續(xù)刪除。

在完成所有重復(fù)項(xiàng)刪除操作后返回最終的字符串。答案保證唯一。

示例：

輸入："abbaca"
輸出："ca"
解釋：
例如，在 "abbaca" 中，我們可以刪除 "bb" 由于兩字母相鄰且相同，這是此時(shí)唯一可以執(zhí)行刪除操作的重復(fù)項(xiàng)。之后我們得到字符串 "aaca"，其中又只有 "aa" 可以執(zhí)行重復(fù)項(xiàng)刪除操作，所以最后的字符串為 "ca"。

提示：

1. 1 <= S.length <= 20000
2. S 僅由小寫(xiě)英文字母組成。

思路

這里使用棧的思想可以很好的解決這個(gè)問(wèn)題，我們每插入一個(gè)字符前進(jìn)行對(duì)比，如果棧頂存在該字符，則刪除棧頂字符且不插入，否則插入字符，最后留在棧中的字符就是需要返回的，考慮到字符順序的問(wèn)題，我們可以直接用字符串來(lái)直接模擬棧。

代碼

class Solution {
public:string removeDuplicates(string s) {string ret;for(int i=0;i<s.size();++i){if(ret.size()&&s[i]==ret.back()) ret.pop_back();else ret+=s[i];}return ret;}
};

02.比較含退格的字符串

題目鏈接：https://leetcode.cn/problems/backspace-string-compare/

給定 s 和 t 兩個(gè)字符串，當(dāng)它們分別被輸入到空白的文本編輯器后，如果兩者相等，返回 true 。# 代表退格字符。

**注意：**如果對(duì)空文本輸入退格字符，文本繼續(xù)為空。

示例 1：

輸入：s = "ab#c", t = "ad#c"
輸出：true
解釋：s 和 t 都會(huì)變成 "ac"。

示例 2：

輸入：s = "ab##", t = "c#d#"
輸出：true
解釋：s 和 t 都會(huì)變成 ""。

示例 3：

輸入：s = "a#c", t = "b"
輸出：false
解釋：s 會(huì)變成 "c"，但 t 仍然是 "b"。

提示：

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小寫(xiě)字母以及字符 '#'

思路

同樣我們使用棧的思想，分別使用兩個(gè)空字符串來(lái)模擬棧，遇到#字符就出棧，其他時(shí)候進(jìn)棧，最后比較兩個(gè)字符串即可。

代碼

class Solution {
public:bool backspaceCompare(string s, string t) {string s1,s2;for(int i=0;i<s.size();++i){if(s[i]=='#') {    if(s1.size()) s1.pop_back();}else s1+=s[i];}for(int i=0;i<t.size();++i){      if(t[i]=='#') {    if(s2.size()) s2.pop_back();}else s2+=t[i];}return s1==s2;}
};

03.基本計(jì)算器 II

題目鏈接：https://leetcode.cn/problems/basic-calculator-ii

給你一個(gè)字符串表達(dá)式 s ，請(qǐng)你實(shí)現(xiàn)一個(gè)基本計(jì)算器來(lái)計(jì)算并返回它的值。

整數(shù)除法僅保留整數(shù)部分。

你可以假設(shè)給定的表達(dá)式總是有效的。所有中間結(jié)果將在 [-231, 231 - 1] 的范圍內(nèi)。

**注意：**不允許使用任何將字符串作為數(shù)學(xué)表達(dá)式計(jì)算的內(nèi)置函數(shù)，比如 eval() 。

示例 1：

輸入：s = "3+2*2"
輸出：7

示例 2：

輸入：s = " 3/2 "
輸出：1

示例 3：

輸入：s = " 3+5 / 2 "
輸出：5

提示：

• 1 <= s.length <= 3 * 105
• s 由整數(shù)和算符 ('+', '-', '*', '/') 組成，中間由一些空格隔開(kāi)
• s 表示一個(gè) 有效表達(dá)式
• 表達(dá)式中的所有整數(shù)都是非負(fù)整數(shù)，且在范圍 [0, 231 - 1] 內(nèi)
• 題目數(shù)據(jù)保證答案是一個(gè) 32-bit 整數(shù)

思路

根據(jù)題目要求我們只需要考慮空格、數(shù)字和四個(gè)運(yùn)算符這幾種情況，我們可以使用一個(gè)數(shù)組來(lái)模擬棧插入每一個(gè)數(shù)，使用一個(gè)前綴字符來(lái)進(jìn)行運(yùn)算符的標(biāo)記，初始設(shè)為加，當(dāng)我們碰到加減都更新，碰到乘除就直接在棧頂計(jì)算，直至字符串結(jié)束，最后我們將棧中的數(shù)相加即可。

代碼

class Solution {
public:int calculate(string s) {vector<int> st;char op='+';int n=s.size(),i=0,ret=0;while(i<n){if(s[i]==' ') i++;else if(s[i]>='0'&&s[i]<='9'){int tmp=0;while(i<n&&s[i]>='0'&&s[i]<='9') tmp=tmp*10+(s[i++]-'0');if(op=='+') st.push_back(tmp);else if(op=='-') st.push_back(-tmp);else if(op=='*') st.back() *=tmp;else if(op=='/') st.back() /=tmp;}else op=s[i++];}for(int& i:st) ret+=i;return ret;}
};

04.字符串解碼

題目鏈接：https://leetcode.cn/problems/decode-string/

給定一個(gè)經(jīng)過(guò)編碼的字符串，返回它解碼后的字符串。

編碼規(guī)則為: k[encoded_string]，表示其中方括號(hào)內(nèi)部的 encoded_string 正好重復(fù) k 次。注意 k 保證為正整數(shù)。

你可以認(rèn)為輸入字符串總是有效的；輸入字符串中沒(méi)有額外的空格，且輸入的方括號(hào)總是符合格式要求的。

此外，你可以認(rèn)為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復(fù)的次數(shù) k ，例如不會(huì)出現(xiàn)像 3a 或 2[4] 的輸入。

示例 1：

輸入：s = "3[a]2[bc]"
輸出："aaabcbc"

示例 2：

輸入：s = "3[a2[c]]"
輸出："accaccacc"

示例 3：

輸入：s = "2[abc]3[cd]ef"
輸出："abcabccdcdcdef"

示例 4：

輸入：s = "abc3[cd]xyz"
輸出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30
• s 由小寫(xiě)英文字母、數(shù)字和方括號(hào) '[]' 組成
• s 保證是一個(gè) 有效 的輸入。
• s 中所有整數(shù)的取值范圍為 [1, 300]

思路

這里我們要使用棧來(lái)解決問(wèn)題，我們需要模擬每一種情況的發(fā)生，以及細(xì)節(jié)的處理，我們建立一個(gè)重復(fù)數(shù)的棧和一個(gè)字符串的棧，遇到數(shù)字，放入數(shù)字棧中，遇到左括號(hào)，把后面的字符串提取出來(lái)，放入字符串棧中，遇到了右括號(hào)，解析然后放到字符串棧頂字符串之后，遇到單獨(dú)字符放到字符串棧頂字符串之后，最后棧頂?shù)淖址礊槲覀冃枰淖址?/p>

代碼

class Solution {
public:string decodeString(string s) {// 使用兩個(gè)棧，一個(gè)用于存儲(chǔ)字符串，另一個(gè)用于存儲(chǔ)數(shù)字stack<string> st;stack<int> nums;// 初始化棧，將一個(gè)空字符串入棧，用于存儲(chǔ)當(dāng)前解碼的結(jié)果st.push("");int i = 0, n = s.size();// 遍歷輸入字符串while (i < n) {// 如果當(dāng)前字符是數(shù)字，解析數(shù)字并入數(shù)字棧if (s[i] >= '0' && s[i] <= '9') {int tmp = 0;while (s[i] >= '0' && s[i] <= '9') tmp = tmp * 10 + (s[i++] - '0');nums.push(tmp);}// 如果當(dāng)前字符是'['，入棧一個(gè)空字符串，用于存儲(chǔ)當(dāng)前括號(hào)內(nèi)的解碼結(jié)果else if (s[i] == '[') {i++;string tmp;while (s[i] >= 'a' && s[i] <= 'z') tmp += s[i++];st.push(tmp);}// 如果當(dāng)前字符是']'，將棧頂字符串重復(fù)相應(yīng)次數(shù)后，與前一個(gè)棧頂字符串拼接else if (s[i] == ']') {string tmp = st.top();st.pop();int k = nums.top();nums.pop();while (k--) st.top() += tmp;i++;}// 如果當(dāng)前字符是字母，將字母拼接到棧頂字符串else {string tmp;while (i < n && s[i] >= 'a' && s[i] <= 'z') tmp += s[i++];st.top() += tmp;}}// 最終棧中存儲(chǔ)的即為解碼結(jié)果return st.top();}
};

05.驗(yàn)證棧序列

題目鏈接：https://leetcode.cn/problems/validate-stack-sequences/

給定 pushed 和 popped 兩個(gè)序列，每個(gè)序列中的 值都不重復(fù)，只有當(dāng)它們可能是在最初空棧上進(jìn)行的推入 push 和彈出 pop 操作序列的結(jié)果時(shí)，返回 true；否則，返回 false 。

示例 1：

輸入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
輸出：true
解釋：我們可以按以下順序執(zhí)行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

輸入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
輸出：false
解釋：1 不能在 2 之前彈出。

提示：

• 1 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• pushed 的所有元素 互不相同
• popped.length == pushed.length
• popped 是 pushed 的一個(gè)排列

思路

這里我們可以直接用一個(gè)棧來(lái)模擬這個(gè)過(guò)程，當(dāng)棧為空則說(shuō)明相匹配，否則就說(shuō)明不匹配

代碼

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;int i=0,n=popped.size();for(int& x:pushed){st.push(x);while(!st.empty()&&st.top()==popped[i]){st.pop();i++;}}return st.empty();}
};