admin管理员组

文章数量:1636954

在上国外某教授的algorithm课,课后有一个小quiz,问题如下

 Implement a queue with two stacks so that each queue operations takes a constant amortized number of stack operations.

用两个堆实现一个队列,这个队列每次操作的消耗应该是堆操作的分期常量。

我们知道队列里的元素满足先进先出的原则,而堆里面的元素满足后进先出原则。那么我们可以这么来做:

如果我们把这个俩个堆分为inbox 和outbox 

  进队(enqueue)

       我们把元素push放入inbox

本文标签: 队列两个implementQueueStack