设计一个能够在 O(1) 平均时间内完成出栈和出队操作的栈？

Question

4

我有一个抽象数据类型，可以被视为从左到右存储的列表，具有以下可能的操作： Push：将新项目添加到列表的左端 Pop：删除列表左端的项目 Pull：删除列表右端的项目

使用三个堆栈和恒定的额外内存来实现此操作，以使任何push，pop或pull操作的平摊时间是恒定的。这些堆栈具有基本操作isEmpty，Push和Pop。

平摊时间意味着“如果我花费了这么多时间，我可以再花费一段时间并将其存储在时间银行中以供以后使用。”例如，对于每个push操作，花费三个常数时间块，因此对于每个推送的元素，您有2个额外的常数时间块。

- Dortz

显然，但我想这并不重要，这是一个有趣的问题，我想听听解决方案。 - rjh

是否是作业会影响回答的方式。对于作业，应该引导思考，而不仅仅是提供代码，不是吗？ - dmckee --- ex-moderator kitten

http://stackoverflow.com/questions/230510/homework-on-stackoverflow - Joel Coehoorn

我对作业问题的处理方式与其他问题相同。话虽如此，这个问题实际上是一条指令“做我的作业”，没有任何表明原帖者a）理解问题，b）想要理解问题或c）关心从任务中学到任何东西的迹象。这使得回答它并不令人满足。 - Sam Harwell

4个回答

3

你可以做一些只使用3个栈的事情。想一想汉诺塔。

- sfossen

2

使用双向链表并保留头部和尾部的指针。其他的，您需要先编写自己的代码，然后让我们帮助您进行纠正。

- Joel Coehoorn

这可能是构建该物品的最佳方式，因为它没有人为的大小限制，但相对复杂。 - dmckee --- ex-moderator kitten

一个好的双向链表示例（使用Actionscript）请访问www.polygonal.de。 - Dave Swersky

0

首先，通过两个栈来实现队列（这是一个相当标准的问题），然后进行泛化。

- Captain Segfault

这就是我不理解这个问题的地方。"标准"/Okasaki两个列表的解决方案难道不具有 O(1) 的平摊时间出列吗？ - subsub

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MarkusQ · Accepted Answer

做出一些假设：

使用三个栈和恒定的额外内存来实现，以便于任何推、弹、拉操作的平摊时间都是常数。这三个栈具有基本操作，即isEmpty、Push和Pop。

那么我的第一个建议是忽略那些谈论链表的人。确实，在没有三个栈的要求下，任何合理的人都会采用链表实现，但作业的关键不在于如何合理地实现它，而在于你的教师希望你如何实现。

我的第二个建议是拿一些小块、扑克牌或一堆泡沫杯，并指定三个栈（例如用饮料杯垫之类的东西）。开始试着将一个栈的内容转移到另一个栈中，这样应该可以给你一个想法。