我在一本算法书( Robert Sedgewick和Kevin Wayne的Algorithms, 4th Edition)中遇到了这个问题。
具有三个堆栈的
队列。实现一个具有三个堆栈的队列,以便每个队列操作都需要恒定(最坏情况下)数量的堆栈操作。警告:难度很高。
我知道如何使用2个堆栈来创建一个队列,但是我找不到使用3个堆栈的解决方案。有什么想法吗?
(哦,这不是家庭作业:)
发布于 2011-04-07 05:50:29
摘要
的所有约束内的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个堆栈的算法,正如我们已经知道的那样,查看这里的答案。因此,我猜这个问题仍然悬而未决,无法找到算法(或者证明找不到算法)。
发布于 2011-04-06 22:33:00
好吧,这真的很难,我能想出的唯一解决方案,记得我对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的原因)。
发布于 2011-04-07 01:34:30
我将尝试一个证明来证明这是不可能的。
假设有一个队列Q,它由3个堆栈A、B和C模拟。
断言
进一步,假设Q可以模拟O(1)中的操作{
的( simulated.
让在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) :=
大于XBlo(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个堆栈。当然,堆栈的数量必须是有限的。
最后,如果我是对的,没有证据,那么应该有一个更容易的归纳证明。可能基于每个队列之后发生的事情(在给定队列中所有元素的集合的情况下,跟踪它对出队的最坏情况的影响)。
https://stackoverflow.com/questions/5538192
复制相似问题