如何实现一个三栈的队列？
我在algorithm书（ algorithm，由罗伯特·Sedgewick和凯文·韦恩第四版）中遇到了这个问题。
排队三堆。 实现一个有三个堆栈的队列，以便每个队列操作都有一个常量（最坏情况）的堆栈操作。 警告：难度高。
我知道如何创build2个堆栈的队列，但是我找不到3个堆栈的解决scheme。 任何想法 ？
（哦，这不是作业:)）
概要
- O（1）algorithm是已知的6堆栈
- O（1）algorithm是已知的3堆栈，但使用懒惰评估实际上相当于有额外的内部数据结构，所以它不构成一个解决scheme
- Sedgewick附近的人已经证实他们并不知道在原始问题的所有约束范围内都有一个三层栈的解决scheme
细节
这个链接有两个实现： http : //www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html
其中之一是O（1）有三个堆栈，但它使用惰性执行，实际上创build额外的中间数据结构（闭包）。
另一个是O（1），但使用SIX堆栈。 但是，它没有懒惰的执行。
更新：冈崎的文件在这里： http ：//www.eecs.usma.edu/webs/people/okasaki/jfp95.ps，似乎他实际上只使用了2堆栈的O（1）版本，有懒评估。 问题是，它确实是基于懒惰的评估。 问题是如果它可以被翻译成一个三堆栈algorithm而没有懒惰的评估。
更新：Holger Petersen在第七届计算和组合年会上发表的论文“Stacks vs. Deques”中描述了另一种相关algorithm。 您可以从Google图书中find相关文章。 检查225-226页。 但algorithm实际上不是实时仿真，而是三个栈上双端队列的线性时间仿真。
gusbro：“正如@Leonel前几天所说，我认为与Sedgewick教授商量是否公平，是否知道解决方法或是有什么错误，所以我给他写了信，我刚刚收到回复（虽然不是他自己却是来自普林斯顿的一位同事），所以我想和大家分享一下。他基本上说，他知道没有使用三个堆栈的algorithm，还有其他限制（比如不使用懒惰评估），他知道一个algorithm6堆栈，因为我们已经知道在这里查看答案，所以我想这个问题仍然是开放的，以find一个algorithm（或certificate不能find）。
好吧，这真的很难，我能想出的唯一解决scheme是记住Kirk解决Kobayashi Marutesting（不知何故被欺骗）的解决scheme：这个想法是，我们使用堆栈（并用它来build模一个列表）。 我打电话给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个堆栈的数组并通过索引访问它们，那么你只需要改变索引variables的值）。 一切都在堆栈操作术语的O（1）中。
是的，我知道它是可争辩的，因为我们隐含了超过3个堆栈，但是也许它给了其他人好的想法。
编辑：解释示例：
| | | |3| | | | | | | |_| | | | | | |_____| | | | | | | | | |2| | | | | |_| | | | |_________| | | | | |1| | | |_| | |_____________|
我在这里用一点ASCII-art来显示Stack1。
每个元素都被包装在一个元素堆栈中（所以我们只有types安全的堆栈）。
您看到要删除我们首先popup第一个元素（这里包含元素1和2的堆栈）。 然后popup下一个元素，然后解包1.然后我们说第一个堆栈就是我们新的Stack1。 说多一点function – 这些列表是由2个元素的堆栈实现的，其中顶部元素是cdr，并且第一个/下面的顶部元素是汽车 。 另外两个帮助堆栈。
特别棘手的是插入，因为你不得不深入到嵌套堆栈添加另一个元素。 那就是为什么Stack2在那里。 Stack2总是最内层的堆栈。 然后添加只是推入一个元素，然后推上一个新的Stack2（这就是为什么我们不允许在我们的出列操作中触摸Stack2）。
我要去尝试一个certificate，certificate它不能做到。
假设有一个由3个堆栈模拟的队列Q，A，B和C.
断言
-
ASRT0：=此外，假设Q可以模拟O（1）中的{queue，dequeue}操作。 这意味着对于每个要模拟的队列/出队操作，存在一个特定的堆栈推送/popup序列。
-
不失一般性，假设队列操作是确定性的。
将队列为Q的元素根据它们的队列顺序编号为1,2，…，第一个队列为Q的元素定义为1，第二个元素定义为2，依此类推。
确定
-
Q(0) :=Q中有0个元素时Q的状态（因此A，B和C中有0个元素） -
Q(1) :=Q(0)上的一个队列操作后的Q（和A，B和CQ(0) -
Q(n) :=Q(0)上的n个队列操作之后的Q（以及A，B和CQ(0)
确定
-
|Q(n)| :=|Q(n)| :=Q(n)的元素数（因此|Q(n)| = n） -
A(n) :=当Q的状态是Q(n)时，堆栈A的状态 -
|A(n)| :=|A(n)| :=A(n)中元素的个数A(n)
类似的定义堆栈B和C.
平凡，
|Q(n)| = |A(n)| + |B(n)| + |C(n)| ---
|Q(n)| n。显然是无限的
因此， |A(n)|至less一个 ， |B(n)| 或|C(n)| 在…上是无限的
WLOG1 ，假设堆栈A是无界的，堆栈B和C是有界的。
定义* B_u := B的上界* C_u := C *的上界K := B_u + C_u + 1
WLOG2 ，对于一个n使得|A(n)| > K |A(n)| > K ，从Q(n)selectK个元素。 假设这些元素中有A(n + x)在A(n + x) ，对于所有x >= 0 ，即元素总是在堆栈A中，不pipe有多less个队列操作完成。
-
X :=那个元素
然后我们可以定义
-
Abv(n) :=堆栈A(n)中高于X的项目数 -
Blo(n) :=堆栈A(n)中低于X的元素的数量| A（N）| = Abv（n）+ Blo（n）
ASRT1 :=从Q(n)出列X所需的popup数量至less是Abv(n)
从（ ASRT0 ）和（ ASRT1 ）开始， ASRT2 := Abv(n)必须是有界的。
如果Abv(n)是无界的，那么如果需要20次出队来从Q(n)出列X，那么至less需要Abv(n)/20popup。 哪一个是无限的 20可以是任何常数。
因此，
ASRT3 := Blo(n) = |A(n)| - Abv(n)
必须是无限的。
WLOG3 ，我们可以从A(n)的底部selectK个元素，其中一个在A(n + x)对于所有的x >= 0
X(n) :=对于任何给定的n，该元素
ASRT4 := Abv(n) >= |A(n)| - K
每当一个元素排队到Q(n) …
WLOG4 ，假设B和C已经被填充到它们的上限。 假设已经达到了X(n)以上元素的上界。 然后，一个新元素进入A.
WLOG5 ，假设结果，新的元素必须在X(n)之下input。
ASRT5 :=将元素放置在X(n) >= Abv(X(n))以下所需的popup数量
从(ASRT4) ， Abv(n)在n上是无界的。
因此，将元素放在X(n)之下所需的popup数是无限的。
这与ASRT1相矛盾，因此，不可能模拟3个堆栈的O(1)队列。
即
至less有一个堆栈必须是无界的。
对于停留在堆栈中的元素，它上面的元素数量必须是有界的，否则去除该元素的出队操作将是无限的。
但是，如果它上面的元素数目是有限的，那么它将达到极限。 在某个时候，一个新的元素必须在它下面input。
由于我们总是可以从堆栈中最小的几个元素中select一个旧元素，因此可以在它上面有无限个元素（基于无界堆栈的无限大小）。
要在它下面input一个新的元素，因为上面有一个无限的元素，所以需要无限数量的pop元素将新的元素放在它下面。
这就是矛盾。
有5个WLOG（不失一般性）陈述。 从某种意义上说，他们可以直观地被理解为是真实的（但是假设它们是5，可能需要一些时间）。 没有普遍性的formscertificate可以被推导出来，但却是非常漫长的。 他们被省略了。
我确实承认，这种疏忽可能会使WLOG声明受到质疑。 有了程序员对错误的偏执，如果你愿意的话，请确认WLOG语句。
第三个堆栈也是不相关的。 重要的是有一组有界的堆栈和一组无限的堆栈。 一个例子的最小需求是2个堆栈。 当然，堆栈的数量是有限的。
最后，如果我是对的，没有证据，那么应该有一个更容易的归纳certificate。 可能基于每个队列之后发生的事情（logging给定队列中所有元素的集合如何影响出队的最坏情况）。
注意：这意味着对具有单链表的实时（恒定时间最坏情况）队列的function实现进行评论。 我不能因为声誉而添加评论，但如果有人可以将此更改为由antti.huima附加到答案的评论，那将会很好。 再说一次，评论有点长。
@ antti.huima：链接列表不同于堆栈。
-
s1 =（1 2 3 4） – 一个带有4个节点的链表，每个节点指向右边的一个，并保存值1,2,3和4
-
s2 =popup（s1）— s2现在是（2 3 4）
在这一点上，s2相当于popup（s1），其行为像一个堆栈。 不过，s1仍然可以参考！
- s3 =popup（popup（s1））— s3是（3 4）
我们仍然可以看到s1得到1，而在一个合适的堆栈实现中，元素1从s1消失了！
这是什么意思？
- s1是对堆栈顶部的引用
- s2是对堆栈第二个元素的引用
- s3是参考第三…
现在创build的附加链接列表都可以作为引用/指针！ 有限数量的堆栈不能做到这一点。
根据我在论文/代码中看到的，algorithm都使用链表的属性来保留引用。
编辑：我只指的是2和3链接列表algorithm利用链接列表的属性，因为我先读它们（他们看起来更简单）。 这并不意味着表明它们是否适用，只是为了解释链接列表不一定是完全相同的。 当我有空的时候，我会读6。 @Welbog：感谢您的更正。
懒惰也可以用类似的方式模拟指针function。
使用链表解决了另一个问题。 这个策略可以用来在Lisp中实现实时队列（或者至lessLisp坚持从链表中构build所有东西）：参考“Pure Lisp中的实时队列操作”（通过antti.huima的链接链接）。 使用O（1）操作时间和共享（不可变）结构来devise不可变列表也是一个不错的方法。
您可以在两个堆栈中以分期固定时间执行此操作：
------------- -------------- | | ------------- --------------
添加是O(1) ，如果你想从其中取出的一边不是空的，则删除O(1) ，否则O(n) （将另一个堆栈分成两部分）。
诀窍是看O(n)操作只会在O(n)时间完成（如果你分割，例如一半）。 因此，一个操作的平均时间是O(1)+O(n)/O(n) = O(1) 。
虽然这可能会出现问题，但是如果您使用的是基于数组的堆栈（最快）的命令式语言，那么您将只能使用分配的常量时间。
