如何实现三个堆栈的队列？

Question

我在算法书(Algorithms,第4版,Robert Sedgewick和Kevin Wayne)中遇到了这个问题.

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

我知道如何使用2个堆栈创建一个队列,但我找不到3个堆栈的解决方案.任何的想法 ？

(哦,这不是作业:))

Answer 1

摘要

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

细节

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

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

另一个是O(1),但使用SIX堆栈.但是,它没有延迟执行.

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

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

gusbro:"正如@Leonel前几天说的那样,我认为与Sedgewick教授核实是否知道解决方案或有一些错误是公平的.所以我确实给他写信.我刚收到回复(虽然不是来自他自己,但是来自普林斯顿大学的一位同事)所以我想与大家分享.他基本上说他知道没有使用三个堆栈的算法和强加的其他约束(比如不使用惰性评估).他确实知道使用的算法我们已经知道在这里查看答案的6个堆栈.所以我想问题仍然是找到一个算法(或证明一个无法找到)的问题."

Answer 2

好吧,这真的很难,而且我能想到的唯一解决方案,让我想起Kirks解决Kobayashi Maru测试(不知何故被骗):我的想法是,我们使用堆栈堆栈(并使用它来建模列表) ).我调用操作en/dequeue并推送和弹出,然后我们得到:

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个堆栈的数组并通过索引访问它们,你只需要改变索引变量的值).堆栈操作中的所有东西都在O(1)中.

是的,我知道它是有争议的,因为我们隐含了超过3个堆栈,但也许它给你其他人好主意.

编辑:解释示例:

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

我试着用一点ASCII艺术来展示Stack1.

每个元素都包含在一个元素堆栈中(因此我们只有堆栈的类型安全堆栈).

你看到删除我们首先弹出第一个元素(包含元素1和2的堆栈).然后弹出下一个元素然后打开1.然后我们说第一个poped堆栈现在是我们的新Stack1.更具说明功能 - 这些列表由2个元素的堆栈实现,其中顶部元素是cdr,第一个/下面的顶部元素是car.另外两个正在帮助筹码.

Esp棘手的是插入,因为你不得不深入挖掘嵌套堆栈以添加另一个元素.这就是为什么Stack2在那里.Stack2始终是最里面的堆栈.然后添加只是推入一个元素然后按下一个新的Stack2(这就是为什么我们不允许在我们的出列操作中触摸Stack2).