0%

由两个栈组成的队列

问题

编写一个类,用两个栈实现队列,支持队列的基本操作:add、poll、peek。

思路

栈的特点是先进后出,队列的特点是先进先出,使用两个栈正好能把顺序反过来实现类似队列的操作。

方案

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

public class TwoStackQueue<T extends Comparable<T>> {

private Stack<T> mStack1;

private Stack<T> mStack2;

public TwoStackQueue() {
mStack1 = new Stack<>();
mStack2 = new Stack<>();
}

public void add(T item) {
mStack1.push(item);
}

/**
* 移除并返回队首的元素
*
* @return
*/
public T poll() {

if (mStack1.isEmpty() && mStack2.isEmpty()) {
throw new IllegalStateException("Queue is empty!");
} else if (mStack2.isEmpty()) {
while (!mStack1.isEmpty()) {
mStack2.push(mStack1.pop());
}
}

return mStack2.pop();

}

/**
* 返回队列头部的元素
*
* @return
*/
public T peek() {

if (mStack1.isEmpty() && mStack2.isEmpty()) {
throw new IllegalStateException("Queue is empty!");
} else if (mStack2.isEmpty()) {
while (!mStack1.isEmpty()) {
mStack2.push(mStack1.pop());
}
}

return mStack2.peek();

}
}