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

Question

方法：维护两个栈A和B。将元素推入A中。要弹出元素，查看B是否为空。如果B为空，则完全弹出A并将其推入B，然后从B中弹出。否则，直接从B中弹出。

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

注：摊销分析是一种计算复杂数据结构操作总体平均性能的方法。

- Dubby

Answer 1

当考虑摊销成本时，不是只看单个操作，而是看程序执行过程中的多个操作。其思想是，如果有很多非常便宜的操作（例如单个push或pop），以及少数昂贵的操作（例如从A中弹出所有项并将其推入B），则可以将昂贵操作的成本“分配”到廉价操作上。这样就可以得到与单个dequeue的最坏情况O(n)相比的“总体”成本。

在您的示例中，您可以显示每个元素最多被推两次（一次用于添加，一次用于将其推送到另一个堆栈），并且最多弹出两次（一次用于从堆栈中弹出它，一次用于弹出它以将其从队列中删除）。因此，对于enqueue操作，摊销的最大成本为3（因为当元素被推送并且从未弹出时，它仍可能被弹出并推送到另一个堆栈），而对于dequeue，则为1，两者都是常数。

- frow

Answer 2

这里的关键思想是一个元素在其整个生命周期中只从栈1移动到栈2一次，即将其推入栈1、移动到栈2并弹出。没有来回移动。因此，它最多可以在其生命周期内经历4个操作。

1. (第一次push) 在enqueue时在栈1中进行初始push。 2. (第一次pop) 当从栈1移动到栈2。 3. (第二次push) 当从栈1移动到栈2时在栈2中push。 4. (第二次pop) 在dequeue时弹出。

假设每个push/pop操作费用为1美元。因此，一个元素从入队到出队需要$4的费用。如果你运营这个入队/出队业务，你的业务将在每个enqueue/dequeue操作上获得$0利润或亏损。因此，每个enqueue/dequeue组合操作的摊销成本为$4。

如果你运营的是仅入队业务，你只需收取$1，因为你只需要进行1次push即可完成工作。因此，每个enqueue操作的摊销成本为$1。

如果你运营的是仅出队业务，那么你每个dequeue操作需要收取$3，因为你需要按照上述步骤弹出两次并推一次。因此，每个dequeue操作的摊销成本为$3。

- sdm