如何使用两个堆栈实现队列？

Question

假设我们有两个堆栈，没有其他临时变量。

是否可以仅使用两个堆栈来“构造”队列数据结构？

Answer 1

保留2叠，我们称它们为inbox和outbox。入队：将新元素推到 inbox出队：如果outbox为空，则通过从中弹出每个元素inbox并将其推入来重新填充它outbox弹出并从返回顶部元素 outbox使用此方法，每个元素将在每个堆栈中恰好出现一次-意味着每个元素将被推入两次并弹出两次，从而提供了摊销的固定时间操作。这是Java的实现：public class Queue<E>{&nbsp; &nbsp; private Stack<E> inbox = new Stack<E>();&nbsp; &nbsp; private Stack<E> outbox = new Stack<E>();&nbsp; &nbsp; public void queue(E item) {&nbsp; &nbsp; &nbsp; &nbsp; inbox.push(item);&nbsp; &nbsp; }&nbsp; &nbsp; public E dequeue() {&nbsp; &nbsp; &nbsp; &nbsp; if (outbox.isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while (!inbox.isEmpty()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;outbox.push(inbox.pop());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return outbox.pop();&nbsp; &nbsp; }}