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

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (16)

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

排队三堆。实现一个有三个堆栈的队列,以便每个队列操作都有一个常量(最坏情况)的堆栈操作。警告:难度高。

我知道如何制作2个堆栈的队列,但我找不到3个堆栈的解决方案。任何想法 ?

提问于
用户回答回答于

概要

  • 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 ,看起来他实际上只使用了两个堆栈,用于O(1)版本,它具有惰性评估。问题在于它的确基于懒惰评估。问题在于它是否可以在没有懒惰评估的情况下转换为3栈算法。

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

用户回答回答于

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层以上的隐含,但也许它给了你们其他人好的想法。

扫码关注云+社区