stack - 使用两个堆栈实现队列的恒定摊销复杂度

Question

方法：维护两个堆栈A和B。压入A。弹出看B。如果B为空，则完全弹出A并将其压入B，然后从B弹出。否则只需从B弹出。

问题：1）运行时间和摊销运行时间有什么区别？2）为什么这里的摊销运行时间是常数？它不会随着输入数量的增加而增加吗？当我们决定从中弹出时？因为如果我们继续推动，那么 A 会填满很多，而 B 是空的。现在，如果我们决定从 B 中弹出，那么我需要复制所有 A，然后弹出。

Answer 1

在查看摊销成本时，您不会查看单个操作，而是查看程序执行期间发生的多个操作。这个想法是，如果您有很多非常便宜的操作（例如单次推送或弹出），而很少有昂贵的操作（例如从 A 弹出所有项目并将其推送到 B），您可以“分发”将昂贵的操作成本转移到廉价的操作中。与单个出队的最坏情况 O(n) 相比，这为您提供了“总体”成本。

在您的示例中，您可以显示每个元素在最大值处被推送到堆栈两次（一次用于添加，一次用于将其推送到另一个堆栈）并最大弹出。两次（一次用于将其从堆栈中弹出，一次用于将其弹出以将其从队列中删除）。因此，对于入队操作，摊销的最大值。cost 为 3（因为当一个元素被推送但从未弹出时，它可能仍会被弹出并推送到另一个堆栈）和 1 用于出队，这都是恒定的。

Answer 2

这里的关键思想是，一个项目在其整个生命周期中仅从 stack1 移动到 stack2 一次，即它被推入 stack1，移动到 stack2 然后弹出。没有任何来回。所以在它的生命周期内最多可以进行4次操作

1. （第一次推送）入队时在 stack1 中的初始推送
2. （第一次弹出）当从堆栈 1 移动到堆栈 2 时弹出
3. （第二次推入）当推入堆栈 2 以从堆栈 1 移动到堆栈 2
4. （第二次弹出）在出队时弹出

假设每个推送/弹出操作花费 1 美元。因此，一个项目从入队到出队将消耗 4 美元。因此，如果您正在运行此入队/出队业务，如果您开始为每个入队和出队操作收取 4 美元，您的业务将实现盈亏平衡（0 美元的利润或亏损）。因此，每个入队/出队组合操作的摊销成本为 4 美元。

相反，如果您经营的是仅排队的业务，您只需收取 1 美元，因为您只需执行 1 次推送并且您的工作已完成。因此，每个入队操作的摊销成本为 1 美元。

如果您正在运行仅出队业务，则每次出队操作将收取 3 美元，因为您必须按上述步骤弹出两次并推送一次。因此，每次出队操作的摊销成本为 3 美元。