算法面试：栈实现队列的方案

韩冰发布于2019-08-19 10:43 / 2522人阅读

摘要：解决方案二入队都在中进行，用于队列，同时保证所有元素都在一个栈里，且遵循以下约束入队不管空与否，都将中的所有元素压入中出队若中不为空，则直接从中弹出元素若为空，则说明队列为空，不能出队。

声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。

前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇文章介绍一个有趣的问题：用两个栈实现一个队列。这道题来自互联网公司的算法面试，作为一道经典的算法面试题，本文给出问题的解决思路和Java实现代码。

前两篇文章介绍了栈(stack)和队列（queue）两种特殊的数据结构和他们特点，栈和队列虽然是特点针锋相对的，但有意思的是他们却彼此相互联系。

后进先出的栈如何才能实现先进先出的队列呢？一般会用两个栈来实现。首先定义两个栈分别为stack1和stack2.

1.解决方案一：

我们让入队的操作在stack1中完成，出队的操作在stack2中完成，具体分析过程如下：

入队： ①将所有元素直接向stack1中压栈

出队： ②将stack1中的所有元素依次出栈，③紧接着入栈到stack2中，④然后弹出stack2中的元素。

为清楚说明，用下图解释：

来回入队、出队比较麻烦，尤其是出队比较麻烦，需要先将元素从stack1倒入stack2中，然后stack2弹出的元素又倒回到stack1中。有没有更优化的方案呢？以下方案2是改进之后的思路。

2.解决方案二：

入队都在stack1中进行，stack2用于队列，同时保证所有元素都在一个栈里，且遵循以下约束：

入队：不管stack1空与否，都将stack2中的所有元素压入stack1中

出队：若stack2中不为空，则直接从stack2中弹出元素；若stack2为空，则说明队列为空，不能出队。

方案2与方案1的区别在于，方案2中把倒回的操作放在了入队中完成，使连续入队、出队的效率提高。有没有更优化的方案呢？以下对方案2改进，给出方案3.

3.解决方案三：

入队都在stack1中完成，出队都在stack2中完成，且遵循以下约束：

入队：直接把元素压入stack1中；

出队：若stack2中不为空，则直接弹出stack2中的元素；若stack2中为空，则将stack1中的所有元素倒入stack2中，然后弹出stack2的栈顶元素。同样，若两个栈都为空，则队列为空队，无法出队。

方案3的特点是：入队时非常简单，而在出队时，多数情况下可以直接通过弹出stack2完成。如果把stack1中的元素倒入stack2中，则一般不用每次都进行这样的操作。最坏的情况就是出队一个元素、入队一个元素这样的循环，导致每次出队都需要转移元素。

4.java代码实现

以下给出方案3的代码实现：

public class Stacks2Queue {
    private Stack stack1;
    private Stack stack2;
    private int maxLength;
    
    public Stacks2Queue(int capacity){
        maxLength = capacity;
        stack1 = new Stack(capacity);        
        stack2 = new Stack(capacity);        
    }
    
    /**
     * 队列入队
     * @param element 入队元素
     * @return 入队成功？
     */
    public boolean put(int element){
        if(stack1.isFull() || maxLength == stack1.getSize()){
            //此时stack1满
            return false;
        }
        stack1.push(element);
        return true;
    }
    
    /**
     * 队列出队
     * @return 出队的元素
     */
    public int poll(){
        if(!stack2.isEmpty()){
            return stack2.pop();
        }else{
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }return stack2.pop();
        }
    }
    
    /**
     * 求队列长度
     * @return 返回队列长度
     */
    public int getSize(){
        return stack1.getSize()+stack2.getSize();
    }
}

测试代码如下：

public class Stack2QueueTest {
    public static void main(String[] args) {
        Stacks2Queue q = new Stacks2Queue(5);
        q.put(1);   //入队元素 1
        q.put(2);   //入队元素 2
        System.out.println("出队的元素为"+q.poll());   //出队元素   打印1
        System.out.println("此时队列长度为"+q.getSize());  //返回1
        q.put(3);   //入队元素 3
        q.put(4);   //入队元素 4
        System.out.println("出队的元素为"+q.poll());   //出队元素  打印2
        System.out.println("出队的元素为"+q.poll());   //出队元素  打印3 本次出队操作会把3和4两个元素从stack1中倒入stack2中
    }
}

注：以上代码用到了堆和栈的代码，请移步到前两篇文章获取Java数据结构与算法——栈(stack)和Java数据结构与算法——队列（queue） 5.小结：

本文介绍了一个互联网面试经典问题如何用两个栈实现队列？并给出解决思路和java代码实现，后续会给出其姊妹篇如何用两个队列实现栈？的问题。

欢迎下方讨论提问,觉得文章对您有用，请收藏点个赞 ^_^

私有云云服务器 java 栈队列面试消息队列的实现栈面试题 java 栈队列

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76361.html

算法面试：队列实现栈的方案

摘要：基本解决方案按照上述的大体思路，我们给出解决方案入栈和出栈都在中完成，只作为临时中转空间。入栈入队出栈除队尾的元素外将其他所有元素出队，再入队中转暂存，然后将中的元素出队出栈。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇介绍的是如何用两个队列实现栈的问题。这道题作为上一篇文章算法面试：栈实现队列的方案的姊...

dabai 2019-08-16 11:06 评论0 收藏0
Java面试 32个核心必考点完全解析

摘要：如问到是否使用某框架，实际是是问该框架的使用场景，有什么特点，和同类可框架对比一系列的问题。这两个方向的区分点在于工作方向的侧重点不同。 [TOC] 这是一份来自哔哩哔哩的Java面试Java面试 32个核心必考点完全解析（完）课程预习 1.1 课程内容分为三个模块基础模块：技术岗位与面试计算机基础 JVM原理多线程设计模式数据结构与算法应用模块：常用工具集 ...

JiaXinYi 2019-08-16 16:53 评论0 收藏0
【面试算法】由两个栈组成的队列

摘要：题目编写一个类，用两个栈实现队列，支持队列的基本操作，，代码实现【题目】编写一个类，用两个栈实现队列，支持队列的基本操作（add，poll，peek）代码实现 public class TwoStacksQueue { private Stack stackPush; private Stack stackPop; public TwoStacksQue...

wenshi11019 2019-08-14 15:17 评论0 收藏0
【Java】几道常见的秋招面试题

摘要：总结的时间复杂度是，是空间是使用辅助栈来存储最小值。项目就是为了解决配置繁琐的问题，最大化的实现约定大于配置。前言只有光头才能变强 Redis目前还在看，今天来分享一下我在秋招看过(遇到)的一些面试题(相对比较常见的) 0、final关键字简要说一下final关键字，final可以用来修饰什么？这题我是在真实的面试中遇到的，当时答得不太好，现在来整理一下吧。 final可以修饰...

Rocko 2019-08-16 13:29 评论0 收藏0