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

我在一本算法书(罗伯特·塞奇威克和凯文 · 韦恩的 算法，第四版)中偶然发现了这个问题。

用三叠排队。实现一个包含三个堆栈的队列，以便每个队列操作接受固定(最坏情况下)数量的堆栈操作。警告: 高难度。

我知道如何使一个队列与2堆栈，但我不能找到解决方案与3堆栈。知道吗？

(哦，还有，这不是家庭作业)

15122 次浏览
小开

好吧，这真的很难，而我能想到的唯一解决方案，让我想起了柯克斯对小林丸号测试的解决方案(不知怎么作弊了) : 其思想是，我们使用堆栈(并使用这个来建模一个列表)。 我调用运算 en/dequeue 和 push and 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-art 来展示 Stack1。

每个元素都包装在单个元素堆栈中(因此我们只有类型安全堆栈)。

您可以看到删除我们首先弹出第一个元素(包含在这里的元素1和2的堆栈)。然后弹出下一个元素，在那里展开1。然后，我们说第一个被弹出的栈现在是我们的新 Stack1。为了说明更多的功能-这些列表是由2个元素堆栈实现的，其中顶部元素是 Cdr，顶部元素的第一个/第二个元素是 车。另外两个在帮忙。

特别是棘手的是插入，因为您必须以某种方式深入到嵌套堆栈添加另一个元素。这就是 Stack2在那里的原因。Stack2始终是最内层的堆栈。然后，Add 只是将一个元素放入，然后将一个新的 Stack2放到顶部(这就是为什么在 dequeue 操作中不允许触及 Stack2的原因)。

小开

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

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

断言

  • ASRT0: = 此外，假设 Q 可以模拟 O (1)中的操作{ queue，dequeue }。这意味着对于要模拟的每个队列/队列操作，都存在一个特定的堆栈推/持久化序列。

  • 不失一般性，假设队列操作是确定的。

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

定义一下

  • 当 Q 中有0个元素(因此 A、 B 和 C 中有0个元素)时，Q 的状态
  • 在 Q(0)上执行1个队列操作后 Q (以及 A、 B 和 C)的状态
  • 在 Q(0)上执行 n 个队列操作后 Q (以及 A、 B 和 C)的状态

定义一下

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

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

小事一桩,

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


---

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

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

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

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

对于 |A(n)| > K的 n，从 Q(n)中选择 K 元素。假设其中1个元素在 A(n + x)中，对于所有的 x >= 0，也就是说，无论执行多少队列操作，元素始终在堆栈 A 中。

  • X :=那个元素

然后我们再定义

  • 堆栈 A(n)中大于 X 的项目数

  • 堆栈 A(n)中低于 X 的元素数

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

从 Q(n)中取出 X 所需的持久性有机污染物数量至少为 Abv(n)

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

如果 Abv(n)是无界的，那么如果从 Q(n)中取出 X 需要20个队列，那么它至少需要 Abv(n)/20持久化。这是无限的。20可以是任何常数。

所以,

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

必须是无限的。

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

对于任意给定的 n

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

每当一个元素排队进入 Q(n)..。

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

因此，假设新元素必须输入在 X(n)之下。

将一个元素置于 X(n) >= Abv(X(n))之下所需的持久性有机污染物的数量

从 (ASRT4)开始，Abv(n)在 n 上是无界的。

因此，将一个元素放置在 X(n)之下所需的弹出窗口的数量是无限的。

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

也就是说。

至少有一个堆栈必须是无界的。

对于停留在该堆栈中的元素，其上的元素数量必须是有界的，否则删除该元素的取队列操作将是无界的。

但是，如果它上面的元素数是有界的，那么它将达到一个极限。在某个点上，新元素必须在它下面输入。

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

要在它下面输入一个新元素，因为它上面有无限多个元素，所以需要有无限多个弹出窗口将新元素放在它下面。

因此，矛盾。

有5个 WLOG (不失一般性)声明。从某种意义上说，它们可以被直观地理解为正确的(但鉴于它们是5，这可能需要一些时间)。没有一般性丢失的形式证明是可以推导出来的，但是它非常冗长。都被省略了。

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

第三个堆栈也是无关紧要的。重要的是存在一组有界堆栈和一组无界堆栈。一个示例最少需要两个堆栈。堆栈的数量当然是有限的。

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

小开
最佳答案

总结

  • O (1)算法已知有6个栈
  • O (1)算法已知有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堆栈算法。

更新: 另一个相关的算法在 Holger Petersen 发表于第七届计算和组合学年会的论文“堆栈与数组”中被描述。你可以在谷歌图书中找到这篇文章。检查第225-226页。但是这个算法实际上并不是实时的模拟，而是对一个双端队列在三个栈上的线性时间模拟。

Gusbro: “就像@Leonel 几天前说的，我认为如果 Sedgewick 教授知道一个解决方案或者有一些错误的话，我们应该去问问他。所以我给他写了信。我刚刚收到一个回复(虽然不是来自他自己，而是来自普林斯顿的一个同事) ，所以我想和大家分享一下。他基本上说他知道没有使用三个栈的算法和其他强加的限制(比如不使用惰性评估)。他确实知道一个使用六层叠加的算法我们已经知道了，看看这里的答案。因此，我认为这个问题仍有待于找到一种算法(或者证明无法找到算法)。”

小开

注意: 这是对使用单链表的实时(常数时间最坏情况)队列的功能实现的注释。我不能添加评论由于声誉，但它将是很好的，如果有人可以改变这个评论附加到答案 antti.huima。不过话说回来，评论的时间有点长。

@ antti. huima: 链表与堆栈不同。

  • S1 = (1234)——一个有4个节点的链表，每个节点指向右边的一个节点，并保存值1、2、3和4

  • S2 = pop (s1)——-s2现在是(234)

此时，s2等价于弹出(s1) ，其行为类似于堆栈！

  • S3 = pop (pop (s1))——-s3是(34)

我们仍然可以查看 s1以得到1，而在适当的堆栈实现中，元素1从 s1中消失了！

这是什么意思？

  • S1是对堆栈顶部的引用
  • S2是对堆栈第二个元素的引用
  • S3指的是第三个..。

现在创建的附加链表每个都作为一个引用/指针! 有限数量的堆栈无法做到这一点。

从我在文章/代码中看到的，算法都利用了链表的这一特性来保留引用。

编辑: 我只是指2和3链表算法利用了链表的这个属性，因为我首先读了它们(它们看起来更简单)。这并不意味着它们是否适用，只是解释链表不一定相同。等我有空的时候，我会读有6的那本。@ Welbog: 谢谢纠正。

懒惰还可以以类似的方式模拟指针功能。

使用链表解决了一个不同的问题。这个策略可以用来在 Lisp 中实现实时队列(或者至少是坚持从链表构建所有东西的 Lisps) : 参考“ Pure Lisp 中的实时队列操作”(通过 antti.huima 的链接链接)。这也是设计具有 O (1)操作时间和共享(不可变)结构的不可变列表的好方法。

小开

你可以用两个堆栈在摊销的常量时间内完成:

------------- --------------
| |
------------- --------------

如果您希望从中取出的那一边不是空的，那么 Add 为 O(1)，delete 为 O(1)，否则为 O(n)(将另一个堆栈分成两部分)。

诀窍是要确保 O(n)操作只在每次 O(n)时执行(如果分割，例如分成两半)。因此，操作的平均时间是 O(1)+O(n)/O(n) = O(1)。

虽然这可能像一个问题，如果你使用命令式语言与数组为基础的堆栈(最快) ，你将只有摊销常量时间无论如何。


提交答案