用栈实现队列

方案1

此方案较为繁琐。

  1. 声明两个栈A,B。
  2. 队列put：将A中的所有元素压入B中，向A中压入元素，将B中所有元素压回。
  3. 队列poll：将A中元素全部压入B，B出栈。

方案2

  1. 申明两个栈A,B。A专职入队，B专职出队。
  2. 队列put：向A中压入元素。
  3. 队列poll：如B中有，则B出栈。如果B为空，则将A中元素全部压入B，然后B中出栈。

实现（方案2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package stack2queue;
import stack.Stack;
/**
 * @author jack
 * 2016年11月19日 上午2:20:25
 */
public class Queue {
	private Stack s1; // 专门入栈
	private Stack s2; // 专门出栈
	public Queue(int cap) {
		super();
		this.s1 = new Stack(cap);
		this.s2 = new Stack(cap);
	}
	// 入队
	public boolean put(Object o) {
		return s1.push(o);
	}
	// 出队
	public Object poll() throws Exception {
		if (s2.isEmpty()) {
			stackTrans(s1, s2);
		}
		return s2.pop();
	}
	// 栈之间全拷贝
	private void stackTrans(Stack stack1, Stack stack2) throws Exception {
		while (!stack1.isEmpty()) {
			Object o = stack1.pop();
			stack2.push(o);
		}
	}
}