问如何实现一个有三个栈的队列？

EN

摘要

• 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-stack算法。

更新:另一个相关算法在Holger Petersen的论文"Stacks is“中描述，发表在第七届年度计算和组合会议上。你可以在Google Books上找到这篇文章。查看第225-226页。但该算法并不是真正的实时模拟，它是对三个堆栈上的双端队列的线性时间模拟。

gusbro：“就像@Leonel几天前说的那样，我认为如果Sedgewick教授知道解决方案或有什么错误，与他核实一下是公平的。所以我确实给他写了信。我刚刚收到了一个回复(虽然不是来自他自己，而是来自普林斯顿的一个同事)，所以我想和所有的you.He分享，他基本上说他不知道使用三个堆栈的算法和施加的其他约束(比如不使用惰性评估)。他确实知道一种使用6个堆栈的算法，正如我们已经知道的那样，查看这里的答案。因此，我猜这个问题仍然悬而未决，无法找到算法(或者证明找不到算法)。

好吧，这真的很难，我能想出的唯一解决方案，记得我对Kobayashi Maru测试的Kirks解决方案(不知何故被欺骗了)：想法是，我们使用堆栈(并用它来模拟一个列表)。我调用操作en/dequeue和push和pop，然后我们得到：

queue.new() : Stack1 = Stack.new(<Stack>);  
              Stack2 = Stack1;  

enqueue(element): Stack3 = Stack.new(<TypeOf(element)>); 
                  Stack3.push(element); 
                  Stack2.push(Stack3);
                  Stack3 = Stack.new(<Stack>);
                  Stack2.push(Stack3);
                  Stack2 = Stack3;                       

dequeue(): Stack3 = Stack1.pop(); 
           Stack1 = Stack1.pop();
           dequeue() = Stack1.pop()
           Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();

(StackX = StackY不是内容的副本，只是引用的副本。这只是简单地描述它。您也可以使用3个堆栈的数组，并通过index访问它们，在那里您只需更改index变量的值)。在堆栈操作术语中，一切都是O(1)。

是的，我知道这是有争议的，因为我们有3个以上的隐式堆栈，但它可能会给你们其他人带来好的想法。

编辑:解释示例：

 | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | |         | |
 | |   |2|   | |
 | |   |_|   | |
 | |_________| |
 |             |
 |     |1|     |
 |     |_|     |
 |_____________|

我试着在这里用一个小的ASCII艺术来展示Stack1。

每个元素都包装在一个元素堆栈中(所以我们只有类型安全的堆栈)。

你看，为了删除，我们首先弹出第一个元素(包含这里的元素1和2的堆栈)。然后弹出下一个元素，并在那里展开1。然后，我们说第一个弹出的堆栈现在是我们的新Stack1。说得更实用一点--这些列表是由2个元素组成的堆栈实现的，其中顶部的元素是cdr，第一个/下面的顶部元素是car。另外两个是帮助堆栈。

Esp棘手的是插入，因为你必须以某种方式深入到嵌套堆栈中来添加另一个元素。这就是Stack2出现的原因。Stack2总是最内层的堆栈。and就是将一个元素放入队列，然后再放入一个新的Stack2 (这就是为什么我们不允许在出队操作中接触Stack2的原因)。

我将尝试一个证明来证明这是不可能的。

假设有一个队列Q，它由3个堆栈A、B和C模拟。

断言

进一步，假设Q可以模拟O(1)中的操作{

• ，ASRT0 := }。这意味着对于每个队列/出队操作都存在特定的堆栈推送/弹出序列，假设队列操作是deterministic.

的( simulated.

• Without )而失去一般性

让在Q中排队的元素根据它们的队列顺序被编号为1，2，...，其中排入Q中的第一个元素被定义为1，第二个被定义为2，依此类推。

定义

当Q中有0个元素(以及A，B中的0个元素)时，

• Q(0) := Q的状态，并且在Q(0)
• Q(n) :=上进行1次队列操作之后，C)
• Q(1) := Q(以及A，B和C)的状态在Q(0)

