博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
使用两个队列实现一个栈
阅读量:5948 次
发布时间:2019-06-19

本文共 1825 字,大约阅读时间需要 6 分钟。

如图所示,我们先往栈内压入一个元素a。由于两个队列现在都是空,我们可以选择把a插入两个队列中的任一个。我们不妨把a插入queue1。接下来继续网栈内压入b,c两个元素。我们把它们都插入queue1。这个时候 queue1包含3个元素a,b,c其中a位于队列的头部,c位于队列的尾部。

现在我们考虑从栈内弹出一个元素。根据栈的后入先出的原则,最后被压入栈的c应该最先被弹出。由于c位于queue1的尾部,而我们每次只能从队列的头部删除元素,因此我们可以从queueu中依次删除a/b/c并插入到queue2中,再从queue1中删除c。这就相当于从栈中弹出元素c了。我们可以用同样的方法从栈内弹出元素b。

接下来我们考虑从栈内压入一个元素d.此时queue1已经有了一个元素,我们就把d插入到queue1的尾部。如果我们再从栈内弹出一个元素,此时被弹出的应该是最后被压入的d.由于d位于queue1的尾部,我们只能先从头部删除 queue1的元素并插入到queue2,直到queue1中遇到d再直接把它删除。如果所示:

import java.util.LinkedList;public class StackByTwoQueue {        private LinkedList
queue1 = new LinkedList
(); private LinkedList
queue2 = new LinkedList
(); /* * 两个队列实现一个栈 * pop完成出栈操作,push完成入栈操作 */ public void push(String obj) { if(queue1.isEmpty()){ queue2.add(obj); } if(queue2.isEmpty()){ queue1.add(obj); } } public String pop() { //两个栈都为空时,没有元素可以弹出 if (queue1.isEmpty()&&queue2.isEmpty()) { try { throw new Exception("stack is empty"); } catch (Exception e) { } } if(queue1.isEmpty()){ while(queue2.size()>1){ queue1.add(queue2.poll()); } return queue2.poll(); } if(queue2.isEmpty()){ while(queue1.size()>1){ queue2.add(queue1.poll()); } return queue1.poll(); } return null; } public static void main(String[] args) { StackByTwoQueue stack = new StackByTwoQueue(); for(int i=0;i<10;i++){ stack.push(i+""); } for(int i=0;i<20;i++){ System.out.println(stack.pop()); } } }

 

转载于:https://www.cnblogs.com/ming-zi/p/6379697.html

你可能感兴趣的文章
MOTO MB860 国行2.3.5优化增强ROM_Top_T5_end(经典收藏版)
查看>>
C#学习经典(二)---MVC框架(Model view Controller)
查看>>
我的友情链接
查看>>
log4j配置文件说明
查看>>
Maven: 为Compiler插件设置source和target版本
查看>>
L2TP/IPSec一键安装脚本
查看>>
linux下永久添加静态路由
查看>>
android 全局变量和局部变量命名规则
查看>>
Ubuntu Sub-process /usr/bin/dpkg
查看>>
详解DNS的常用记录(下):DNS系列之三
查看>>
“爆炸门”苹果补刀,三星该“哭晕了”!
查看>>
基于linux的3款压力测试工具:Siege,webbench,ab
查看>>
Netty Buffer
查看>>
华为AAA认证典型配置举例
查看>>
icinga2使用check_snmp_idrac.py监控DELL硬件状态
查看>>
Java基础学习21(代码块)
查看>>
陈松松:无需懂任何视频制作技术,就能做出让客户感觉专业的视频
查看>>
转:用Windows Live Writer在51CTO写博客
查看>>
rsync+ssh的无验证登录
查看>>
我的友情链接
查看>>