假设我们有两个堆栈,没有其他临时变量。
是否可以仅使用两个堆栈来“构造”队列数据结构?
最佳答案
保留2个堆栈,我们称它们为inbox
和outbox
。
排队:
inbox
出队:
outbox
为空,则通过从inbox
弹出每个元素并将其推到outbox
上来重新填充它outbox
的顶部元素使用此方法,每个元素将在每个堆栈中恰好出现一次-意味着每个元素将被插入两次并弹出两次,从而提供了摊销的固定时间操作。
这是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();
}
}