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 / +】