栈和队列相关的OJ题

1.栈的压入、弹出序列

题目链接

栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

题目描述

题目给出两个序列，一个是入序列pushV，一个是出序列popV，要求判断是否匹配入栈出栈的规则顺序。

解题思路

可以用数据模拟入栈出栈，将pushV序列的数据逐一放到栈中，当放到的数据与popV序列的数据相同时，则pop掉数据，再进行判断是否和栈顶相同，若是相同则进行pop，若是不同则将剩下数据再次逐一入栈，每次入栈一个数据都作一次判断是否需要出栈，最后将所有数据入栈后，此时对应判断pop数据后跳出循环，若是循环结束后栈内数据全部出栈成功，则意味着这两个序列匹配入栈出栈的规则，若还有数据则说明某次不匹配。

参考代码

    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {size_t pushi = 0,popi = 0;stack<int> st;while(pushi != pushV.size()){st.push(pushV[pushi++]);while(!st.empty() && st.top() == popV[popi]){st.pop();popi++;}}return st.empty();}

2.最小栈

题目链接

155. 最小栈 - 力扣（LeetCode）

题目描述

题目要求实现一个能够返回栈内数据最小值的栈，具备栈该有的基本接口，并且要以O（1）的代价提供一个接口，能够返回栈内最小的数据

解题思路

用C++的话可以复用库内的栈，将数据和最小值分别存在两个栈中，当栈push的时候，最小值的栈作判断，若是push的值比栈顶的小或者相等，则将值同时存放到放最小值的栈中，出栈时同样判断是否需要一起出栈，即可实现要求

参考代码

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

3.逆波兰表达式求值

题目链接

150. 逆波兰表达式求值 - 力扣（LeetCode）

题目描述

逆波兰表达式也叫后缀表达式，计算机在对式子进行运算时，需要知道运算的先后顺序，因此需要将平时常见的中缀表达式先转换为后缀表达式，该题目要求模拟实现计算机然后实现对中缀表达式进行运算，题目给一串字符串序列，我们需要模拟实现计算过程，将计算结果返回

解题思路

后缀表达式的计算方法，从左往右遍历，遇到数值则入栈，当遇到运算符时，则将栈顶的两个元素作为表达式左值和右值进行运算（栈顶第一个元素为右值，第二个为左值），将结果继续入栈，重复操作后，最终遍历结束后，在栈中保留下来的值就是计算的最终结果。

参考代码

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

4.用栈实现队列

题目链接

232. 用栈实现队列 - 力扣（LeetCode）

题目描述

用两个栈去实现一个队列，并且要支持其基本的接口

解题思路

两个栈可以想象成两个单口长杯，数据入队列时，用a栈去接收数据，当需要出队列时，则将a栈内的数据全部倒到b栈中，a栈负责接收数据，b栈负责出数据，当b为空则找a要数据，两个栈都为空则说明队列内为空

参考代码

class MyQueue 
{
public:MyQueue() {}void push(int x) {_in.push(x);}void if_out_empty(){if(_out.empty() && !_in.empty()){while(!_in.empty()){_out.push(_in.top());_in.pop();}}}int pop() {if_out_empty();int ret = peek();_out.pop();return ret;}int peek() {if_out_empty();return _out.top();}bool empty() {return _in.empty()&&_out.empty();}
private:stack<int> _in;stack<int> _out;
};

5.用队列实现栈

题目链接

225. 用队列实现栈 - 力扣（LeetCode）

题目描述

用两个队列实现栈的基本接口

解题思路

核心难点在于找到栈顶top，一个队列用来存放数据，一个队列用来找到栈顶，当需要pop栈顶的时候，可以让存放数据的队列，除了队尾的数据，也就是需要被pop的栈顶，其余全部放到另一个队列中，让另一个队列重新作为存储数据的地方，而栈顶单独拿出来释放即可。

参考代码

class MyStack {
public:MyStack() {}void push(int x) {if(_q1.empty()){_q2.push(x);}else{_q1.push(x);}}int pop() {int ret = top();if(!_q1.empty()){while(_q1.size() != 1){_q2.push(_q1.front());_q1.pop();}_q1.pop();}else{while(_q2.size() != 1){_q1.push(_q2.front());_q2.pop();}_q2.pop();}return ret;}int top() {if(!_q1.empty()){return _q1.back();}else{return _q2.back();}}bool empty() {return _q1.empty() && _q2.empty();}
private:queue<int> _q1;queue<int> _q2;};