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

dabai 发布于2019-08-16 11:06 / 1064人阅读

摘要：基本解决方案按照上述的大体思路，我们给出解决方案入栈和出栈都在中完成，只作为临时中转空间。入栈入队出栈除队尾的元素外将其他所有元素出队，再入队中转暂存，然后将中的元素出队出栈。

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

前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇介绍的是如何用两个队列实现栈的问题。这道题作为上一篇文章算法面试：栈实现队列的方案的姊妹篇（也是一道思路拓展题），本文给出问题的解决思路和Java实现代码。

首先定义两个队列分别为queue1和queue2。

1.大体思路：

队列实现栈，栈的特点是后进的先出，我们可以让元素入队queue1，留下队尾元素让其他元素出队，暂存到queue2中，然后让queue1中剩下的元素出队，即最后进的最先出来。

2.基本解决方案

按照上述的大体思路，我们给出解决方案：入栈和出栈都在queue1中完成，queue2只作为临时中转空间。

入栈入队queue1

出栈除queue1队尾的元素外将其他所有元素出队queue1，再入队queue2（中转暂存），然后将queue1中的元素出队（出栈）。最后一步，将暂存在queue2中的元素再倒回queue1中。

为描述清晰，请看下图：
事实上，这个思路和用两个栈实现队列的方案1类似，都是第二个数据区作为暂存中转，最后在倒回到第一个数据区。

3.改进后的方案

上述方案是一个基本的最容易想到的解决方案，但是仔细观察会发现其并不完美：在每次出栈步骤中要把queue2中的元素倒回到queue1中，这个操作很累赘，能否优化一下，可不可以不用每次先出栈后倒回？？下面给出改进后的方案

入栈：

两个队列全空：任选一个队列让元素入队，此处规定queue1

两个队列一个空：让元素入队非空的队列

注：不考虑两个队列全满，因为本身没意义

出栈： 将非空队列中除最后入队的元素之外的其他所有元素入队到另外一个队列中，然后出队剩下的那个元素（后进来的先出去，完成出栈）

相比于基本方案，改进后的方案没有了基本方案中的倒回操作，整个流程变得简洁高效，下面给出改进方案的java代码实现。

4.java代码实现

public class Queues2Stack {
    private ArrayQueue q1;
    private ArrayQueue q2;
    private int maxLength;
    
    public Queues2Stack(int capacity){
        maxLength = capacity;
        q1 = new ArrayQueue(capacity);
        q2 = new ArrayQueue(capacity);
    }
    
    public int getSize(){
        return q1.getsize()+q2.getsize();
    }
    
    /**
     * 入栈：
     * @param element 入栈元素
     * @return 入栈成功结果？
     */
    public boolean push(int element){
        if(getSize() == maxLength){ //队列都满，此情景无意义
            return false;
        }
        if(q2.isEmpty()){
            q1.put(element);
        }else{
            q2.put(element);
        }
        return true;
    }
    
    /**
     * 出栈
     * @return 出栈元素
     */
    public Object pop(){
        if(getSize()==0){
            throw new IndexOutOfBoundsException("空栈，无元素可出栈");
        }else{   //留非空队列中最后一个元素，其他搬到空队列中
            if(q2.isEmpty()){  
                while(q1.getsize()>1) q2.put(q1.pull()); 
                return q1.pull();  //出队最后一个，实现后进先出
            }else{
                while(q2.getsize()>1) q1.put(q2.pull());
                return q2.pull();   //出队最后一个，实现后进先出
            }
        }
    }
}

测试程序：

public class Queues2StackTest {
    public static void main(String[] args) {
        Queues2Stack s = new Queues2Stack(5);
        s.push(1);
        s.push(2);
        s.push(3);
        System.out.println(s.pop());  //返回3
        s.push(4);
        s.push(5);
        System.out.println(s.pop());  //返回5
        System.out.println(s.pop());  //返回4
        System.out.println(s.pop());  //返回2
        System.out.println(s.pop());  //返回1
        System.out.println(s.pop());  //抛出异常：提示栈为空
    }
}

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

本篇的姊妹篇请移步到之前的文章算法面试：栈实现队列的方案

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

云服务器 GPU云服务器栈的实现与应用栈和队列面试题 java 栈队列面试队列实现原理

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

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

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

摘要：解决方案二入队都在中进行，用于队列，同时保证所有元素都在一个栈里，且遵循以下约束入队不管空与否，都将中的所有元素压入中出队若中不为空，则直接从中弹出元素若为空，则说明队列为空，不能出队。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇文章介绍一个有趣的问题：用两个栈实现一个队列。这道题来自互联网公司的算法面试...

韩冰 2019-08-19 10:43 评论0 收藏0
Java 高级面试知识点汇总！

摘要：适配器模式将一个类的接口转换成客户希望的另外一个接口。适配器模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。这个主题对象在状态发生变化时，会通知所有观察者对象，使它们能够自动更新自己。 1、常用设计模式单例模式：懒汉式、饿汉式、双重校验锁、静态加载，内部类加载、枚举类加载。保证一个类仅有一个实例，并提供一个访问它的全局访问点。代理模式：动态代理和静态代理，什么时候使用...

since1986 2019-08-16 12:33 评论0 收藏0
【Java】几道常见的秋招面试题

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

Rocko 2019-08-16 13:29 评论0 收藏0
前端进击的巨人（二）：栈、堆、队列、内存空间

摘要：中有三种数据结构栈堆队列。前端进击的巨人一执行上下文与执行栈，变量对象中解释执行栈时，举了一个乒乓球盒子的例子，来演示栈的存取方式，这里再举个栗子搭积木。对于基本类型，栈中存储的就是它自身的值，所以新内存空间存储的也是一个值。面试经常遇到的深浅拷贝，事件轮询，函数调用栈，闭包等容易出错的题目，究其原因，都是跟JavaScript基础知识不牢固有关，下层地基没打好，上层就是豆腐渣工程，...

edgardeng 2019-08-23 14:43 评论0 收藏0
PHP面试知识梳理

摘要：三次握手所谓三次握手，是指简历一个连接时需要客户端和服务器总共发送三个包三次握手的目的是连接服务器指定端口，简历连接，并同步连接双方的序列号并交换窗口大小信息。关于作者昨天在思否上发了这篇整理，晚上10点多看到了很多赞收藏和关注，其实挺愧疚的，因为最近在找工作这篇文章并没有整理完。看到这个还挺受欢迎的，也因为新工作基本定下来了，现在的公司正常交接中，打算下周末之前把这个知识梳理整理...

archieyang 2019-06-28 18:33 评论0 收藏0