如何实现具有三个堆栈的队列? [英] How to implement a queue with three stacks?

问题描述

我在一本算法书(算法，第 4 版 作者:Robert Sedgewick 和 Kevin Wayne).

I came across this question in an algorithms book (Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne).

具有三个堆栈的队列.实现一个具有三个堆栈的队列，以便每个队列操作采用恒定(最坏情况)数量的堆栈操作.警告:高难度.

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 个堆栈的解决方案.任何的想法 ?

I know how to make a queue with 2 stacks but I can't find the solution with 3 stacks. Any idea ?

(哦，这不是家庭作业 :) )

(oh and, this is not homework :) )

推荐答案

SUMMARY

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

详情

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

There are two implementations behind this link: http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

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

One of them is O(1) with three stacks BUT it uses lazy execution, which in practice creates extra intermediate data structures (closures).

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

Another of them is O(1) but uses SIX stacks. However, it works without lazy execution.

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

UPDATE: Okasaki's paper is here: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps and it seems that he actually uses only 2 stacks for the O(1) version that has lazy evaluation. The problem is that it's really based on lazy evaluation. The question is if it can be translated to a 3-stack algorithm without lazy evaluation.

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

UPDATE: Another related algorithm is described in paper "Stacks versus Deques" by Holger Petersen, published in 7th Annual Conference on Computing and Combinatorics. You can find the article from Google Books. Check pages 225-226. But the algorithm is not actually real-time simulation, it's linear-time simulation of a double-ended queue on three stacks.

gusbro:正如@Leonel 几天前所说的那样，我认为与 Sedgewick 教授核实他是否知道解决方案或存在错误是公平的.所以我确实写信给他.我刚刚收到回复(尽管不是来自他自己，而是来自普林斯顿的一位同事)，所以我想与大家分享.他基本上说他不知道使用三个堆栈的算法以及强加的其他约束(例如不使用惰性求值).他确实知道一种使用 6 个堆栈的算法，因为我们已经知道在此处查看答案.所以我想问题仍然存在以找到算法(或证明找不到算法)."

gusbro: "As @Leonel said some days ago, I thought it would be fair to check with Prof. Sedgewick if he knew a solution or there was some mistake. So I did write to him. I just received a response (albeit not from himself but from a colleague at Princeton) so I like to share with all of you.He basically said that he knew of no algorithms using three stacks AND the other constraints imposed (like not using lazy evaluation). He did know of an algorithm using 6 stacks as we already know looking at the answers here. So I guess the question is still open to find an algorithm (or prove one cannot be found)."

这篇关于如何实现具有三个堆栈的队列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！