文章目录

• 最小栈
• 栈的压入、弹出序列
• 逆波兰表达式求值

最小栈

题目要求是在常数时间内检索到最小的元素的栈，思路是每当栈中存放一个更小的数据时，就将它入栈，相同的值也要入栈。

class MinStack {
public:MinStack() {}//对自定义类型，调用它的构造函数void push(int val) {_st.push(val);if(_minst.empty()||val<=_minst.top()){_minst.push(val);}}void pop() {if(_st.top()==_minst.top()){_minst.pop();}_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}
private:stack<int> _st;stack<int> _minst;
};

栈的压入、弹出序列

class Solution {public:bool IsPopOrder(vector<int> pushV, vector<int> popV) {stack<int> _st;int ipush = 0;int ipop = 0;while (ipush < pushV.size()) {_st.push(pushV[ipush++]);while(!_st.empty()&&_st.top()==popV[ipop]){_st.pop();ipop++;}}return _st.empty();}
};

逆波兰表达式求值

题目的要求就是将后缀表达式转换为中缀表达式并进行计算。
下面来了解一下后缀怎么转换为中缀表达式的。

拓展： 将中缀表达式转换为后缀表达式

#
#
#
#
#
#
#
#
#
##
#

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for(auto& ch:tokens){if(ch=="-"||ch=="+"||ch=="/"||ch=="*"){int right=st.top();st.pop();int left=st.top();st.pop();switch(ch[0])//switch必须是整形char也是属于整形{case '+':st.push(left+right);break;case '-':st.push(left-right);break;case '*':st.push(left*right);break;case '/':st.push(left/right);break;}}else{st.push(stoi(ch));}}return st.top();}
};

造句网