Queue via Stacks: Implement a MyQueue class which implements a queue using two stacks.
解答
两个Stack，如果把一个Stack的元素pop然后push到另外一个Stack上，那么顺序就会发生颠倒。
Stack是FILO，Queue是FIFO，那么很自然的可以想到利用这两个Stack来实现Queue。
1
2
3
4
5
|
IN OUT
4 1
3 2
2 3
1 4
|
当Queue中添加元素的时候，把OUT都移到IN里，然后在IN的顶部push。
当Queue中拿出元素的时候，把IN都移到OUT里，然后在OUT的顶部push。
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
|
public class MyQueue {
Stack in = new Stack();
Stack out = new Stack();
public void add(Object value) {
drain(out, in);
in.push(value);
}
public T remove() {
drain(in, out);
return out.pop();
}
public T peek() {
drain(in, out);
return out.peek();
}
private void drain(Stack from, Stack to) {
if (from.isEmpty()) {
return;
}
Object v = from.pop();
while (v != null) {
to.push(v);
v = from.pop();
}
}
}
|
评论