方法:维护两个堆栈 A 和 B。插入 A。弹出查看 B。如果 B 为空，则将 A 完全弹出并将其插入 B，然后从 B 弹出。否则简单地从 B 弹出。
问题:1)运行时间和摊销运行时间有什么区别？
2)为什么这里的摊销运行时间是常数？它不会随着输入数量的增加以及我们决定从它弹出时增加吗？因为如果我们继续插入，那么 A 会填满很多，而 B 是空的。现在，如果我们决定从 B 弹出，那么我需要复制所有 A 然后弹出。
最佳答案
在查看摊销成本时，您不会查看单个操作，而是查看程序执行期间发生的多个操作。这个想法是，如果您有很多非常便宜的操作(例如单次推送或弹出)，并且很少有昂贵的操作(例如从 A 弹出所有项目并将其推送到 B)，您可以“分发”昂贵的操作的成本到廉价的操作。与单个出队的最坏情况 O(n) 相比，这为您提供了“总体”成本。
在您的示例中，您可以显示每个元素最多被推送到堆栈两次(一次用于添加，一次用于将其推送到另一个堆栈)并弹出最多。两次(一次用于从堆栈中弹出它，一次用于弹出以将其从队列中删除)。因此，对于入队操作，摊销最大值。 cost 是 3(因为当一个元素被插入但从未弹出时，它可能仍然被弹出并插入另一个堆栈)和 1 对于出列都是常数。
关于stack - 使用两个堆栈实现队列的恒定摊销复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23949640/