1 与栈有关的考题
1.1 最小栈
题目描述：
解题思路：
要想在O(1)时间内获得栈内最小元素只用一个栈肯定是行不通的，所以我们不妨再开一个栈来记录当前栈里面每个元素的最小值，这样就要多开出O(N)的空间，可以优化空间的方法是并不是所有的元素都要入最小栈，而是当前元素比最小栈栈顶的数据大便不必再入数据了，但是等于时一定要入进去，当pop掉元素时只需要比较普通栈与最小栈栈顶元素是否相等，若相等，则最小栈栈顶数据也得pop。
参考代码：
class MinStack { public: MinStack() {} void push(int val) { _st.push(val); if(_minSt.empty() || _minSt.top()>=val) _minSt.push(val); } void pop() { if(_minSt.top()==_st.top()) _minSt.pop(); _st.pop(); } int top() { return _st.top(); } int getMin() { return _minSt.top(); } stack<int> _st; stack<int> _minSt;//记录最小的数据 };
运行结果：
题后反思：
万一数据像这种22222222,貌似我们优化空间的方法起不到作用了，可以采取的优化措施是我们存储数据时可以存一个pair,里面额外记录一下变量的个数，当有重复数据时便不再入数据了，而是++里面的计数器，pop时就--里面的计数器，大家有兴趣可以自己实现下，这里我就不再实现了。
1.2 栈的弹出压入序列
题目描述：
解题思路：
这道题的解决方法有很多种，这里分享一种比较容易理解的思路：另外搞一个栈，将栈的压入序列不断的push到这个栈中，当该栈不为空并且栈的弹出序列与该栈栈顶数据相等时就pop掉该栈栈顶数据，然后不断迭代走，最后返回值就是该栈是否为空或者是否走到了弹出序列的尾。
参考代码：
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int> v; int pushi=0,popi=0; while(pushi<pushV.size()) { v.push(pushV[pushi++]); while(!v.empty() && v.top()==popV[popi]) { v.pop(); popi++; } } return v.empty(); } };
运行结果：
1.3 逆波兰表达式求值
题目描述：
解题思路：
由于逆波兰表达式就是后缀表达式，运算符的优先级已经确定了，所以我们只需要模拟下运算的过程即可，注意先取的数据是右，后取的数据为左。
参考代码：
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> s; for(auto& e:tokens) { if(e=="+" || e=="-" || e=="*" || e=="/") { int right=s.top(); s.pop(); int left=s.top(); s.pop(); switch(e[0]) { case '+': s.push(left+right); break; case '-': s.push(left-right); break; case '*': s.push(left*right); break; case '/': s.push(left/right); break; } } else { s.push(stoi(e)); } } return s.top(); } };
运行结果：
题后反思：
假如给的不是后缀表达式，而是中缀表达式，如何将中缀表达式转化为后缀表达式呢？
给定中缀表达式【1+2*(3-4)+5/6】，我们如何将其转化为后缀表达式？
基本规则是这样的：当遇到操作数的时候我们直接输出；遇到操作符当栈为空就直接入栈，栈若不为空就与栈顶数据相比，若优先级大于栈顶就将该操作符入栈(由于后面操作符优先级可能更大，所以先让其入栈),若优先级小于或者等于栈顶，就将栈顶数据pop掉然后输出，直到栈为空或者遇到优先级更小的操作符，然后继续迭代直到访问到所有元素。
但是这个规则只适用于没有()的转换中，例如【1+2*3-4】可以转化成【1 2 3 * + 4 -】
但是像上面的那个栗子【1+2*(3-4)+5/6】貌似就不适用了，处理方法有两种：
第一种是不入()到栈中，当发现出现了()时就认为()中的运算符优先级非常大，就让其入栈，其他规则与基本规则类似。
第二种是将()入栈，当出现(时就认为(的优先级非常低，(目的是让括号中运算符入栈),当出现)时同样认为)的优先级非常低，(目的是让括号中运算符出栈输出)
无论使用哪种规则，我们都能够很轻易的将上述中缀表达式转化为：
【1 2 3 4 - * + 5 6 / +】
