algorithm - 设计一个也可以在 O(1) 摊销时间内出队的堆栈？

Question

我有一个抽象数据类型，可以看作是从左到右存储的列表，具有以下可能的操作:推送:向列表的左端添加一个新项目Pop:移除列表左端的项目拉取:移除列表右端的项

使用三个堆栈和常量附加内存来实现它，以便任何推送、弹出或拉取操作的摊销时间是常量。栈有基本的操作，isEmpty，Push，Pop。

摊销时间意味着“如果我花费了这段时间，我可以花费另一个 block 并将其存储在时间银行中以备后用。”就像对于每个推送操作，花费三个恒定时间 block ，因此对于每个推送的元素，你有 2 个额外的恒定时间 block 。

Answer 1

做一些假设:

1. 这是家庭作业
2. 这一段是作业的一部分

Implement this using three stacks and constant additional memory, so that the amortized time for any push, pop, or pull operation is constant. The stacks have basic operations, isEmpty, Push, and Pop.

那么我的第一个建议就是忽略那些和你谈论链表的人。诚然，这就是任何有理智的人在没有三个堆栈要求的情况下会如何实现它，但家庭作业的关键因素不是按照一个有理智的人的方式去做，而是你的老师希望你如何做.

我的第二个建议是准备一些积木、一副纸牌或一堆泡沫塑料杯，并指定三叠(例如杯垫或其他东西)。开始尝试将一个堆栈的内容转移到另一个堆栈时会发生什么，这应该会让您有所了解。