棧（Stack）是一種基于先進后出（Last In, First Out，LIFO）原則的數(shù)據(jù)結構。棧具有兩個主要的操作：
- 壓棧（Push）：將元素添加到棧的頂部。
- 出棧（Pop）：從棧的頂部移除元素。
棧常常用于需要反轉操作順序的場景，或者在需要記錄操作歷史的情況下。在算法中，棧的應用廣泛，以下是一些典型的棧算法：
-
括號匹配問題：使用棧來檢查表達式中的括號是否匹配，例如檢查
()、[]、{}是否正確嵌套。 - 逆波蘭表達式求值：通過棧來實現(xiàn)對逆波蘭表達式的求值，其中操作數(shù)和操作符都存儲在棧中。
- 函數(shù)調用棧：在編程語言中，函數(shù)調用時的執(zhí)行過程通常使用函數(shù)調用棧（Call Stack）來管理。
- 深度優(yōu)先搜索（DFS）：在圖或樹的遍歷過程中，使用棧來實現(xiàn)深度優(yōu)先搜索。
- 迭代法求解二叉樹的前序、中序、后序遍歷：通過棧來模擬遞歸過程，實現(xiàn)二叉樹的不同遍歷方式。
- 表達式求值：將中綴表達式轉換為后綴表達式，然后使用棧求解后綴表達式的值。
- 迷宮求解：通過棧來記錄路徑，實現(xiàn)對迷宮的求解過程。
棧的特性使其在某些問題場景中非常有效和方便。在算法設計和實現(xiàn)中，棧通常用于臨時存儲數(shù)據(jù)、回溯操作、深度優(yōu)先搜索等。
01.刪除字符串中的所有相鄰重復項
題目鏈接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
給出由小寫字母組成的字符串 S，重復項刪除操作會選擇兩個相鄰且相同的字母，并刪除它們。
在 S 上反復執(zhí)行重復項刪除操作，直到無法繼續(xù)刪除。
在完成所有重復項刪除操作后返回最終的字符串。答案保證唯一。
示例：
輸入："abbaca"
輸出："ca"
解釋：
例如，在 "abbaca" 中，我們可以刪除 "bb" 由于兩字母相鄰且相同，這是此時唯一可以執(zhí)行刪除操作的重復項。之后我們得到字符串 "aaca"，其中又只有 "aa" 可以執(zhí)行重復項刪除操作，所以最后的字符串為 "ca"。
提示：
1 <= S.length <= 20000-
S僅由小寫英文字母組成。
思路
這里使用棧的思想可以很好的解決這個問題，我們每插入一個字符前進行對比，如果棧頂存在該字符，則刪除棧頂字符且不插入，否則插入字符，最后留在棧中的字符就是需要返回的，考慮到字符順序的問題，我們可以直接用字符串來直接模擬棧。
代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-829600.html
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 兩個字符串，當它們分別被輸入到空白的文本編輯器后，如果兩者相等，返回 true 。# 代表退格字符。
**注意：**如果對空文本輸入退格字符，文本繼續(xù)為空。
示例 1：
輸入：s = "ab#c", t = "ad#c"
輸出：true
解釋：s 和 t 都會變成 "ac"。
示例 2：
輸入：s = "ab##", t = "c#d#"
輸出：true
解釋：s 和 t 都會變成 ""。
示例 3：
輸入：s = "a#c", t = "b"
輸出：false
解釋：s 會變成 "c"，但 t 仍然是 "b"。
提示：
1 <= s.length, t.length <= 200-
s和t只含有小寫字母以及字符'#'
思路
同樣我們使用棧的思想，分別使用兩個空字符串來模擬棧，遇到#字符就出棧，其他時候進棧，最后比較兩個字符串即可。
代碼
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.基本計算器 II
題目鏈接：https://leetcode.cn/problems/basic-calculator-ii
給你一個字符串表達式 s ，請你實現(xiàn)一個基本計算器來計算并返回它的值。
整數(shù)除法僅保留整數(shù)部分。
你可以假設給定的表達式總是有效的。所有中間結果將在 [-231, 231 - 1] 的范圍內。
**注意：**不允許使用任何將字符串作為數(shù)學表達式計算的內置函數(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ù)和算符('+', '-', '*', '/')組成，中間由一些空格隔開 -
s表示一個 有效表達式 - 表達式中的所有整數(shù)都是非負整數(shù)，且在范圍
[0, 231 - 1]內 - 題目數(shù)據(jù)保證答案是一個 32-bit 整數(shù)
思路
根據(jù)題目要求我們只需要考慮空格、數(shù)字和四個運算符這幾種情況，我們可以使用一個數(shù)組來模擬棧插入每一個數(shù)，使用一個前綴字符來進行運算符的標記，初始設為加，當我們碰到加減都更新，碰到乘除就直接在棧頂計算，直至字符串結束，最后我們將棧中的數(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/
給定一個經(jīng)過編碼的字符串，返回它解碼后的字符串。
編碼規(guī)則為: k[encoded_string]，表示其中方括號內部的 encoded_string 正好重復 k 次。注意 k 保證為正整數(shù)。
你可以認為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號總是符合格式要求的。
此外，你可以認為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復的次數(shù) k ，例如不會出現(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由小寫英文字母、數(shù)字和方括號'[]'組成 -
s保證是一個 有效 的輸入。 -
s中所有整數(shù)的取值范圍為[1, 300]
思路
這里我們要使用棧來解決問題，我們需要模擬每一種情況的發(fā)生，以及細節(jié)的處理，我們建立一個重復數(shù)的棧和一個字符串的棧，遇到數(shù)字，放入數(shù)字棧中，遇到左括號，把后面的字符串提取出來，放入字符串棧中，遇到了右括號，解析然后放到字符串棧頂字符串之后，遇到單獨字符放到字符串棧頂字符串之后，最后棧頂?shù)淖址礊槲覀冃枰淖址?/p>
代碼
class Solution {
public:
string decodeString(string s) {
// 使用兩個棧，一個用于存儲字符串，另一個用于存儲數(shù)字
stack<string> st;
stack<int> nums;
// 初始化棧，將一個空字符串入棧，用于存儲當前解碼的結果
st.push("");
int i = 0, n = s.size();
// 遍歷輸入字符串
while (i < n) {
// 如果當前字符是數(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);
}
// 如果當前字符是'['，入棧一個空字符串，用于存儲當前括號內的解碼結果
else if (s[i] == '[') {
i++;
string tmp;
while (s[i] >= 'a' && s[i] <= 'z') tmp += s[i++];
st.push(tmp);
}
// 如果當前字符是']'，將棧頂字符串重復相應次數(shù)后，與前一個棧頂字符串拼接
else if (s[i] == ']') {
string tmp = st.top();
st.pop();
int k = nums.top();
nums.pop();
while (k--) st.top() += tmp;
i++;
}
// 如果當前字符是字母，將字母拼接到棧頂字符串
else {
string tmp;
while (i < n && s[i] >= 'a' && s[i] <= 'z') tmp += s[i++];
st.top() += tmp;
}
}
// 最終棧中存儲的即為解碼結果
return st.top();
}
};
05.驗證棧序列
題目鏈接：https://leetcode.cn/problems/validate-stack-sequences/
給定 pushed 和 popped 兩個序列，每個序列中的 值都不重復，只有當它們可能是在最初空棧上進行的推入 push 和彈出 pop 操作序列的結果時，返回 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 <= 10000 <= pushed[i] <= 1000-
pushed的所有元素 互不相同 popped.length == pushed.length-
popped是pushed的一個排列
思路
這里我們可以直接用一個棧來模擬這個過程，當棧為空則說明相匹配，否則就說明不匹配文章來源：http://www.zghlxwxcb.cn/news/detail-829600.html
代碼
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();
}
};
到了這里，關于算法沉淀——棧（leetcode真題剖析）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
![[職場] 會計學專業(yè)學什么 #其他#知識分享#職場發(fā)展](https://imgs.yssmx.com/Uploads/2024/02/830441-1.jpeg)
