用两个栈实现一个队列。队列的声明如下,请实现它的两个函数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 }