用两个队列实现栈

╰+哭是因爲堅強的太久メ 2023-06-02 10:51 87阅读 0赞

首先，明白了栈和队列的特点之后，就发现用队列来实现栈和用栈来实现队列的思想差不多是一样的。队列的特点是先进先出，栈的特点是先进先出，用队列来实现栈，即使用队列来完成先进后出的操作。

和用栈实现队列一样，我们假设需要操作的数据为A、B、C、D、E。有两个队列queue1和queue2，和用栈实现队列不同的是，此两个队列没有严格的插入和删除之分，栈实现队列时，我们使用主栈来压栈，辅助栈来弹栈。首先我们将元素A、B、C、D依次进入队列queue1中，此时队首元素为A，队尾元素为D。queue2此时为空。接下来我们需要进行出队操作，按照栈的特点，首先需要出栈的元素是D，但是由于此时数据存储在队列里，而按照队列的规则，此时不能直接出队元素D。那么需要做的就是把queue1中的A、B、C元素依次出队并进入队列queue2中，此时，queue1中只有一个元素D，便能进行直接删除操作了，而queue2中的元素有ABC，且A为队首元素，C为队尾元素。接着继续删除，很明显，我们需要删除的是元素C。那么此时元素C位于队列queue2的队尾，不能直接删除。仿照删除元素D的方法，先将queue2中的元素A、B依次出队并进入队列queue1中，此时queue2中只有一个元素C，可直接进行出队操作，达到删除的目的，queue1中的元素有A、B，A为队首，B在队尾。接着再删除元素B。删除元素B之后，队列queue1为空，queue2中只有元素A。此时，我们如果再让元素E入队的话呢？元素E应该进入哪个队列呢？

其实，此时队列queue1为空，queue2只有一个元素A，此时插入元素E的时候不管哪个队列都可以插入。通常我们选择非空队列，即queue2。此时，若想继续删除的话，则要将queue2中的元素A出队并进入队列queue1中，删除元素E，之后再删除A。图示如下：

（1）最开始的时候，我们先将元素A、B、C、D依次入队queue1中，A为队首元素，D为队尾元素，此时栈中的元素也为A、B、C、D，而queue2中暂时为空。

![20191004194816102.png][]

（2）之后进行删除操作。按照栈的先进后出的规则，我们需要先删除元素D，但是此时队列queue1中D在队尾，不能直接进行出队操作，所以此时我们需要借助队列queue2来使得元素D到达某个队列的队首，这样就能进行出队操作已达到删除的目的。按照同样的规则，依次删除元素D、C、B。完成之后，队列中只有一个元素A了，而此时元素A在队列queue2中。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70][]

（3）接下来我们考虑此时插入元素E。按照插入的原则，元素E应该进入到非空队列队列queue2中。

![201910042000137.png][]

（4）接下来再考虑删除元素的话，需删除元素E。按照相同的规则，将queue2中的队首元素A出队并进入到队列queue1中，然后对queue2中的元素E执行出队操作。接下来也可直接删除元素A。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 1][]

相关代码如下：

queue<int> queue1;
    queue<int> queue2;
    void push(int x)
    {
        queue1.push(x);
    }
    
    int pop()
    {
        int temp = 0;
        if (!queue1.empty())
        {
    	while (queue1.size() > 1)
    	{
    	    temp = queue1.front();
    	    queue1.pop();
    	    queue2.push(temp);
    	}
    	if (queue1.size() == 1)
    	{
    	    temp = queue1.front();
    	    queue1.pop();
    	}
        }
        else
        {
    	while (queue2.size() > 1)
    	{
    	    temp = queue2.front();
    	    queue2.pop();
    	    queue1.push(temp);
    	}
    	if (queue2.size() == 1)
    	{
    	    temp = queue2.front();
    	    queue2.pop();
    	}
        }
        return temp;
    }
    
    int top()
    {
        int temp = 0;
        if (!queue1.empty())
        {
    	while (queue1.size() > 1)
    	{
    	    temp = queue1.front();
    	    queue2.push(temp);
    	}
    	if (queue1.size() == 1)
    	{
    	    temp = queue1.front();
    	    queue1.pop();
    	}
        }
        else
        {
    	while (queue2.size() > 1)
    	{
    	    temp = queue2.front();
    	    queue2.pop();
    	    queue1.push(temp);
    	}
    	if (queue2.size() == 1)
    	{
    	    temp = queue2.front();
    	}
        }
        return temp;
    }
    
    bool empty()
    {
        if (queue1.empty() && queue2.empty())
        {
    	return true;
        }
        else
        {
    	return false;
        }
    }

