栈（Stack）是一种基于先进后出（Last In, First Out，LIFO）原则的数据结构。栈具有两个主要的操作：
- 压栈（Push）：将元素添加到栈的顶部。
- 出栈（Pop）：从栈的顶部移除元素。
栈常常用于需要反转操作顺序的场景，或者在需要记录操作历史的情况下。在算法中，栈的应用广泛，以下是一些典型的栈算法：
-
括号匹配问题：使用栈来检查表达式中的括号是否匹配，例如检查
()、[]、{}是否正确嵌套。 - 逆波兰表达式求值：通过栈来实现对逆波兰表达式的求值，其中操作数和操作符都存储在栈中。
- 函数调用栈：在编程语言中，函数调用时的执行过程通常使用函数调用栈（Call Stack）来管理。
- 深度优先搜索（DFS）：在图或树的遍历过程中，使用栈来实现深度优先搜索。
- 迭代法求解二叉树的前序、中序、后序遍历：通过栈来模拟递归过程，实现二叉树的不同遍历方式。
- 表达式求值：将中缀表达式转换为后缀表达式，然后使用栈求解后缀表达式的值。
- 迷宫求解：通过栈来记录路径，实现对迷宫的求解过程。
栈的特性使其在某些问题场景中非常有效和方便。在算法设计和实现中，栈通常用于临时存储数据、回溯操作、深度优先搜索等。
01.删除字符串中的所有相邻重复项
题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：
1 <= S.length <= 20000-
S仅由小写英文字母组成。
思路
这里使用栈的思想可以很好的解决这个问题，我们每插入一个字符前进行对比，如果栈顶存在该字符，则删除栈顶字符且不插入，否则插入字符，最后留在栈中的字符就是需要返回的，考虑到字符顺序的问题，我们可以直接用字符串来直接模拟栈。
代码文章来源地址https://www.toymoban.com/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 。# 代表退格字符。
**注意：**如果对空文本输入退格字符，文本继续为空。
示例 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 ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
**注意：**不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
示例 1：
输入：s = "3+2*2"
输出：7
示例 2：
输入：s = " 3/2 "
输出：1
示例 3：
输入：s = " 3+5 / 2 "
输出：5
提示：
1 <= s.length <= 3 * 105-
s由整数和算符('+', '-', '*', '/')组成，中间由一些空格隔开 -
s表示一个 有效表达式 - 表达式中的所有整数都是非负整数，且在范围
[0, 231 - 1]内 - 题目数据保证答案是一个 32-bit 整数
思路
根据题目要求我们只需要考虑空格、数字和四个运算符这几种情况，我们可以使用一个数组来模拟栈插入每一个数，使用一个前缀字符来进行运算符的标记，初始设为加，当我们碰到加减都更新，碰到乘除就直接在栈顶计算，直至字符串结束，最后我们将栈中的数相加即可。
代码
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/
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 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由小写英文字母、数字和方括号'[]'组成 -
s保证是一个 有效 的输入。 -
s中所有整数的取值范围为[1, 300]
思路
这里我们要使用栈来解决问题，我们需要模拟每一种情况的发生，以及细节的处理，我们建立一个重复数的栈和一个字符串的栈，遇到数字，放入数字栈中，遇到左括号，把后面的字符串提取出来，放入字符串栈中，遇到了右括号，解析然后放到字符串栈顶字符串之后，遇到单独字符放到字符串栈顶字符串之后，最后栈顶的字符串即为我们需要的字符串。
代码
class Solution {
public:
string decodeString(string s) {
// 使用两个栈，一个用于存储字符串，另一个用于存储数字
stack<string> st;
stack<int> nums;
// 初始化栈，将一个空字符串入栈，用于存储当前解码的结果
st.push("");
int i = 0, n = s.size();
// 遍历输入字符串
while (i < n) {
// 如果当前字符是数字，解析数字并入数字栈
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);
}
// 如果当前字符是']'，将栈顶字符串重复相应次数后，与前一个栈顶字符串拼接
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
解释：我们可以按以下顺序执行：
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的一个排列
思路
这里我们可以直接用一个栈来模拟这个过程，当栈为空则说明相匹配，否则就说明不匹配文章来源：https://www.toymoban.com/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模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[职场] 会计学专业学什么 #其他#知识分享#职场发展](https://imgs.yssmx.com/Uploads/2024/02/830441-1.jpeg)
