C算法专题学习栈相关的算法
C++算法专题学习：栈相关的算法
[
「开学季干货」：聚焦知识梳理与经验分享
10w+人浏览
192人参与
](
)
本期我们就来从0开始学习C++中与经典的数据结构——栈相关的算法
栈相关的题解代码已经上传至作者的个人gitee： 喜欢请点个赞谢谢
栈相关的算法
栈的基本概念与特性
栈（Stack）是一种遵循"后进先出"（LIFO, Last In First Out）原则的线性数据结构。它只允许在一端（称为栈顶，top）进行插入（push）和删除（pop）操作。栈的主要特性包括：
- 后进先出原则：最后一个入栈的元素会最先被弹出
- 限定操作位置：所有操作只能在栈顶进行
- 基本操作：
- push：将元素压入栈顶
- pop：移除并返回栈顶元素
- peek/top：返回栈顶元素但不移除
- isEmpty：判断栈是否为空
- size：返回栈中元素数量
栈的变种与高级应用
最小栈：设计一个支持push、pop、top操作，并能在常数时间内检索到最小元素的栈
- 实现方法：使用辅助栈同步存储当前最小值
双栈实现队列：用两个栈模拟队列的FIFO行为
- 一个栈用于入队，另一个用于出队
- 当出队栈为空时，将入队栈元素全部转移到出队栈
浏览器历史记录：使用两个栈实现前进后退功能
- 一个栈存储后退页面，另一个存储前进页面
函数调用栈：程序执行时管理函数调用关系
- 调用函数时压栈，返回时弹栈
深度优先搜索(DFS)：图的遍历算法，显式使用栈或递归隐式使用调用栈
实际工程中的应用案例
- 撤销操作实现：文本编辑器中的撤销功能通常使用栈存储操作历史
- 语法分析：编译器使用栈进行语法检查和代码生成
- 路由导航：Web应用中的路由历史管理
- 表达式解析：计算器和编程语言解释器中的表达式处理
- 内存管理：程序运行时的局部变量存储
复杂度分析与优化
- 基本操作时间复杂度：O(1)
- 空间复杂度：O(n)，n为栈中元素数量
- 优化方向：
- 使用数组实现时考虑动态扩容
- 对于特定问题（如单调栈）可以优化空间使用
- 多栈共享存储空间（如双栈法实现队列）
1、删除字符串中所有相邻重复项
算法思想：用栈模拟
class Solution {
public:
string removeDuplicates(string s)
{
string ret;//模拟栈
for(auto&ch:s)
{
if(ret.size()&&ch==ret.back()) ret.pop_back();//入栈
else ret+=ch;//出栈
}
return ret;
}
};2、比较含退格的字符串
算法思想：
class Solution {
public:
bool backspaceCompare(string s, string t)
{
return changestr(s)==changestr(t);
}
string changestr(string s)
{
string ret;
for(auto&ch:s)
{
if(ch!='#') ret+=ch;
else
{
if(ret.size()) ret.pop_back();
}
}
return ret;
}
};3、基本计算器2
算法思想：栈模拟
以+4-3+6*4/2-123+34这个表达式为例
当我们遇到数字的时候提取出来入栈，然后将其前面的符号存储起来。当遇到一个数前面是乘的时候将数字出栈
分情况讨论：
1、遇到操作符更新操作符op。
2、遇到数字：将数字提取出来，存储到tmp中。
根据op的符号分情况讨论：
(1）op==’+’，tmp入栈
（2）op==’-‘，-tmp
（3）op==’*’，直接乘到栈顶元素
（4）op==’/’，直接除到栈顶元素
class Solution {
public:
int calculate(string s)
{
vector<int>st;//数组模拟栈结构
int i=0,n=s.size();
char op='+';
while(i<n)
{
if(s[i]==' ') i++;
else if((s[i]-'0')>=0&&(s[i]-'0')<=9) //提取数字
{
int tmp=0;
while(i<n&&(s[i]-'0')>=0&&(s[i]-'0')<=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];
i++;
}
}
int ans=0;
for(auto& x:st)
{
ans+=x;
}
return ans;
}
};4、字符串解码
算法思想：用栈来模拟
分情况讨论：
1、如果遇到数字：提取出来放入数字栈中
2、如果遇到字符串：提取出字符，放到字符串栈
3、如果遇到“[”： 字符串提取出来放入字符串栈中
4、如果遇到“]”：字符串栈顶数据拿出来放到字符串后面
class Solution {
public:
string decodeString(string s)
{
string ret="";
stack<int>nums;
stack<string>str;
int num=0,n=s.size();
for(auto&x:s)
{
if(x=='[')
{
nums.push(num);
num=0;
str.push(ret);
ret="";
}
else if(x==']')
{
int r=nums.top();
nums.pop();
for(int i=0;i<r;i++)
{
str.top()+=ret;
}
ret=str.top();
str.pop();
}
else if(x>='0'&&x<='9')
{
num=num*10+(x-'0');
}
else if(x>='a'&&x<='z'||x>='A'&&x<='Z')
{
ret+=x;
}
}
return ret;
}
};5、验证栈序列
算法思想：
1、所有元素进栈
2、进栈的同时判断是否出栈
3、所有元素进站后，判断i是否遍历完毕或者判断栈是否为空
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
{
stack<int>st;
int i=0, n=popped.size();
for(auto& x:pushed)
{
st.push(x);
while(st.size()&&st.top()==popped[i])
{
st.pop();
i++;
}
}
return i==n;
}
};本期内容到这里就结束了，喜欢请点个赞谢谢