【C++】stack（一）
文章目录
- 1.stack的介绍和使用
- 1.1 stack的介绍
- 1.2 stack的使用
- 最小栈
- 栈的弹出压入序列
- 逆波兰表达式求值
- 用两个栈实现队列
1.stack的介绍和使用
1.1 stack的介绍
stack的文档介绍
1.2 stack的使用
| 函数说明 | 接口说明 |
|---|---|
| stack() | 构造空的栈 |
| empty() | 检测stack是否为空 |
| size() | 返回stack中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素val压入stack中 |
| pop() | 将stack中尾部的元素弹出 |
最小栈
1.插入值val<=minst栈顶数据，minst就要插入val。如果val=minst栈顶数据时却不插入，如果删除st栈顶数据，minst栈顶数据因为和st栈顶数据相等也会被删除
2.为什么可以没有MinStack（空 {}）？ 因为 MinStack 内部通常使用其他容器（如 std::stack 或
std::vector）来存储数据，而这些容器自身就有默认构造函数，能够正确初始化为空状态。 因此，MinStack
的构造函数不需要做任何额外工作，只需调用成员变量的默认构造即可。而成员变量的默认构造会被编译器自动调用，即使构造函数体为空。
实际上，如果你完全省略 MinStack() {}
这个显式定义，编译器也会隐式生成一个完全相同的默认构造函数。所以“可以没有”指的是：即使你不写这个函数，程序也能编译通过。
classMinStack{public:MinStack(){}voidpush(intval){_st.push(val);if(_minst.empty()||val<=_minst.top()){_minst.push(val);}}voidpop(){if(_st.top()==_minst.top())_minst.pop();_st.pop();}inttop(){return_st.top();}intgetMin(){return_minst.top();}private:stack<int>_st;stack<int>_minst;};栈的弹出压入序列
思路：
- 入栈序列入栈
- 栈顶数据跟出栈序列比较
2.1 相等，持续出栈顶数据，直到不相等或栈为空
2.2 不相等 - 继续1,2，直到入栈序列进入完了
- 如果入栈序列进入完了，而出数据的栈为空则合法，否则不合法
class Solution{public:boolIsPopOrder(vector<int>&pushV,vector<int>&popV){size_tpushi=0,popi=0;stack<int>st;while(pushi<pushV.size()){st.push(pushV[pushi]);while(!st.empty()&&st.top()==popV[popi]){st.pop();popi++;}++pushi;}returnst.empty();}};逆波兰表达式求值
逆波兰表达式也称后缀表达式，它的运算符优先级已经排好了
思路：
1.运算数入栈
2.遇到运算符，取栈顶两个数据运算，运算结果继续入栈，先取到的值是右操作数
注意
1.这里遍历string时，for(auto& e:str)中，auto要加&，如果不加 &，即 for (auto e :
str)，则每个字符都会被拷贝到循环变量 e 中。虽然拷贝一个 char 开销很小，但对于长字符串或频繁遍历，累积的拷贝仍有一定成本。
使用 auto& 直接绑定到原字符串中的字符，无需拷贝，效率更高。
2.tokens 是 vector&，即字符串向量，它的每个元素是 string 类型（一个完整的 token，例如 “2”、“+”、“3”）。
因此，for(auto& str : tokens)中的 str 是 string 类型的引用，代表一个字符串，而不是单个字符。
后面使用 str[0] 是取这个字符串的第一个字符，用于 switch 判断运算符
3.在 C++ 中，switch 语句的 case 标签后面必须跟着整数常量表达式。但这里的 ‘+’、‘-’ 等字符字面量属于整数常量，因为字符类型 char 是整型的一种，每个字符都对应一个整数值（例如 ASCII 码）。所以 case ‘+’ 是合法的，编译器会将 ‘+’ 转换为它的 ASCII 码（43）进行比较。
换句话说，switch (str[0]) 拿到的是字符串的第一个字符（比如 ‘+’ 对应的整数 43），而 case ‘+’ 也是整数 43，两者匹配。这种写法很常见，比直接写数字 case 43 更直观。
classSolution{public:intevalRPN(vector<string>&tokens){stack<int>st;for(auto&str:tokens){if("+"==str||"-"==str||"*"==str||"/"==str){//运算符intright=st.top();st.pop();intleft=st.top();st.pop();switch(str[0]){case'+':st.push(left+right);break;case'-':st.push(left-right);break;case'*':st.push(left*right);break;case'/':// 题目说明了不存在除数为0的情况st.push(left/right);break;}}else{st.push(stoi(str));}}returnst.top();}};用两个栈实现队列
classMyQueue{public:MyQueue(){}voidpush(intx){instack.push(x);}//返回删除元素intpop(){if(outstack.empty())in2out();intx=outstack.top();outstack.pop();returnx;}intpeek(){if(outstack.empty())in2out();returnoutstack.top();}//取队列的队首boolempty(){returninstack.empty()&&outstack.empty();}private:stack<int>instack;stack<int>outstack;voidin2out(){while(!instack.empty()){outstack.push(instack.top());instack.pop();}}};