用6个栈实现O(1)队列

发现问题

上周瞎逛的时候，看到一个很有意思的问题，如何实现一个 O(1) 时间复杂度的队列。

咋一看好像挺容易的，但仔细想了一下好像也没那么简单，于是乎在网上找了一下，居然找到了一篇文章，描述了一种使用 6 个栈来实现的 O(1) 队列的算法，还挺有意思的。

文章链接在这里，文章不长，感兴趣的可以去阅读一下 Real Time Queue Operations in Pure LISP*

一般情况（2栈 H,P）

首先考虑最一般的情况用两个栈模拟队列，无非就是一个入队一个出队，比如栈 T 入 H 出，进出的时间复杂度一般情况都是 O(1)，唯一的例外就是出队时，发现 H 为空的时候，需要把 T 里的元素依次 pop 并 push 进 H 中，可以想象到最坏的时间复杂度就变成了 O(n)。

魔改一（3栈 H,P,H_p）

然后作者就开始魔改了。我们可以看到关键就在于出队的某些时刻会出现需要在两个栈之间倒腾元素的操作费时，一个常见的想法就是把费时的操作均摊到每次操作当中去，用分时的思路来降低整体时间复杂度，当然想降低时间复杂度必然导致空间复杂度上升。假设我们增加一个栈 H_p，在 H 每次出队的时候，都把 T 中的一个元素转移到 H_p 中，这样当 H 为空的时候，直接交换 H 跟 H_p，就能够保证任何时候出队时间复杂度依然是 O(1)。

魔改二（4栈 H,P,H_p,T_p）

然而这样依然不够，因为不可能一直都只有出队的操作，在把 T 中的元素转移到 H_p 的过程中，依然有可能存在入队列的操作。所以再引入一个栈 T_p ，用来保存在转移过程中新入队的元素。在 T 未完全转移至 H_p 时，所有的入队操作压入的元素都暂存在 T_p 中。当 T 也为空时，我们交换 H 跟 H_p，T 跟 T_p，再把入队出队操作交回 H 跟 T 就好了。

魔改三（5栈 H,P,H_p,T_p,H_r）

依然不完美，因为上面我们假设的都是在把 T 中的元素转移至 H_p 后，H 早已为空，所以可以立刻交换 H 跟 H_p。但实际上这个情况并不一定会存在。如果 T 转移空了，H 不为空，则我们无法直接交换 H 跟 H_p，因此，我们还需要再引入一个栈 H_r，在 T 转移的同时，我们也进行一个操作把 H 中的元素转移至 H_r，并在最后把 H_r 中的元素追加转移到 H_p 里，最后再交换 H 跟 H_p，这样队列的顺序就没问题了。这样每次入队操作都进行两步转移：H -> H_r，T -> H_p，当 T 为空时，继续 H_r -> H_p，直到 H_r 为空了，再交换 H 跟 H_p，T 跟 T_p。

魔改四（6栈 H,P,H_p,T_p,H_r,h）

上面还存在一个问题，就是在把 H 中的元素转移到 H_r 的过程中，如果需要出队怎么办？

我们引入最后一个栈 h，当我们决定要开始从 H 中转移元素到 H_r 的时刻，让 h 成为 H 的一个浅拷贝，然后出队操作由 h 来进行，因为每次入队/出队都会进行一次元素转移，所以 H 的位置始终会比 h 要低，不用担心想要转移的元素已经出队了。同时，由于存在出队的操作穿插在整个转移过程中，所以当 H 转移空时，我们不一定需要把 H_r 中全部的元素转移到 H_p 中了，因为从逻辑上来说已经有一些元素出队了，不在队列中了，所以我们在转移过程中需要记录一下出队了几个元素，最后把 H_r 转移到 H_p 中的时候相应的减掉那些元素就好。

机智的人已经发现，这里还存在一个问题，怎么保证在 h 出队为空之前 T 中跟 H_r 中需要转移的元素都已经全部转移至 H_p 中了呢？

答案就在于我们选择何时开始进行这个转移步骤。作者敏锐的发现，选择在 T 中的元素超过 H 中的元素的时刻开始转移，就能够保证在 h 不为空的时候，整个转移过程全部完成。证明如下：

T 中的元素超过 H 中的时刻只会发现在入队操作。 我们选择在第 k + 1 次入队时开启转移，此时 H 中应该有 k 个元素。T 中有 k + 1 个元素。 我们可以在接下来的每一个入队或者出队操作转移 1 个 T 中的元素至 H_p 中，1 个 H 中的元素至 H_r 中，这样只需要 k + 1 次操作即可完成清空 T 跟 H。 接下来需要把 H_r 中的元素转移至 H_p，这里又需要 k 次操作。所以我们一共需要 2k + 1 次操作才能完成清空 T、H、H_r，准备好 H_p。 而 h 的长度是 k，极端情况下后续全部是出队操作的情况下只能提供 2k 次操作机会。而第 k + 1 个元素入队的同时我们开启转移，也有 2 次操作机会，所以我们一共能够拥有的是 2k + 2 次操作机会，比需要的 2k + 1 次多。 因此我们能够在 h 未空之前完成全部的转移工作。

写了个 demo 测了一下，代码在这里 o1_queue，还挺有意思的。

后来在 StackOverflow 看到了更详细的讨论，发现大家在努力找到 3 个栈的实现方式，不过目前的最好方法使用 3 个栈，但用到了懒加载技术，那就不完全是使用栈实现了。还看到了更诡异的数据结构 3 个栈中栈实现的方法，感兴趣的可以去看看。