摘要

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

细节

该链接背后有两种实现方式：http
:
//www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

其中之一是带有三个堆栈的O（1），但是它使用了延迟执行，实际上这会创建额外的中间数据结构（关闭）。

其中另一个是O（1），但使用了SIX堆栈。但是，它无需延迟执行即可工作。

更新：冈崎的论文在这里：http
://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps
，看来他实际上只使用了2个堆栈用于O（1）版本，其懒惰的评估。问题在于它实际上是基于惰性评估。问题是，是否可以将其转换为3层算法而无需进行延迟评估。

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

gusbro：“正如@Leonel几天前所说，我认为与Sedgewick教授确认他是否知道解决方案或存在一些错误是很公平的。所以我确实写信给他。我刚刚收到了答复（尽管不是来自他基本上是说，他不知道使用三个堆栈的算法以及施加的其他限制（例如不使用惰性评估），他确实知道与其他人共享算法。我们已经知道要在这里找到6个堆栈，因此我想寻找一个算法还是存在一个问题（或者证明找不到一个算法）。”