实现队列,就要实现它的3个方法:Enqueue(入队)、Dequeue(出队)和Peek(队头)。
之前先准备两个栈 stack1和stack2
1)stack1存的是每次进来的元素,所以Enqueue就是把进来的元素push到stack1中。
2)而对于Dequeue,一开始stack2是空的,所以我们把stack1中的元素全都pop到stack2中,这样stack2的栈顶就是队头。只要stack2不为空,那么每次出队,就相当于stack2的pop。
3)接下来,每入队一个元素,仍然push到stack1中。每出队一个元素,如果stack2不为空,就从stack2中pop一个元素;如果stack2为空,就重复上面的操作——把stack1中的元素全都pop到stack2中。
4)Peek操作,类似于Dequeue,只是不需要出队,所以我们调用stack2的Peek操作。当然,如果stack2为空,就把stack1中的元素全都pop到stack2中。
5)注意边界的处理,如果stack2和stack1都为空,才等于队列为空,此时不能进行Peek和Dequeue操作。
讲起来很烦 代码写起来很简单:
public class NewQueue {
private Stack stack1;
private Stack stack2;
public NewQueue() {
stack1 = new Stack();
stack2 = new Stack();
}
public void Enqueue(int element) {
stack1.Push(element);
}
public int Dequeue() {
if (stack2.Count == 0) {
if (stack1.Count == 0) {
throw new Exception("Thequeue is empty");
} else {
while (stack1.Count > 0)
stack2.Push(stack1.Pop());
}
}
return (int) stack2.Pop();
}
public int Peek() {
if (stack2.Count == 0) {
if (stack1.Count == 0) {
throw new Exception("Thequeue is empty");
} else {
while (stack1.Count > 0)
stack2.Push(stack1.Pop());
}
}
return (int) stack2.Peek();
}
}