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

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

最佳答案

保留2个堆栈,我们称它们为inboxoutbox

排队:

  • 将新元素推送到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();
        }
    
    }
    

    08-16 12:29