2017做哪些网站能致富,网络营销是什么营销,网站开发语言 asp,做网站时怎么取消鼠标悬停栈和队列的相关oj 最小栈思路解决代码 栈的压入弹出序列思路解决代码 逆波兰表达式思路#xff1a;解决代码 这里就挑了三道题用来熟悉栈
最小栈
力扣链接 咱们已经是高贵的C使用者了#xff0c;不用像C语言一样从头开始造轮子了
这里我们调用了stack后#xff0c;就会发… 栈和队列的相关oj 最小栈思路解决代码 栈的压入弹出序列思路解决代码 逆波兰表达式思路解决代码 这里就挑了三道题用来熟悉栈
最小栈
力扣链接 咱们已经是高贵的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:stackint _stack;stackint _stack_min;
};栈的压入弹出序列
力扣链接 思路
这道题主要就是考如何判断出栈的顺序的可行性的判断。
这里我们随便来串数字进行判断 那我们来看一下我们的判断方法 经过上图我们知道了我们判断一个出栈顺序是否符合入栈顺序的基本过程
总结来说就是模拟入栈和出栈
所以这边我们可以把过程给归纳一下了 1.不停入栈直到和出栈顺序的元素相同 2.然后将出栈元素出栈之后继续不停入栈再知道和出栈队列元素相同 3.判断入栈元素是否无了跳出循环 4.判断栈是否为空如果为空栈这样的话证明结论是是可行的反之则不行。
解决代码
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pushV int整型vector * param popV int整型vector * return bool布尔型*/bool IsPopOrder(vectorint pushV, vectorint popV) {// write code herestackint _st;int push0;int pop0;while(pushpushV.size()){_st.push(pushV[push]);while(!_st.empty()_st.top()popV[pop]){_st.pop();pop;}}return _st.empty();}
};逆波兰表达式
力扣链接
这里首先来解释一下为什么会有这个表达式的出现
对于计算机来说用中缀的表达式十分不友好。 因为如果读取两个数和一个符号后还不能马上进行计算
因为你无法确定后面有没有更高优先级的运算符。
思路
这里其实我们看到思路也很简单其实没有什么复杂的。 这里就拿这个队列来举例子。 接下来就是重复就行了。。
思路还是很明确的。
解决代码 class Solution {
public:int evalRPN(vectorstring 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:stackint _st;};
