用两个栈实现队列

曾经终败给现在 2023-06-02 09:15 112阅读 0赞

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

假设我们先把元素A、B、C、D压栈压到主栈stack1中，那么此时主栈中的元素就为\{A，B，C，D\}，其中A为栈底元素，D为栈顶元素。如果此时我们需要删除元素，按照队列先进先出的原则，我们应该删除元素A，但此时元素A位于主栈的栈底，很明显不能直接删除，这时候我们就需要使用辅助栈stack2来完成。如果我们依次把主栈stack1中的元素弹出并压栈到辅助栈stack2中，则经过四次弹栈与压栈的操作后，元素在stack2中的顺序恰好和stack1中的顺序相反，即栈顶元素为A，栈底元素为D，而主栈stack1为空，这个时候我们就可以弹出辅助栈栈顶的元素A了，达到了删除的目的。删除之后，辅助栈中的元素为\{B，C，D\}，栈顶元素为B，主栈仍然为空。此时如果我们想继续删除元素的话，我们发现，由于在压栈的时候，B比C更先进入，而且根据队列先进先出的规则，我们自然而然要先删除元素B了，而此时在辅助栈stack2中，元素B正好位于栈顶，则直接删除即可，删除后辅助栈的元素为\{C，D\}，主栈仍然为空。还想继续删除元素的话操作也一样。

由此我们发现删除元素的步骤：当辅助栈stack2中不为空时，在stack2中的栈顶元素是最先进入队列的元素，那么就可以直接弹栈删除。如果stack2为空时，我们需要把主栈stack1中的元素逐个弹栈并压入stack2中。由于先进队列的元素被压到stack1的底部，经过弹出和压入操作之后就处于stack2的顶端了，就可以直接弹出。

那如果此时我们还需要继续插入元素E呢？同样的，将元素E压入主栈stack1中，此时主栈中只有一个元素\{E\}，辅助栈stack2中仍然有元素\{C，D\}。当下一次我们考虑删除队列头部元素的时候，发现C和D比E都先进入队列，则直接在辅助栈stack2中弹栈即可，在删除元素E之前，C和D都应该在此之前删除。

图解为：

（1）首先将元素A，B，C，D压栈入主栈stack1中，辅助栈stack2暂时为空。压栈后的主栈中，栈顶元素为D，栈底元素为A。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70][]

（2）接下来准备删除元素。删除元素之前先把stack1中的元素依次弹栈并压入stack2中。然后依次删除A和B元素。由于删除队列首元素A的时候，A刚好位于stack2的顶部，则直接弹栈即可。接着再想删除队列首元素的时候发现此时的队列首元素B也刚好位于stack2的顶部，也直接弹栈即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 1][]

（3）此时我们再看另一种情况，即如果想再插入元素的话。看是否插入之后再删除的话是否会有矛盾。如下图所示，我们发现，插入元素的时候仍然将元素压入主栈stack1中，此时并不影响后续删除队列元素的弹栈操作。

![20191004135957769.png][]

相关代码如下：

class Solution
    {
    public:
        //入队操作
        void push(int element)
        {
    	stack1.push(element);
        }
        //出队操作
        int pop()
        {
    	//如果辅助栈为空，则将stack1中元素依次弹出并压入此栈中
    	if (stack2.empty())
    	{
    	    while (!stack1.empty())
    	    {
    		stack2.push(stack1.top());
    		stack1.pop();
    	    }
    	}
    	if (stack2.empty())
    	{
    	    cout << "Stack2 is empty!" << endl;
    	}
    	int head = stack1.top();
    	stack2.pop();
    	return head;
        }
    private:
        stack<int> stack1;
        stack<int> stack2;
    };

完整代码如下：

queue.h
    
    #include <iostream>
    #include <stack>
    using namespace std;
    class Queue
    {
    private:
        stack<int> stack1;		//主栈
        stack<int> stack2;		//辅助栈
    public:
        //入队操作
        void Push(int element);
        //出队操作
        void Pop();
        //返回队首元素
        int Front();
        //返回队尾元素
        int Back();
        //判断队列是否为空
        bool Empty();
        //返回队列大小
        int Size();
    };
    
    queue.cpp
    
    #include "queue.h"
    
    //入队
    void Queue::Push(int element)
    {
        //主栈stack1作队列的队尾，stack2作为队列的队头
        stack1.push(element);
        cout << element << " ";
    }
    
    //出队
    void Queue::Pop()
    {
        while (!stack1.empty())
        {
    	int element = stack1.top();
    	stack2.push(element);
    	stack1.pop();
        }
        stack2.pop();
    }
    
    //返回队首元素
    int Queue::Front()
    {
        while (!stack1.empty())
        {
    	stack2.push(stack1.top());
    	stack1.pop();
        }
        int temp = stack2.top();
        while (!stack2.empty())
        {
    	int x = stack2.top();
    	stack1.push(x);
    	stack2.pop();
        }
    return temp;
    }
    
    //返回队尾元素
    int Queue::Back()
    {
        return stack1.top();
    }
    
    //判断队列是否为空
    bool Queue::Empty()
    {
        if (stack1.empty() && stack2.empty())
        {
    	return true;
        }
        else
        {
    	return false;
        }
    }
    
    //返回队列大小
    int Queue::Size()
    {
        return stack1.size() + stack2.size();
    }
    
    int main()
    {
        Queue q;
        cout << "入队操作，插入到队列的元素分别是：";
        q.Push(1);
        q.Push(2);
        q.Push(3);
        q.Push(4);
        q.Push(5);
        q.Push(6);
        cout << endl;
        cout << "队列是否为空：";
        if (q.Empty())
        {
    	cout << "是" << endl;
        }
        else
        {
    	cout << "否" << endl;
        }
        cout << "队首元素是：" << q.Front() << endl;
        cout << "队尾元素是：" << q.Back() << endl;
        cout << "队列大小为：" << q.Size() << endl;
        cout << "出队操作：" << endl;
        q.Pop();
        cout << endl;
        return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 2][]

更多详细内容还请访问[https://blog.csdn.net/lixiaogang\_theanswer/article/details/72539997][https_blog.csdn.net_lixiaogang_theanswer_article_details_72539997]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70]: /images/20230601/24926995879546c4994881a8b0312478.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 1]: /images/20230601/2816a8b8fd3f4625a1d43089535e188f.png
[20191004135957769.png]: /images/20230601/9f45b098a5a64bb983db268e8128b017.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW9tdWJhaQ_size_16_color_FFFFFF_t_70 2]: /images/20230601/07383b7ea6664c5ba508ae7578c4c239.png
[https_blog.csdn.net_lixiaogang_theanswer_article_details_72539997]: https://blog.csdn.net/lixiaogang_theanswer/article/details/72539997

发表评论取消回复

表情：

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

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

相关阅读

相关用两个栈实现队列

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

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

相关用两个栈实现队列

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

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

相关 python：用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有

Dear 丶/ 2022年11月12日 13:42/ 0 赞/ 184 阅读

相关 [数据结构][Python]用两个栈实现队列与用两个队列实现栈

题目用栈模拟一个队列，实现入队、出队解决方案让元素1入队 <table> <thead> <tr> <th>栈A</th> <t

àì夳堔傛蜴生んèń/ 2022年10月02日 15:55/ 0 赞/ 228 阅读

相关用两个栈实现队列

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

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

相关用两个栈实现队列

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

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

相关用两个栈实现队列

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

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

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

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

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

相关用两个栈实现队列

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

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

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

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

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