**参考文章：**[https://blog.csdn.net/cherrydreamsover/article/details/80466781][https_blog.csdn.net_cherrydreamsover_article_details_80466781]

[20191004194816102.png]: /images/20230601/b252f47807a54968ad16aafa846f4cf7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70]: /images/20230601/40f848ea027145c2a7ce4d389eba1ed4.png
[201910042000137.png]: /images/20230601/970084771fc7414185609b985cc9c25f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 1]: /images/20230601/e310008c692744f7965266ef9e20e0e1.png
[https_blog.csdn.net_cherrydreamsover_article_details_80466781]: https://blog.csdn.net/cherrydreamsover/article/details/80466781

发表评论取消回复

表情：

评论列表（有 0 条评论，87人围观）

还没有评论，来说两句吧...

相关阅读

相关用两个栈实现队列

文章目录题目描述代码题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。代码 stack1用

清疚/ 2024年02月19日 13:04/ 0 赞/ 68 阅读

相关用两个栈实现队列

题目描述用两个栈来实现一个队列，完成队列的Push和Pop操作. 队列中的元素为int类型. 解题思路栈：先入后出队列：先入先出此时我们有俩个栈，

不念不忘少年蓝@/ 2023年07月07日 03:57/ 0 赞/ 3 阅读

相关用两个队列实现栈

首先，明白了栈和队列的特点之后，就发现用队列来实现栈和用栈来实现队列的思想差不多是一样的。队列的特点是先进先出，栈的特点是先进先出，用队列来实现栈，即使用队列来完成先进后出的操

╰+哭是因爲堅強的太久メ/ 2023年06月02日 10:51/ 0 赞/ 88 阅读

相关用两个栈实现队列

我们知道，栈的特点是先进后出，而队列的特点是先进先出，那么如何用先进后出的栈来完成队列的先进先出的操作呢？很明显，用一个栈是不能实现的，因此我们需要一个辅助栈来配合主栈完成。

曾经终败给现在/ 2023年06月02日 09:15/ 0 赞/ 128 阅读

相关用两个栈实现队列

package com.zhiru; import java.util.Stack; / 用两个栈实现队列 /

分手后的思念是犯贱/ 2022年08月12日 01:30/ 0 赞/ 332 阅读

相关用两个栈实现队列

> 牛客网《剑指offer》时间限制：`1秒` 空间限制：`32768K` 热度指数：`145526` 本题知识点： `队列` `栈` 题目描述用两个栈来实现一

悠悠/ 2022年06月08日 02:38/ 0 赞/ 265 阅读

相关用两个栈实现队列

链接： [https://www.nowcoder.com/questionTerminal/54275ddae22f475981afa2244dd448c6][https_w

- 日理万妓/ 2022年06月05日 10:36/ 0 赞/ 236 阅读

相关用两个栈实现队列和两个队列实现栈

用两个栈实现队列，完成队列的Push和Pop操作。队列中的元素为int类型。分析：栈是先进后出，队列是先进先出。用两个栈实现队列，栈1入栈，栈2出栈，就是队列的顺序了

以你之姓@/ 2022年04月24日 15:02/ 0 赞/ 318 阅读

相关用两个栈实现队列

时间限制：1秒空间限制：32768K 热度指数：346516 本题知识点：队列栈算法知识视频讲解题目描述用两个栈来实现一个队列，完成队列的Push和

末蓝、/ 2022年03月11日 20:51/ 0 赞/ 281 阅读

相关剑指offer：用两个栈实现队列用两个队列实现栈

试题：用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。代码：首先显然要有个stack用来push，由于stack的后进后出

曾经终败给现在/ 2021年09月16日 06:30/ 0 赞/ 419 阅读