StackQueue平摊时间实现

Question

根据下面引号中的规范，实现了一个队列(语言是Ruby，但希望它对每个人来说都是好的)。

使用栈实现队列。也就是说，写入enqueue和dequeue只使用push和pop操作

在性能方面，排队应该是0(1)，但排队可以是0 (1)最坏的O (n)。在平摊时间方面，dequeue应为O(1)。证明你的解决方案能做到这一点。

class StackQueue
  def initialize
    @in, @out = [], []
  end
  def enqueue(value)
    @in << value
  end
  def dequeue
    if @out.empty?
      @out << @in.pop until @in.empty?
    end
    @out.pop
  end
end

我想知道，你如何证明dequeue的平摊时间?谢谢!

Answer 1

直观上，O(1)平销复杂度很容易理解:我们从队列中取出的每个元素都恰好一次被推入in，恰好一次从in弹出，恰好一次被推入out，恰好一次从out弹出，所有这些操作都是O(1)操作。

用势法很容易证明。每次我们输入enqueue的值，我们"支付"3:1为push的成本，2为将来移动到out而节省。

我们也可以为dequeue支付3:1用于empty测试，1用于out上的pop, 1用于确定in为空。我们可以用enqueue的盈余来支付in上的pop和out上的push。

我们可以通过为每个操作"支付"3来负担所有操作，从而得到平摊复杂度为O(1)。