摘要

• O（1）算法是已知的6堆栈
• O（1）算法是已知的3堆栈，但使用这在实践中对应于具有附加的内部数据结构惰性评估，因此它并不构成的溶液
• 在靠近塞奇威克人们已经证实，他们不知道的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.

更新：另一个相关算法由霍尔格·彼得森纸栈与双端中所述，发表在计算与组合第7届会议。您可以从谷歌图书的文章。检查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说了一些天前，我想如果他知道的解决方案或有一些错误，这将是公平的检查与塞奇威克教授于是我写信给他，我刚刚收到的响应（虽然不是从本人，而是来自一个同事在普林斯顿），所以我想用所有you.He的交流基本上可以说，他知道使用三个栈和规定的其他限制没有算法（如不使用惰性计算）。他知道使用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)."