因為這個解法有點複雜，因此單獨開一貼介紹。《演算法（第四版）》中的題目是這樣的：1.3.49棧與隊列。用有限個棧實現一個隊列，保證每個隊列操作（在最壞情況下）都只需要常數次的棧操作。那麼這裡就使用六個棧來解決這個問題。這個演算法來自於這篇論文。原文里用的是 Pure Lisp，不過語法很簡單，還是很容易... ...
因為這個解法有點複雜，因此單獨開一貼介紹。
《演算法（第四版）》中的題目是這樣的：
1.3.49
棧與隊列。
用有限個棧實現一個隊列，
保證每個隊列操作（在最壞情況下）都只需要常數次的棧操作。
那麼這裡就使用六個棧來解決這個問題。
這個演算法來自於這篇論文。
原文里用的是 Pure Lisp，不過語法很簡單，還是很容易看懂的。
先導知識——用兩個棧模擬一個隊列
如何使用兩個棧來模擬一個隊列操作？
這是一道很經典的題目，答案也有很多種，這裡只介紹之後會用到的一種方法。
首先我們有兩個棧，H 和 T，分別用作出隊和入隊用。
這樣，入隊操作等同於向 T 添加元素，T 的入棧操作只需要 O(1) 時間。
如果 H 不為空，出隊操作等同於 H 彈棧，H 的彈棧操作也只需要 O(1) 時間。
但如果 H 為空，則需要將 T 中的元素依次彈出並壓入到 H 中，這是一個 O(n) 的操作。
顯然，這種方式中，出隊操作的最壞時間複雜度是 O(n)，並不滿足題目要求。
分攤 O(n)
那麼，怎麼解決這個問題呢？
一個很自然的想法是，如果在棧 H 變為空之前，我們就能逐步將棧 T 的內容彈出並壓入到另一個棧 H' 中，等到棧 H 為空時，直接交換 H 和 H' 即可。
假設目前的隊列狀態是這樣，有三個元素等待出隊，還有三個元素等待入隊。
現在依次讓三個元素出隊，與此同時我們讓棧 T 中的元素依次進入 H' 中。
每一次出隊都執行兩個操作，元素出隊和元素複製（Pop & Push），時間複雜度 O(1) + O(1) + O(1) = O(1)。
第一次操作（出隊）
第二次操作（出隊）
第三次操作（出隊）
現在棧 H 和棧 T 都為空，下一次出隊操作時，我們直接交換棧 H 和棧 H'（由於是交換引用，因此時間複雜度仍為 O(1)）。
之後再進行出隊操作。
這就是這個演算法基本想法，在棧 H 變為空之前，分步將棧 T 中的內容分步複製到另一個棧中。
當棧 H 為空時直接用準備好的棧 H' 替代 H，保證時間複雜度為常數。
對複製時 Enqueue 的支持和 T' 的引入
剛纔是一種理想情況，顯然我們的隊列在複製時不可能只發生出隊操作，為了增加對入隊操作的支持，我們引入臨時棧 T'。
例如我們有隊列狀態如下，現在啟動複製進程，入隊操作全部由 T' 完成。
我們進行一次入隊操作和兩次出隊操作，如下組圖所示：
第一次操作（入隊）
第二次操作（出隊）
第三次操作（出隊）
現在 H 和 T 均為空，下一次操作時（不論入隊還是出隊），我們先交換 H 和 H' 以及 T 和 T'，同時讓入隊操作控制權回到 T。
這樣，我們增加了對複製時入隊操作的支持，但還並不完全，只有在理想情況下才可以做到。
h 與 HR ，對複製時出入隊序列支持的擴展
在之前的例子中，當複製結束時 H 總是為空的，現在我們來討論一下複製結束時 H 不為空的情況。
如果複製結束時 H 不為空，直接交換的結果是我們丟失了原來棧 H 中的數據。
因此，在翻轉 T 的同時，我們還應翻轉 H 到 HR，併在最後將 HR 的內容再度翻轉並添加到 H' 上。
這個過程可以以下圖方式進行：
初始狀態：
第一次操作（入隊），H->HR ,T->H'，時間複雜度 O(1) + O(1) + O(1) + O(1) = O(1)。
第二次操作（入隊）
第三次操作（入隊）
第四次操作（入隊）
第五次操作（入隊）
第六次操作（出/入隊執行前）
這樣我們就解決了 H 複製結束後不為空的問題，代價是引入了兩個額外的問題：
- 操作次數增加到了 2k 次，k 代表棧 T 中的元素數量。（如果當 T 中元素數量大於 H 中元素數量時開始複製）
- 由於 H 被用於複製進程，我們無法在複製過程中支持出隊操作。
第一個問題解決方案比較簡單，我們可以在每一次出/入隊操作執行時進行兩次的複製步驟（對 T 和 H 進行兩次的 Pop 操作），時間複雜度仍為 O(1)。
第二個問題我們通過引入棧 h 來解決。
h 用於在複製時代替 H 執行出隊功能，它會在複製開始時自動變為棧 H 的一個淺拷貝（也就是說，h 和 H 共用同一片記憶體空間，但它們用於指示棧頂位置的指針相互獨立）。
現在我們有了全部 6 個棧，它們的功能如下圖所示（為了方便介紹我將一些棧的位置做了調換）。
由於我們並不能預知接下來會發生的操作，因此當 H 棧中的元素數量第一次小於 T 棧中的元素數量時，我們就必須啟動複製進程了（總是假設接下來全部都是出隊操作）。我們引入一個布爾類型變數 IsCopying 來指示覆制進程。
現在我們進行第一次入隊操作，IsCopying = true，開始複製。
首先 h 變為 H 的淺拷貝，這個過程是 O(1) 的。
如果在複製過程中有出隊操作，作為 H 的翻轉 HR 中就有一個元素不再需要複製，我們引入一個變數 needcopy 來記錄 HR 中需要複製的元素數量。
接下來是兩次複製操作，T 和 H 分別有兩個元素進入了 H' 和 HR 。
然後是第二次出/入隊操作，這次我們選擇出隊，1 出隊後顯然 HR 中的 1 不再需要複製，needcopy – 1。
隨後再是兩次複製操作，第一次將 H 中的 3 移到 HR 中，needcopy + 1，T 中的 5 移到 H' 中；第二次只將 T 中的 4 移到 H' 中。
第三次出/入隊操作我們選擇入隊，8 入隊。隨後 HR 中的兩個元素進入了 H'，needcopy – 2。
由於 needcopy 變成了 0，我們再額外進行一次交換操作，並將 IsCopying 置為 false。
至此，完整的演算法運行完畢。
有關複製開始時機的證明
這裡我們選擇了在第 k + 1 個元素入隊時開始複製，現在證明一定能夠在 h 空之前完成複製：
假設複製開始時 H 有 k 個元素，T 有 k + 1個元素。
完成第一輪複製（H->HR , T->H'）需要 k + 1 次操作，
完成第二輪複製（H->H'）需要 k 次操作，總共需要 2k + 1 次操作才能完成複製。
而 h 的長度為 k，能夠提供 2k 次的操作機會。第 k + 1 個元素入隊時也能提供 2 次操作機會，因此一共是 2k + 2 次操作機會。
由於 2k + 1 < 2k + 2，我們證明瞭該演算法能夠及時完成複製工作。
程式設計
根據之前的內容，我們可以開始設計程式了。主要實現三個功能，Enqueue(), Dequeue() 和 Peek()。
根據演算法要求我們添加一個進行複製時操作的函數 OneStep()，用於執行元素的複製，棧交換等操作。
Peek() 只需要根據是否在進行複製選擇棧 h 或棧 H 進行 Peek()。
Enqueue()
- 如果不處於複製狀態
- 如果 H.Length – T.Length > 0，直接將元素壓入棧 T。
- 否則令 IsCopying = true，h 進行淺拷貝，進行兩次的 OneStep。
- 如果處於複製狀態，將元素壓入 T'，進行兩次的 OneStep。
Dequeue()
- 如果不處於複製狀態
- 如果 H.Length – T.Length > 0，直接從 H 彈出元素。
- 否則從 H 彈出元素，IsCopying = true，h 進行淺拷貝，進行兩次的 OneStep。
- 如果處於複製狀態，從 h 彈出元素，needcopy - 1，進行兩次的 OneStep。
OneStep()
- 如果不處於複製狀態，什麼也不做。
- 如果處於複製狀態。
- 如果 H 和 T 都不為空，從 H 搬運一個元素至 HR ，從 T 搬運一個元素至 H' ，needcopy + 1。
- 如果 H 為空但 T 不為空，從 T 搬運一個元素至 H' 。
- 如果 H 和 T 都為空，但 needcopy > 1，從 HR 搬運一個元素至 H' ，needcopy – 1。
- 如果 H 和 T 都為空，但 needcopy = 1，從 HR 搬運一個元素至 H' ，needcopy – 1，交換 H 和 H' 以及 T 和 T'，其他棧置空，退出複製狀態。
- 如果 H 和 T 都為空，但 needcopy = 0，交換 H 和 H' 以及 T 和 T'，其他棧置空，退出複製狀態。
程式實現（C#）
顯然光演示是不夠的，這裡放上我自己寫的 C# 代碼供參考（HH = H', TT = T'）：
using Generics; namespace _1._3._49 { class StackQueue<Item> { Stack<Item> H; Stack<Item> T; Stack<Item> h; Stack<Item> HH; Stack<Item> TT; Stack<Item> Hr; bool isRecopying; int nowcopying; public StackQueue() { this.isRecopying = false; this.nowcopying = 0; this.H = new Stack<Item>(); this.T = new Stack<Item>(); this.h = new Stack<Item>(); this.HH = new Stack<Item>(); this.TT = new Stack<Item>(); this.Hr = new Stack<Item>(); } public Item Peek() { if (this.isRecopying) { return h.Peek(); } else { return H.Peek(); } } public void Enqueue(Item item) { if (!this.isRecopying && Lendiff() > 0) { this.nowcopying = 0; this.T.Push(item); } else if (!this.isRecopying && Lendiff() == 0) { this.T.Push(item); this.isRecopying = true; this.h = this.H.Copy(); OneStep(OneStep(this)); } else if (this.isRecopying) { this.TT.Push(item); OneStep(OneStep(this)); } } public int Lendiff() { return this.H.Size() - this.T.Size(); } public Item Dequeue() { if (!this.isRecopying && Lendiff() > 0) { return this.H.Pop(); } else if (!this.isRecopying && Lendiff() == 0) { Item temp = this.H.Pop(); this.HH = this.H; this.isRecopying = true; OneStep(OneStep(this)); return temp; } else { Item temp = this.h.Pop(); this.nowcopying--; OneStep(OneStep(this)); return temp; } } private static StackQueue<Item> OneStep(StackQueue<Item> q) { if (q.isRecopying && !q.H.IsEmpty() && !q.T.IsEmpty()) { q.nowcopying++; q.HH.Push(q.T.Pop()); q.Hr.Push(q.H.Pop()); } else if (q.isRecopying && q.H.IsEmpty() && !q.T.IsEmpty()) { q.isRecopying = true; q.HH.Push(q.T.Pop()); } else if (q.isRecopying && q.H.IsEmpty() && q.T.IsEmpty() && q.nowcopying > 1) { q.isRecopying = true; q.nowcopying--; q.HH.Push(q.Hr.Pop()); } else if (q.isRecopying && q.H.IsEmpty() && q.T.IsEmpty() && q.nowcopying == 1) { q.isRecopying = false; q.nowcopying--; q.HH.Push(q.Hr.Pop()); q.H = q.HH; q.T = q.TT; q.HH = new Stack<Item>(); q.TT = new Stack<Item>(); q.Hr = new Stack<Item>(); q.h = new Stack<Item>(); } else if (q.isRecopying && q.H.IsEmpty() && q.T.IsEmpty() && q.nowcopying == 0) { q.isRecopying = false; q.H = q.HH; q.T = q.TT; q.HH = new Stack<Item>(); q.TT = new Stack<Item>(); q.Hr = new Stack<Item>(); q.h = new Stack<Item>(); } return q; } } }
後記
事實上這道題還沒有結束，在英文版的《演算法（第四版）》中，這道題要求的是只使用 3 個棧而不是有限個，具體可以查看 Stackoverflow 上的討論。
討論的結果是 6 個棧顯然可行，3 個棧的解決方案用到了懶載入技術，還有一種 3 棧方案太過取巧（3 個“棧的棧“），最後還有人試圖證明 3 棧方案根本不可能。
顯然後來作者意識到了問題因此改成了有限個棧，那麼三個棧實現 O(1) 隊列是否可能呢？
反正我是不知道怎麼弄，尤其是看完 6 個棧的實現方案之後。 ╮（╯＿╰）╭
