假设我们有两个堆栈并且没有其他临时变量。
是否可以仅使用两个堆栈来“构建”队列数据结构?
最佳答案
保留 2 个堆栈,我们称它们为 inbox
和 outbox
。
排队:
- 将新元素推送到
收件箱
出列:
如果
/li>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();
}
}
关于algorithm - 如何使用两个堆栈实现队列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69192/