algorithm - 三栈队列如何实现？

Question

我在一本算法书(罗伯特塞奇威克和凯文韦恩的 Algorithms, 4th Edition)中遇到了这个问题。

Queue with three stacks. Implement a queue with three stacks so that each queue operation takes a constant (worst-case) number of stack operations. Warning : high degree of difficulty.

我知道如何使用 2 个堆栈创建队列，但我找不到使用 3 个堆栈的解决方案。任何想法 ？

(哦还有，这不是作业:))

Answer 1

总结

• O(1) 算法已知有 6 个堆栈
• O(1) 算法以 3 个堆栈而闻名，但使用惰性求值，这在实践中对应于具有额外的内部数据结构，因此它不构成解决方案
• Sedgewick 附近的人已经确认他们不知道在原始问题的所有限制范围内的 3 堆栈解决方案

详情

此链接背后有两个实现:http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

其中一个是具有三个堆栈的 O(1)，但它使用惰性执行，这实际上会创建额外的中间数据结构(闭包)。

其中另一个是 O(1)，但使用六个堆栈。但是，它无需延迟执行即可工作。

更新:Okasaki 的论文在这里:http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps并且看起来他实际上只使用了 2 个堆栈用于具有惰性评估的 O(1) 版本。问题是它实际上是基于惰性求值。问题是它是否可以在没有惰性评估的情况下转化为 3 栈算法。

更新:Holger Petersen 在第 7 届计算与组合年会上发表的论文“Stacks versus Deques”中描述了另一种相关算法。您可以从 Google 图书中找到这篇文章。检查第 225-226 页。但该算法实际上并不是实时模拟，而是对一个双端队列在三个栈上的线性时间模拟。

gusbro:“正如@Leonel 几天前所说，我认为与 Sedgewick 教授核实他是否知道解决方案或存在一些错误是公平的。所以我确实写信给他。我刚刚收到回复(虽然不是来自他自己，而是来自普林斯顿的一位同事)所以我想和大家分享。他基本上说他不知道使用三个堆栈的算法和其他施加的约束(比如不使用惰性评估)。他确实知道一个使用 6 个堆栈的算法，因为我们已经知道在这里查看答案。所以我想这个问题仍然是寻找算法(或证明找不到算法)的问题。”