用jsp做网站的难点,深圳网站建设的基本知识,企业logo设计规范,清远佛冈住房和城乡建设局网站声明#xff1a;码字不易#xff0c;转载请注明出处#xff0c;欢迎文章下方讨论交流。前言#xff1a;Java数据结构与算法专题会不定时更新#xff0c;欢迎各位读者监督。本篇介绍的是如何用两个队列实现栈的问题。这道题作为上一篇文章算法面试#xff1a;栈实现队列的…声明码字不易转载请注明出处欢迎文章下方讨论交流。前言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()); //返回3s.push(4);s.push(5);System.out.println(s.pop()); //返回5System.out.println(s.pop()); //返回4System.out.println(s.pop()); //返回2System.out.println(s.pop()); //返回1System.out.println(s.pop()); //抛出异常提示栈为空}}本篇的姊妹篇请移步到之前的文章算法面试栈实现队列的方案欢迎讨论提问,觉得文章对您有用请收藏点个赞 ^_^
