一、最小栈
1、题目讲解
2、思路讲解
3、代码实现
class MinStack { public: MinStack() {} void push(int val) { st.push(val); if(minst.empty() || st.top()<=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(); } stack<int> st; stack<int> minst; };
二、栈的压入、弹出序列
1、题目讲解
2、思路讲解
3、代码实现
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { stack<int> s; int pushi=0,popi=0; for(auto ch:pushV) { s.push(pushV[pushi]); pushi++; while(!s.empty() && s.top()==popV[popi]) { s.pop(); popi++; } } return s.empty(); }
三、逆波兰表达式求值
1、题目讲解
2、思路讲解
3、代码实现
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> s; for(auto& ch:tokens) { if(ch=="+" || ch=="-" || ch=="*" || ch=="/" ) { int right=s.top(); s.pop(); int left=s.top(); s.pop(); switch(ch[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(ch)); } } return s.top(); } };
