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

本文共 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

你可能感兴趣的文章
CentOS7 睡眠 休眠 关机 电源
查看>>
SqlServer里DateTime转字符串
查看>>
2019-4-23 plan
查看>>
固定弹层叉掉
查看>>
[编解码] 关于base64编码的原理及实现
查看>>
WinDbg配置和使用基础
查看>>
转:Object-Runtime的基本数据类型
查看>>
JMJS系统总结系列----Jquery分页扩展库(五)
查看>>
Excel技巧之——英文大小写转换(转)
查看>>
Google 翻译的妙用
查看>>
算法导论--python--插入排序
查看>>
Hydra用户手册
查看>>
常用的集合
查看>>
Unity3D工程源码目录
查看>>
杀死进程命令
查看>>
cookie 和session 的区别详解
查看>>
浮点数网络传输
查看>>
Mongodb对集合(表)和数据的CRUD操作
查看>>
面向对象类的解析
查看>>
tomcat如何修改发布目录
查看>>