首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指offer(9)——用两个栈实现队列

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

作者头像
说故事的五公子
发布2019-09-11 17:24:55
2180
发布2019-09-11 17:24:55
举报

题目:

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数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 }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-07-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目:
  • 思路:
  • 代码:
  • 相关题目——两个队列实现栈:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档