1. 最小栈
题目链接：155. 最小栈 - 力扣（LeetCode）
题干：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素val推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
示例：
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
题目分析：
为了能够在O(1)的时间复杂度内找到当前栈中的最小值，我们能想到使用两个栈，一个栈正常存储数据（数据栈），另一个栈存储当前栈中的最小值（最小栈），这样最小值就能直接找到。
每次push数据的时候数据站正常push，最小栈判断在push之前的最小值与当前值的大小，如果push数据小于最小栈的top，那么最小栈就push当前值，否则就push栈顶值。
实际上，如果入栈的数据大多数都大于当前最小值时，最小栈中就会出现很多相同且连续的数，这样对于空间是很大的浪费，所以，我们可以考虑修改最小栈的入栈规则，只有当新入栈的数据小于当前最小值时才入最小栈，这样最小栈中的数据就不会出现这种冗余。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4feFqUnf-1682496626758)(null)]
代码实现：
//解法一： class MinStack { public: MinStack() {//这里默认构造函数就不用实现了，因为在这里成员变量会走初始化列表，在初始化列表这里会自动调用成员变量类型的默认构造函数 } void push(int val) { _st.push(val); if(_minst.empty() || val <= _minst.top()) { _minst.push(val); } } void pop() { if(_st.top() == _minst.top()) { _minst.pop(); } _st.pop(); } int top() { return _st.top(); } int getMin() { return _minst.top(); } stack<int> _st; stack<int> _minst; };
2. 逆波兰表达式
题目链接：150. 逆波兰表达式求值 - 力扣（LeetCode）
题干：
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为 '+'、'-'、'*' 和 '/' 。
- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = [“2”,“1”,“+”,“3”,“*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = [“4”,“13”,“5”,“/”,“+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
题目分析：
对于逆波兰表达式的计算，我们按照顺序遍历的方式，找到第一个运算符，然后将前面两个操作数拿出来运算即可，按照这种方式，我们可以想到用栈来存放数据，遇到操作符就pop出两个元素用于运算
代码实现：
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> st; for(auto& str : tokens) { if(str == "+" || str == "-" || str == "*" || str == "/")//遇到运算符 { //拿到左右两个操作数 int right = st.top(); st.pop(); int left = 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 '/': st.push(left / right); break; } } else//遇到数字 { st.push(stoi(str)); } } return st.top(); } };
拓展知识：中缀表达式和后缀表达式
表达式时由操作数和操作符组成的，我们一般见到的表达式通常是把操作符放在两个操作数之间的，这种把操作符放在中间的表达式叫做中缀表达式，这种表达式对人类很友好，但是对计算机不太友好。波兰数学家Jan Lukasiewicz提出了另一种数学表示法，它有两种表示形式：把运算符写在操作数之前，称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression)，如+AB；把运算符写在操作数之后，称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression)，如AB+。在上题中提到的逆波兰表达式就是后缀表达式
这里给出中缀转后缀的算法思路：
- 创建栈
- 从左向右顺序获取中缀表达式
- 数字直接输出
- 运算符
- 情况一：遇到左括号直接入栈，遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出，同时左括号出栈但是不输出。
- 情况二：遇到乘号和除号直接入栈，直到遇到优先级比它更低的运算符，依次弹栈。
- 情况三：遇到加号和减号，如果此时栈空，则直接入栈，否则，将栈中优先级高的运算符依次弹栈（注意：加号和减号属于同一个优先级，所以也依次弹栈）直到栈空或则遇到左括号为止，停止弹栈。（因为左括号要匹配右括号时才弹出）。
- 情况四：获取完后，将栈中剩余的运算符号依次弹栈输出
