摘要:解决方案二入队都在中进行,用于队列,同时保证所有元素都在一个栈里,且遵循以下约束入队不管空与否,都将中的所有元素压入中出队若中不为空,则直接从中弹出元素若为空,则说明队列为空,不能出队。
声明:码字不易,转载请注明出处,欢迎文章下方讨论交流。
前言:Java数据结构与算法专题会不定时更新,欢迎各位读者监督。本篇文章介绍一个有趣的问题:用两个栈实现一个队列。这道题来自互联网公司的算法面试,作为一道经典的算法面试题,本文给出问题的解决思路和Java实现代码。
前两篇文章介绍了栈(stack)和队列(queue)两种特殊的数据结构和他们特点,栈和队列虽然是特点针锋相对的,但有意思的是他们却彼此相互联系。
后进先出的栈如何才能实现先进先出的队列呢?一般会用两个栈来实现。首先定义两个栈分别为stack1和stack2.
1.解决方案一:我们让入队的操作在stack1中完成,出队的操作在stack2中完成,具体分析过程如下:
入队: ①将所有元素直接向stack1中压栈
出队: ②将stack1中的所有元素依次出栈,③紧接着入栈到stack2中,④然后弹出stack2中的元素。
为清楚说明,用下图解释:
来回入队、出队比较麻烦,尤其是出队比较麻烦,需要先将元素从stack1倒入stack2中,然后stack2弹出的元素又倒回到stack1中。有没有更优化的方案呢?以下方案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代码实现,后续会给出其姊妹篇如何用两个队列实现栈?的问题。
欢迎下方讨论提问,觉得文章对您有用,请收藏点个赞 ^_^
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/76361.html
摘要:基本解决方案按照上述的大体思路,我们给出解决方案入栈和出栈都在中完成,只作为临时中转空间。入栈入队出栈除队尾的元素外将其他所有元素出队,再入队中转暂存,然后将中的元素出队出栈。 声明:码字不易,转载请注明出处,欢迎文章下方讨论交流。 前言:Java数据结构与算法专题会不定时更新,欢迎各位读者监督。本篇介绍的是如何用两个队列实现栈的问题。这道题作为上一篇文章算法面试:栈实现队列的方案的姊...
摘要:如问到是否使用某框架,实际是是问该框架的使用场景,有什么特点,和同类可框架对比一系列的问题。这两个方向的区分点在于工作方向的侧重点不同。 [TOC] 这是一份来自哔哩哔哩的Java面试Java面试 32个核心必考点完全解析(完) 课程预习 1.1 课程内容分为三个模块 基础模块: 技术岗位与面试 计算机基础 JVM原理 多线程 设计模式 数据结构与算法 应用模块: 常用工具集 ...
摘要:题目编写一个类,用两个栈实现队列,支持队列的基本操作,,代码实现 【题目】编写一个类,用两个栈实现队列,支持队列的基本操作(add,poll,peek) 代码实现 public class TwoStacksQueue { private Stack stackPush; private Stack stackPop; public TwoStacksQue...
摘要:总结的时间复杂度是,是空间是使用辅助栈来存储最小值。项目就是为了解决配置繁琐的问题,最大化的实现约定大于配置。 前言 只有光头才能变强 Redis目前还在看,今天来分享一下我在秋招看过(遇到)的一些面试题(相对比较常见的) 0、final关键字 简要说一下final关键字,final可以用来修饰什么? 这题我是在真实的面试中遇到的,当时答得不太好,现在来整理一下吧。 final可以修饰...
阅读 3050·2021-11-24 10:24
阅读 2838·2021-11-11 16:54
阅读 3038·2021-09-22 15:55
阅读 2010·2019-08-30 15:44
阅读 1877·2019-08-29 18:41
阅读 2684·2019-08-29 13:43
阅读 3026·2019-08-29 12:51
阅读 1109·2019-08-26 12:19