一個介面、兩種內部次序
先進先出隊列傳回仍在隊列中最早加入的項目;堆疊卻移除最近推入的項目。兩個堆疊可把次序反轉兩次,但必須在正確時機轉移。隊列的邏輯次序應獨立於實作堆疊的陣列或鏈結結構來描述。
假設兩個堆疊起初為空,每次堆疊 push 或 pop 花一個基本操作,其他比較、空檢查及傳回項目均為常數時間。空隊列出隊報告下溢;以下成本界只計成功入隊與出隊。
操作及不變量
定義 2.1.1
(雙堆疊隊列)
稱輸入堆疊為 、輸出堆疊為 。入隊把新項目 push 到 。出隊時若 為空,便反覆從 pop 並 push 到 ,直至 清空;然後 pop 並傳回 的頂項。若兩者均空則報告下溢。
定理 2.1.2
(隊列的邏輯次序)
每次操作邊界,隊列由最舊至最新的邏輯次序,是 由頂到底的序列,接上 由底到頂的序列。
證明
(對操作歸納)
起初兩段都空。入隊把新項目放在 的頂部,也就是其由底到頂序列的末尾,因此追加到邏輯隊列。若 非空,其頂項就是最早項目,pop 恰好移除它。若 空而 非空,搬動全部項目會反轉堆疊次序:原本 底部成為 頂部,故原輸入的由底到頂序列成為輸出的由頂到底序列。再 pop 即傳回最舊項目。對操作歸納便證明不變量及先進先出性。
證明透視
為何要等輸出堆疊清空才轉移
已在 的項目都早於目前 的項目。若把較新的輸入項目移到非空 ,它們會置於舊輸出項目之上,改變下一次答案。例如 有 、 有 ,過早轉移會令 在頂部,儘管隊列次序是 。輸出為空的條件保留兩組新舊項目之間的界線。
常見錯誤
(轉移時只搬一項)
設 (由底到頂)、,所以隊列次序是 。若轉移只搬 的頂項,則 ,出隊便傳回 ,而最舊的項目其實是 。轉移必須搬走整個 ,把它的次序反轉,令原來的底部 落在 的頂部。
一次追蹤
例題 2.1.3
(交錯的入隊與出隊)
堆疊均由底到頂書寫。依次入隊 ,得到 。出隊時先轉移成 ,再傳回 ,餘下 。入隊 得 。其後兩次出隊不需轉移,依次傳回 。最後 空,把 轉移並傳回。傳回序列是 。
反例模式
攤銷不代表每次操作都便宜
若 中有 項而 為空,一次出隊需從 pop 次、向 push 次,再從 pop 一次,共 次堆疊操作。即使整段操作序列的每次成功操作有常數攤銷成本,這一次操作的最壞成本仍非常數。
例題 2.1.4
(下溢與單一項目)
兩個堆疊起初都空。出隊發現 與 均空,不作任何堆疊操作便報告下溢。入隊 :。此時出隊要轉移一項,即從 pop 一次、向 push 一次,再從 pop 出 :成本 ,兩個堆疊回復為空。再出隊便報告下溢。成本界只計成功的出隊。
例題 2.1.5
(達到上界的序列)
入隊 :四次 push,,勢能 。第一次出隊轉移四項,再 pop 出 : 次操作,餘下 。其後三次出隊各花一次操作,依次傳回 。總成本是 ,而 。等號成立,因為每件項目都被轉移一次,也都被出隊一次。
計算轉移成本
定理 2.1.6
(操作序列的總成本)
從兩個空堆疊開始,含 次入隊及 次成功出隊的序列至多使用 次堆疊操作。因此每次成功操作的攤銷成本是 ,雖然當 中有 項等待時,單次出隊可花 。
證明
(每件項目至多移動三次)
一段序列有 次入隊和 次成功出隊時,每件項目只被 push 到 一次,最多被轉移一次。總堆疊操作最多 :每次入隊一次 push,每件入隊項目最多一次輸入 pop 和輸出 push,每次成功出隊一次輸出 pop。有些入隊項目可能仍留在某個堆疊,所以這是上界,不是每次都完成轉移的斷言。
也可使用勢能 ,起初為零且永不為負。入隊實際成本一、勢能增加二,攤銷成本為三;不轉移的出隊成本一且勢能不變;轉移 項的出隊實際成本 、勢能減少 ,攤銷成本一。把實際成本加勢能變化逐項相加後望遠鏡相消;由末勢能非負,實際堆疊成本不超過 。起初為空的假設很重要:預先放入 的項目會帶來正的初始勢能。
常見錯誤
(選了太小的勢能)
若以 代替 ,入隊的攤銷成本是 ,但轉移 項的出隊攤銷成本是 ,並非常數,論證便甚麼也沒有證明。因子二支付了項目之後的兩次移動,即從 pop 及 push 到 ;取 時,轉移的攤銷成本是 。
練習與解答
快速檢查
(若 、 均由底到頂列出,寫出邏輯隊列。)
解答 · 答案
:先由頂到底讀 ,再由底到頂讀 。
快速檢查
(由空開始,入隊 ,出隊一次,入隊 ,再出隊兩次。傳回甚麼?)
解答 · 答案
依次傳回 。傳回 後 仍在 的頂部,必須早於新加入的 。
快速檢查
(若一次出隊轉移三項,實際堆疊操作成本及勢能變化各是多少?)
解答 · 答案
成本 ; 減少三,故 ,攤銷成本為一。
快速檢查
(若 非空,為何每次入隊時都轉移 是錯誤的?)
解答 · 答案
它可能把新項目放到較舊輸出項目之上。證明中 的 與 的 例子顯示了次序違反。