设计一个也可以在 O(1) 摊余时间内出队的堆栈？
我有一个抽象数据类型，可以将其视为从左到右存储的列表，具有以下可能的操作： 推送：将新项目添加到列表的左端 Pop：删除列表左端的项目 拉：删除列表右端的项目
使用三个堆栈和恒定的附加内存来实现此操作，以便任何推送、弹出或拉操作的摊销时间是恒定的。 堆栈具有基本操作：isEmpty、Push 和 Pop。
摊销时间意味着“如果我花费了这么多时间，我可以花费另一块时间并将其存储在时间银行中以供以后使用。” 就像每个推送操作一样，花费三个恒定时间块，因此对于每个推送的元素，您都有 2 个额外的恒定时间块。
I have an abstract data type that can be viewed as a list stored left to right, with the following possible operations:
Push: add a new item to the left end of the list
Pop: remove the item on the left end of the list
Pull: remove the item on the right end of the list
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.
Amortized time means "If I spend this amount of time, I can spend another block of it and store it in a bank of time to be used later." like for each push operation, spend three blocks of constant time, so for every element pushed, you have 2 extra blocks of constant time.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
做出一些假设：
那么我的第一个建议就是忽略那些与你谈论链表的人。 确实，这就是任何理性人在没有三叠要求的情况下实现它的方式，但家庭作业的关键因素不是按照理性人的方式去做，而是你的老师希望你如何做。
我的第二个建议是准备一些积木、一副纸牌或一堆聚苯乙烯泡沫塑料杯，并指定三堆（例如杯垫或其他东西）。 开始尝试一下将一个堆栈的内容转移到另一个堆栈时会发生什么，这应该会给您一个想法。
Making a few assumptions:
Then my first advice would be to ignore the people talking to you about linked lists. True, that's how any reasonable person would implement it without the three stack requirement, but the key factor in homework isn't to do it the way a reasonable person would, but rather how your instructor wants you to.
My second bit of advice would be to get some blocks, a deck of cards, or a bunch of styrofoam cups and designate three stacks (e.g. with coasters or something). Start playing around with what happens when you transfer the contents of one stack to another, and that should give you an idea.
你可以做一些只使用 3 个堆栈的事情。 想想河内塔。
You could do something which uses only the 3 stacks. Think tower of Hanoi.
使用双向链表并保留指向头和尾的指针。 其余的，您需要先编写自己的代码，然后让我们帮助您纠正它。
Use a doubly-linked list and keep pointers to the head and tail. For the rest, you need to write your own code first and then let us help you correct it.
首先根据两个堆栈实现一个队列（一个相当标准的问题）并进行概括。
Start by implementing a queue in terms of two stacks (a pretty standard problem) and generalize.