刷题笔记——栈和队列互相冒充

- 5.3 用队列实现栈
- - 两队列实现栈
  - 一个队列实现栈
- 5.4 用栈实现队列
- - 两栈实现队列
  - push栈和pop栈
  - 一个栈实现队列

5.3 用队列实现栈

原OJ题：225. 用队列实现栈 - 力扣（LeetCode）
请添加图片描述

两队列实现栈

入栈的实现

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

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

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

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

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

判断队列是否为空

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

为节省篇幅，这里用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。

思路：

入栈

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

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

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

出栈和获取栈顶元素

队列正常弹出队首即可。

判断栈是否为空

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

参考程序：

#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栈

入队

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

出队

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

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

获取队首元素

套用出栈的思路即可。

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

判断队列是否为空

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

参考程序：

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;
};

一个栈实现队列

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

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

入队

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

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

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

出队

正常弹出栈顶元素即可。

获取队首元素

正常返回栈顶元素即可。

判断队列是否为空

栈为空，队列则为空。

这里入队的每层递归时间复杂度都为 $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();
 */