用栈实现队列

文章目录

• 题目介绍
• 思路分析
• 代码实现
  • C语言版本
  • C++版本

上一篇文章我们讲解了如何用队列实现栈，那这篇文章我们再来看一个兄弟题目——用栈实现队列

题目介绍

链接: link

在这里插入图片描述

仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

思路分析

那我们来分析一下这道题又该怎么实现。

思路是这样的：

让我们用两个栈来实现

在这里插入图片描述

我们把其中一个栈命名为pushstack，只用来入数据（队尾入数据），另一个命名为popstack，只用来出数据（对头出数据） 比如我们现在入队列1 2 3 4，那就永远都是往pushstack里面入

在这里插入图片描述

那然后我现在想出队列元素，应该出几啊？ 🆗，队列是先进先出，所以现在出队列应该是出1，但是1现在在pushstack的栈底，那怎么办呢？ 那就又需要导数据了，我们可以把pushstack的元素全部导入到popstack中

在这里插入图片描述

因为栈上后进先出，所以导入到popstack之后从顶到底就是1 2 3 4，顺序跟之前在pushstack里面就反了。 但是此时我们去出栈顶的元素，不就符合队列先进先出的顺序了嘛，1 2 3 4，这跟之前入队列的顺序正好是一样的。 所以此时把1从popstack里面pop掉，就等同于1出队列了

在这里插入图片描述

那然后我要继续入数据呢？ 那就还是往pushstack里面入就行了 比如再入队列5 6

在这里插入图片描述

然后再出队列呢？ 刚才出队列元素的时候我们把pushstack的元素全部导入到popstack中，那现在还需要导数据吗？ 🆗，我们看到是不需要的，我们继续出popstack里面的元素这个顺序就是对的啊。 再出队列3次，2 3 4，那这顺序都是对的

在这里插入图片描述

那此时pop为空了，我要再想出队列数据怎么办？ 是不是又需要把pushstack的元素再全部导入到popstack中，然后再去出popstack栈顶的元素，这个顺序是对的。 所以，总结一下： 队尾入数据的时候，永远把数据入到pushstack里面； 队头出数据的时候，要判断一下：如果popstack不为空，直接出栈popstack栈顶的元素即可，如果popstack为空，那就先把pushstack的元素再全部导入到popstack中，然后再去出popstack栈顶的元素。

那我们来看一下题目让我们实现哪几个接口：

在这里插入图片描述

首先push——队尾入数据： 上面分析过了，队尾入数据的时候，永远把数据入到pushstack里面 然后我们先来看这个——peek：返回队头元素 跟上面分析的pop是一样的思路，如果popstack不为空，popstack栈顶的元素就是队头元素，如果popstack为空，先把pushstack的元素再全部导入到popstack中，然后再返回popstack栈顶的元素。 接着来看——pop：移除队头元素并返回 那这个其实就可以复用上面的peek函数，先调用一下peek接口，获取popstack栈顶的元素即队头元素作为返回值，当然返回之前再去pop掉popstack栈顶元素即可（调完peek之后直接pop，无需判断popstack为空，因为如果为空的话peek函数里面也会把pushstack的元素再全部导入到popstack中） 最后——empty：判空 两个栈都为空就是队列为空

代码实现

C语言版本

C语言实现的话，还是要自己造轮子，这里我就直接拷贝之前写过的栈：

在这里插入图片描述

接着是本题的代码实现：

在这里插入图片描述

在这里插入图片描述

然后

在这里插入图片描述

就过啦

C++版本

C++就可以直接用STL里面的stack，无需造轮子：

在这里插入图片描述

在这里插入图片描述

class MyQueue {
public:
    MyQueue() {}
    
    void push(int x) {
        pushstack.push(x);
    }
    
    int pop() {
        int top=peek();
        popstack.pop();
        return top;
    }

    int peek() {
        if(popstack.empty())
        {
            while(!pushstack.empty())
            {
                popstack.push(pushstack.top());
                pushstack.pop();
            }
        }
        return popstack.top();
    }
    
    bool empty() {
        return pushstack.empty()&&popstack.empty();
    }
private:
    stack<int> pushstack;
    stack<int> popstack;
};