栈的三道oj【C++】

这里就挑了三道题用来熟悉栈

最小栈

力扣链接

咱们已经是高贵的C++使用者了，不用像C语言一样从头开始造轮子了

这里我们调用了stack后，就会发现这道题主要的问题就是getMin的功能。

思路

按照一般人的思路可能会想在成员变量中添加一个最小值的成员：min
每次进栈和出栈来比较是否与值相同，进行更新。

但是在实现的过程中就会发现这个思路并不可行
因为：
**
当最小值出栈后，那第二个最小值不知道填什么
这个问题的最主要原因是栈无法遍历**

所以这里就要用新的思路了：

双栈：
创建一个用来放最小值的栈

1.每次插入都进行比较，看看是否是比栈顶小，这样就可以保证栈顶一直是最小值

2.注意这里相同大小的最小值也要进行放入，防止有相同的重复最小值

3.出栈时：与最小栈的栈顶进行比较，看看是否等于，如果一样就出最小栈的栈顶

思路大致是这样，实现就直接放在下面了。

解决代码

class MinStack {
public:void push(int val) {_stack.push(val);if(_stack_min.empty()||val<=_stack_min.top()){_stack_min.push(val);}}void pop() {if(_stack.top()==_stack_min.top())_stack_min.pop();_stack.pop();}int top() {return _stack.top();}int getMin(){return _stack_min.top();}private:stack<int> _stack;stack<int> _stack_min;
};

栈的压入弹出序列

力扣链接

思路

这道题主要就是考：如何判断出栈的顺序的可行性的判断。

这里我们随便来串数字进行判断

那我们来看一下我们的判断方法：

经过上图我们知道了我们判断一个出栈顺序，是否符合入栈顺序的基本过程

总结来说就是模拟入栈和出栈

所以这边我们可以把过程给归纳一下了：
1.不停入栈，直到和出栈顺序的元素相同
2.然后将出栈元素出栈，之后继续不停入栈，再知道和出栈队列元素相同
3.判断入栈元素是否无了，跳出循环
4.判断栈是否为空，如果为空栈，这样的话证明结论是是可行的，反之则不行。

解决代码

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> _st;int push=0;int pop=0;while(push<pushV.size()){_st.push(pushV[push++]);while(!_st.empty()&&_st.top()==popV[pop]){_st.pop();pop++;}}return _st.empty();}
};

逆波兰表达式

力扣链接

这里首先来解释一下为什么会有这个表达式的出现：

对于计算机来说，用中缀的表达式十分不友好。
因为如果读取两个数和一个符号后，还不能马上进行计算

因为你无法确定后面有没有更高优先级的运算符。

思路：

这里其实我们看到思路也很简单其实，没有什么复杂的。

这里就拿这个队列来举例子。

接下来就是重复就行了。。

思路还是很明确的。

解决代码

class Solution {
public:int evalRPN(vector<string>& tokens){for (auto& str : tokens){if (str != "*" && str != "-" && str != "+" && str != "/"){_st.push(stoi(str));}else{switch (str[0]){case '+':{int left = _st.top();_st.pop();int right = _st.top();_st.pop();_st.push(right + left);break;}case '-':{int left = _st.top();_st.pop();int right = _st.top();_st.pop();_st.push(right - left);break;}case '*':{int left = _st.top();_st.pop();int right = _st.top();_st.pop();_st.push(right * left);break;}case '/':{int left = _st.top();_st.pop();int right = _st.top();_st.pop();_st.push(right / left);break;}}}}return _st.top();}
private:stack<int> _st;};