专栏首页用代码征服天下剑指offer(9)——用两个栈实现队列

剑指offer(9)——用两个栈实现队列

题目:

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。

思路:

首先定义两个栈stack1、stack2,stack1用于插入,stack2用于删除。删除时如果直接出栈就无法实现先进先出,这时需要将stack1中的所有元素从stack1出栈,然后依次压入stack2中,然后再从stack2中出栈。如果stack2中有元素存在,那么直接出栈,无需将stack1中元素压入stack2中。只有当stack2中元素都为空时,才需要将stack1中元素取出。

代码:

 1 import java.util.Stack;
 2 
 3 /**
 4  *  两个栈实现队列
 5  * @author wydream
 6  *
 7  */
 8 
 9 public class TwoStackQueue {
10 
11     private Stack<Object> s1;//s1插入元素
12     private Stack<Object> s2;//s2删除元素
13     
14     public TwoStackQueue() {
15         s1=new Stack<Object>();
16         s2=new Stack<Object>();
17     }
18     
19     //插入元素
20     public void push(Object obj) {
21         s1.push(obj);
22     }
23     
24     //元素出队列
25     public Object pop() {
26         if(s2.empty()&&s1.empty()) {
27             return null;
28         }
29         if(s2.empty()) {
30             System.out.println("s1中数据进入到s2");
31             while(!s1.empty()) {
32                 Object obj=s1.pop();
33                 s2.push(obj);
34             }
35         }
36         return s2.pop();
37     }
38     
39     public static void main(String[] args) {
40         TwoStackQueue tq=new TwoStackQueue();
41         tq.push("北京");
42         tq.push("上海");
43         tq.push("深圳");
44         tq.push("杭州");
45         System.out.println(tq.pop());
46         System.out.println(tq.pop());
47         System.out.println(tq.pop());
48         tq.push("武汉");
49         System.out.println(tq.pop());
50         System.out.println(tq.pop());
51     }
52     
53 }

相关题目——两个队列实现栈:

 1 import java.util.LinkedList;
 2 import java.util.Queue;
 3 
 4 /**
 5  * 两个队列实现栈
 6  * 
 7  * @author wydream
 8  *
 9  */
10 
11 public class TwoQueueStack {
12     
13     private Queue<String> queue1=new LinkedList<String>();
14     private Queue<String> queue2=new LinkedList<String>();
15     
16     //向栈中压入元素
17     public void push(String value) {
18         //两个队列都为空时,优先考虑queue1
19         if(queue1.isEmpty()&&queue2.isEmpty()) {
20             queue1.add(value);
21             return;
22         }
23         
24         //如果queue1为空,queue2中有数据,则直接放入queue2中
25         if(queue1.isEmpty()) {
26             queue2.add(value);
27             return;
28         }
29         
30         //如果queue2为空,queue1有数据,直接放入queue1中
31         if(queue2.isEmpty()) {
32             queue1.add(value);
33             return;
34         }
35     }
36     
37     
38     //从栈中弹出一个数据
39     public String pop() {
40         //两个栈都为空
41         if(queue1.isEmpty()&&queue2.isEmpty()) {
42             System.out.println("栈为空");
43             return null;
44         }
45         //如果queue1中没有元素,queue2中有元素,将其queue2中的元素依次放入queue1中,直到最后一个元素,弹出即可
46         if(queue1.isEmpty()) {
47             while(queue2.size()>1) {
48                 queue1.add(queue2.poll());
49             }
50             return queue2.poll();
51         }
52         //如果queue2中没有元素,queue1中有元素,将其queue1中的元素依次放入queue2中,直到最后一个元素,弹出即可
53         if(queue2.isEmpty()) {
54             while(queue1.size()>1) {
55                 queue2.add(queue1.poll());
56             }
57             return queue1.poll();
58         }
59         return null;
60     }
61     
62     
63     public static void main(String[] args) {
64         TwoQueueStack ts=new TwoQueueStack();
65         ts.push("北京");
66         ts.push("上海");
67         ts.push("广州");
68         ts.push("深圳");
69         
70         System.out.println(ts.pop());
71         System.out.println(ts.pop());
72         ts.push("苏州");
73         ts.push("杭州");
74         System.out.println(ts.pop());
75         System.out.println(ts.pop());
76         
77     }
78     
79 
80 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Vue.js学习总结——1

    双大括号会将数据解释为普通文本,而非 HTML 代码。为了输出真正的 HTML,你需要使用 v-html 指令:

    说故事的五公子
  • 邂逅Vue.js

    运行这段程序,我们可以在浏览器中看到你好呀,那么这段程序做了些什么,为什么可以显示出来?

    说故事的五公子
  • Java基础系列5:Java代码的执行顺序

    该系列博文会告诉你如何从入门到进阶,一步步地学习Java基础知识,并上手进行实战,接着了解每个Java知识点背后的实现原理,更完整地了解整个Java技术体系,形...

    说故事的五公子
  • 103ZB数据存不下,存储技术需要另辟蹊径

    首先让我们看一组数据:2018年全球产生的数据量是32ZB,预计2023年会达到103ZB。其中,有多少数据被保留下来了呢?

    用户5498443
  • html --- bootstrap 框架 (栅格系统布局)

    小蔚
  • Prometheus 入门教程(一):Prometheus 快速入门

    Prometheus 是任何一个高级工程师必须要掌握的技能。那么如何从零部署一套 Prometheus 监控系统呢?本篇文章将从 Prometheus 的原理讲...

    陈树义
  • 腾讯Techo开发者大会Serverless阵容热炸,云计算教父级大咖直播连线,马上预约!

    12月19日至20日,由腾讯主办的2020 Techo Park开发者大会将于北京召开。本次大会将邀请全球超过200位顶级技术专家来到现场,和数千位参会者就云...

    腾讯云serverless团队
  • 比较全面的MySQL优化参考

    本文整理了一些MySQL的通用优化方法,做个简单的总结分享,旨在帮助那些没有专职MySQL DBA的企业做好基本的优化工作,至于具体的SQL优化,大部分通过加适...

    wangxl
  • 谈谈React中Diff算法的策略及实现

    keyWords
  • Scala学习三-面向对象

    前面我们已经学习了特质类似接口,其可以被继承,同时如果需要继承多个特质的话,则需要使用extends…with…进行继承。其类似java中的接口和抽象方法的结合...

    路行的亚洲

扫码关注云+社区

领取腾讯云代金券