上进行n次队列操作之后，Q的状态(以及A，B和C

定义

• |Q(n)| := Q(n)中的元素数量(因此，当Q的状态为Q(n)
• |A(n)| :=时，堆栈A的状态为A(n)

中的元素数量

以及对堆栈B和C的类似定义。

平凡的是，

|Q(n)| = |A(n)| + |B(n)| + |C(n)|

---

|Q(n)|显然在n上是无界的。

因此，|A(n)|、|B(n)|或|C(n)|中至少有一个在n上是无界的。

WLOG1，假设堆栈A是无界的，而堆栈B和C是有界的。

定义* B_u :=是B* C_u :=的上界，是C* K := B_u + C_u + 1的上界

WLOG2，对于n这样的|A(n)| > K，从Q(n)中选择K个元素。假设对于所有的x >= 0，这些元素中有1个在A(n + x)中，也就是说，无论完成多少个队列操作，该元素总是在堆栈A中。

• X :=

的那个元素

然后我们就可以定义

• Abv(n) :=大于X
• Blo(n) :=的堆栈A(n)中的项数小于X的堆栈A(n)中的元素数

|A(n)| = Abv(n) + Blo(n)

ASRT1 :=从Q(n)出队X所需的pops数至少为Abv(n)

从(ASRT0)和(ASRT1)开始，ASRT2 := Abv(n)必须是有界的。

如果Abv(n)是无界的，则如果需要20个出队才能将X从Q(n)出队，则至少需要Abv(n)/20 pops。它是无界的。20可以是任何常量。

因此，

ASRT3 := Blo(n) = |A(n)| - Abv(n)

必须是无界的。

WLOG3，我们可以从A(n)的底部选择K个元素，其中一个元素位于A(n + x)中，用于所有x >= 0

对于任何给定的n，X(n) :=该元素

ASRT4 := Abv(n) >= |A(n)| - K

当一个元素在Q(n)中排队时...

WLOG4，假设B和C已经填充到它们的上界。假设已经达到了X(n)以上元素的上限。然后，一个新元素进入A。

WLOG5，假设作为结果，新元素必须在X(n)下面输入。

ASRT5 :=将元素放在X(n) >= Abv(X(n))以下所需的pops数量

在(ASRT4)中，Abv(n)在n上是无界的。

因此，将元素放在X(n)之下所需的pops数量是无限的。

这与ASRT1相矛盾，因此，不可能模拟具有3个堆栈的O(1)队列。

也就是说。

至少有一个堆栈必须是未绑定的。

对于驻留在该堆栈中的元素，其上方的元素数量必须是有界的，否则移除该元素的出队操作将是无界的。

然而，如果超过它的元素的数量是有界的，那么它将达到一个限制。在某些情况下，必须在其下方输入一个新元素。

因为我们总是可以从堆栈中最低的几个元素中选择旧元素，所以它上面可以有无限数量的元素(基于无界堆栈的无限大小)。

要在它下面输入一个新元素，因为它上面有无限数量的元素，所以需要无限数量的pops才能将新元素放在它下面。

这样就产生了矛盾。

有5个WLOG (不失一般性)语句。在某种意义上，可以直观地理解它们是真的(但考虑到它们是5，这可能需要一些时间)。可以推导出没有丢失共性的形式证明，但非常冗长。它们被省略了。

我承认，这样的遗漏可能会使WLOG声明受到质疑。由于程序员对bug的偏执，如果您愿意的话，请务必验证WLOG语句。

第三个堆栈也是不相关的。重要的是有一组有界堆栈和一组无界堆栈。一个示例最少需要2个堆栈。当然，堆栈的数量必须是有限的。

最后，如果我是对的，没有证据，那么应该有一个更容易的归纳证明。可能基于每个队列之后发生的事情(在给定队列中所有元素的集合的情况下，跟踪它对出队的最坏情况的影响)。