假设我们有两个堆栈并没有其他的临时变量。
Suppose we have two stacks and no other temporary variable.
时尽可能仅使用两个栈,以构建一个队列的数据结构?
Is to possible to "construct" a queue data structure using only the two stacks?
请2堆栈,我们姑且称之为收件箱
和发件箱
。
Keep 2 stacks, let's call them inbox
and outbox
.
队列:
- 将新元素添加到收件箱
Queue:
- Push the new element onto inbox
出列:
- 如果发件箱
是空的,由收件箱
弹出的每个元素,将其推到斟满发件箱
- 弹出并从返回的顶级元素发件箱
Dequeue:
- If outbox
is empty, refill it by popping each element from inbox
and pushing it onto outbox
- Pop and return the top element from outbox
采用这种方法,每个元件将在每个堆叠正好一次。 - 这意味着每个元素将被推两次和弹出两次,给予分期常量时间的操作
Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.
下面是一个Java的实现:
Here's an implementation in Java:
public class Queue<E>
{
private Stack<E> inbox = new Stack<E>();
private Stack<E> outbox = new Stack<E>();
public void queue(E item) {
inbox.push(item);
}
public E dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.pop();
}
}