5.3 用队列实现栈

原OJ题：225. 用队列实现栈 - 力扣（LeetCode）

两队列实现栈

1. 入栈的实现

选非空的队列进行push，两个都空的话随便选。

2. 出栈的实现和返回栈顶元素

假设我们有两个队列1、2。

若1队列非空，2队列为空，则1队列除了队尾全部转移到2队，1队仅剩的1个元素即为目标元素。

随着操作次数变多，我们可能会忘了哪个队列为空。此时需要假设一个队列为空，再去验证该队列是否为空。

3. 判断队列是否为空

两个队列都没有数据时，栈才算为空。

为节省篇幅，这里用STL来模拟相应的数据结构。

参考程序：

#include<queue>
using namespace std;class MyStack {
public:MyStack() {size=0;}void push(int x) {//入栈if(!q2.empty()){q2.push(x);size++;}else{q1.push(x);size++;}}int pop() {//假设队列q1为空queue<int>*emptyQ=&q1,*noEmptyQ=&q2;if(!(*emptyQ).empty()){emptyQ=&q2;noEmptyQ=&q1;}//将非空队列的数据转移到空队列while((*noEmptyQ).size()>1){(*emptyQ).push((*noEmptyQ).front());(*noEmptyQ).pop();}int t=(*noEmptyQ).front();//获取栈顶元素(*noEmptyQ).pop();size--;return t;}int top() {//这里的操作和pop函数是一样的queue<int>*emptyQ=&q1,*noEmptyQ=&q2;if(!(*emptyQ).empty()){emptyQ=&q2;noEmptyQ=&q1;}while((*noEmptyQ).size()>1){(*emptyQ).push((*noEmptyQ).front());(*noEmptyQ).pop();}int t=(*noEmptyQ).front();(*noEmptyQ).pop();(*emptyQ).push(t);return t;}bool empty() {return size==0;}
private:queue<int>q1,q2;int size;
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

一个队列实现栈

假设我们只有一个队列q。

思路：

1. 入栈

假设我们要将数据x入队。

若队列q为空，则x正常入队。

若队列有数据，则先标记队列内的元素长度，再将x入队，最后将除了x的数据全部进行先出队再入队的操作，保证队首始终为后进的元素。

2. 出栈和获取栈顶元素

队列正常弹出队首即可。

3. 判断栈是否为空

直接判断队列是否为空即可。

参考程序：

#include<queue>
using std::queue;class MyStack {
public:void push(int x) {int num=q.size();//获取当前队列元素个数q.push(x);while(num--){//除了x都进行一次排队的操作int t=q.front();q.pop();q.push(t);}}//之后都是正常队列的操作int pop() {int t=q.front();q.pop();return t;}int top() {int t=q.front();return t;}bool empty() {return q.empty();}
private:queue<int>q;
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

5.4 用栈实现队列

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

两栈实现队列

模仿两队列实现栈的思路。

参考程序：

#include<stack>
using std::stack;class MyQueue {
public:MyQueue() {size=0;}void push(int x) {if(!s2.empty()){s2.push(x);size++;}else{s1.push(x);size++;}}int pop() {//找出空栈stack<int>*emptyS=&s1,*noEmptyS=&s2;if(!(*emptyS).empty()){emptyS=&s2;noEmptyS=&s1;}//获取栈顶元素while((*noEmptyS).size()>1){(*emptyS).push((*noEmptyS).top());(*noEmptyS).pop();}int t=(*noEmptyS).top();(*noEmptyS).pop();//这步使非空栈变为空size--;return t;}int peek() {stack<int>*emptyS=&s1,*noEmptyS=&s2;if(!(*emptyS).empty()){emptyS=&s2;noEmptyS=&s1;}while((*noEmptyS).size()>1){(*emptyS).push((*noEmptyS).top());(*noEmptyS).pop();}int t=(*noEmptyS).top();while((*emptyS).size()){//因为没有进行pop操作，需要将数据放回原栈(*noEmptyS).push((*emptyS).top());(*emptyS).pop();}return t;}bool empty() {return size==0;}
private:stack<int>s1,s2;int size;
};/*** Your MyCircularQueue object will be instantiated and called as such:* MyCircularQueue* obj = new MyCircularQueue(k);* bool param_1 = obj->enQueue(value);* bool param_2 = obj->deQueue();* int param_3 = obj->Front();* int param_4 = obj->Rear();* bool param_5 = obj->isEmpty();* bool param_6 = obj->isFull();*/

push栈和pop栈

1. 入队

一个栈用于实现数据入队操作，记为ins栈；另一个栈用于实现出队操作，记为outs栈。

2. 出队

若outs栈为空，则ins栈的数据全部压入outs栈再pop；

若outs栈非空，直接出栈即可。

3. 获取队首元素

套用出栈的思路即可。

或将出栈获取栈顶元素的步骤用于获取栈顶元素的函数的实现，出栈的函数调用获取栈顶元素的函数即可。

4. 判断队列是否为空

两个栈都为空，队列则为空。

参考程序：

class MyQueue {//一个栈用于push，一个栈用于pop
public:MyQueue() {size=0;}void push(int x) {//入栈ins.push(x);size++;}int pop() {//出栈int t=this->peek();outs.pop();size--;return t;}int peek() {//获取栈顶元素if(outs.empty()){while(ins.size()>1){outs.push(ins.top());ins.pop();}int t=ins.top();ins.pop();outs.push(t);//到这里，ins栈为空return t;}return outs.top();}bool empty() {return size==0;}
private:stack<int>ins,outs;int size;
};

一个栈实现队列

原则上一个栈是不可能实现完整的队列操作，至少需要两个栈。

但我们可以利用栈的特性，通过递归来暂时替代另一个栈的功能。

1. 入队

假设元素x为入队的元素。

若栈内没有元素，则x直接入栈。

若栈内有元素，则先取出栈顶元素进行保存，之后进行递归。直到栈空时，将x入栈。之后回溯的过程中将通过递归保存的数据重新放回栈。

2. 出队

正常弹出栈顶元素即可。

3. 获取队首元素

正常返回栈顶元素即可。

4. 判断队列是否为空

栈为空，队列则为空。

这里入队的每层递归时间复杂度都为$O(1)$，所有的$n$个数据都进行一次递归的话，时间复杂度为$O(n)$。

参考程序：

#include<stack>
using std::stack;class MyQueue {
public:void push(int x) {//栈为空则x入栈if(sk.empty()){sk.push(x);return;}int t=sk.top();sk.pop();push(x);sk.push(t);//回溯操作其实也用到了系统自带的栈}int pop() {int t=sk.top();sk.pop();return t;}int peek() {int t=sk.top();return t;}bool empty() {return sk.empty();}
private:stack<int>sk;
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/