请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
//示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
本题思路：首先栈的push，top,操作我们可以直接用stl库函数，最麻烦的是min函数，而且时间复杂度为O(1)，这个思想非常重要，定义一个栈s1,专门用来存放栈中的元素，完成栈的push,pop工作，然后定义一个辅助栈，来存放最小值，使得每一个s1对应的栈顶元素都有对应的最小值
class MinStack {
public:
/** initialize your data structure here. */
//1.定义两个栈，第一个栈用来存储值
//第二个栈用来寻找最小值
stack<int>s1;
stack<int>s2;
MinStack() {
? //先将s2初始化
? s2.push(INT_MAX);
}
void push(int x) {
? //为s1赋值
? s1.push(x);
? //每次找到栈顶元素和输入元素的较小值进行比较，使得s1的每个主站元素都有其对应的最小值
? s2.push(min(s2.top(),x));
}
void pop() {
? //s1执行pop操作
? //与之对应的最小值也执行pop操作，让每个栈顶元素与最小值进行对应
? s1.pop();
? s2.pop();
}
int top() {
? return s1.top();
}
int getMin() {
? return s2.top();
}
};
/**
\* Your MinStack object will be instantiated and called as such:
\* MinStack* obj = new MinStack();
\* obj->push(x);
\* obj->pop();
\* int param_3 = obj->top();
\* int param_4 = obj->getMin();
*/
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 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 之前弹出。
思路：首先建立一个栈，我们将pushed中的元素进行入栈，判断栈中的top()和popped中的元素是否相等，如果相等那么就st.pop(),popped中的元素向后走一位，之后再将pushed中的下一个元素继续入栈;如果不相等就将push元素后移，循环结束条件为i<push.size(),此时pushed数组已经走到了结尾，最终只需要判断popped数组是否走到了结尾，要是两者都走到了结尾，就说明两者为栈的压入与弹出，不相等说明不是栈的压入与弹出
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
int i=0;
int j=0;
//建立一个栈
stack<int>st;
//循环结束条件：pushed数组遍历完
while(i<pushed.size())
{
//每次将pushed[i]进入栈中
st.push(pushed[i]);
//判断刚进入栈的元素，即栈顶元素是否与popped[j]相等，相等st.pop(),j++
while(!st.empty()&&st.top()==popped[j])
{
st.pop();
j++;
}
//直到st,top()与popped[j]不相等
之后++i;
i++;
}
//判断是否为栈的压入与弹出只需要判断popped数组是否走完了
return j==popped.size();
}
};
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 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
提示：
1 <= tokens.length <= 104
tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-200, 200] 内的整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
逆波兰表达式(后缀表达式)求解方法:建立一个栈，遇到数字就入栈，遇到运算符就取出栈顶的两个元素进行相应的运算，并且将运算结果压入栈中
class Solution {
public:
//逆波兰表达式(后缀表达式)计算方法：遇到数字就入栈，遇到运算符就进行运算，运算完成后将结果再次返回到栈中，到最后返回栈顶元素即可
void GetNumber(stack<int>&st,int&left,int&right)
{
? right=st.top();
? st.pop();
? left=st.top();
? st.pop();
}
int evalRPN(vector<string>& tokens) {
? stack<int>st;
? //auto自动变量遍历每一个数组内容赋值到str中去
? for(auto &str :tokens)
? {
? int left,right;
? //str.back():返回末尾最后一位字符，用于判断它是什么符号
