本節延伸已有的雙堆疊隊列課,該課已證明先進先出與基本攤銷界。本節增加內部轉移不變量、隊首觀察操作、實作細節及底層成本條件。
堆疊移除最新的元素,隊列卻必須移除最早仍在等待的元素。把一整個堆疊轉移到另一個,會反轉次序,因此兩個堆疊可以組成隊列。難點不只是反轉,而是知道何時反轉才能保留舊元素與新到元素之間的先後。
這個實作也提供了一個精簡而完整的攤銷分析例子。單次隊列操作可能轉移大量元素,但一長串操作的堆疊總工作量仍為線性。本節會證明正確性和成本,包括一個容易忽略的事實:查看隊首可以重整內部表示,卻不改變抽象隊列。
精確說明兩個堆疊代表甚麼序列
定義 2.3.1
(輸入堆疊、輸出堆疊與抽象 FIFO 序列)
設 是輸入堆疊, 是輸出堆疊。每個堆疊都按由底至頂寫成序列,右端是頂部。隊列由最舊至最新的序列為
其中 表示序列串接。兩個堆疊初始均為空。每次入隊的項目都恰好在其中一個堆疊,它們的總長度就是隊列長度。
enqueue(x) 把 加到隊尾。隊列非空時,front() 回傳最舊值而不移除,dequeue() 則回傳並移除該值。隊列為空時,兩項操作都報錯。
次序約定非常重要。若 、,隊列是 ,不是 。輸出堆疊頂部是最舊等待元素;輸入堆疊底部則是在尚未轉移的到達項目中最舊的一個。
概念視角結構
一條序列和一個可移動的切點
把隊列寫成 ,並令 。此時 存放 , 在頂端; 存放 , 在頂端。入隊在右端加長序列,切點不動;出隊刪去 並令 減一;轉移則把切點移到右端,即 。後文使用的勢能就是 。
常見錯誤
(從錯誤的一端讀取輸出堆疊)
若 、,把隊列寫成 ,就是把輸出堆疊的底部當成最舊元素,出隊便會錯誤地回傳 7。最舊的是輸出堆疊的頂部:隊列是 ,出隊回傳 4。
只有輸出堆疊為空時才轉移
入隊永遠把元素推到 。查看或移除隊首前,使用以下規則:若 為空,就反覆從 彈出一項,再推入 ,直到 為空。若 已非空,就不要轉移任何元素。
定理 2.3.2
(兩個堆疊實作 FIFO 隊列)
由兩個空堆疊開始,入隊時推入 ,只有在 front 或 dequeue 之前 為空時才轉移。每次公開操作之後, 就是抽象隊列的序列:入隊加在隊尾,front 回傳最舊元素,dequeue 移除並回傳它。
證明
(每個公開操作都保留 FIFO 序列)
入隊把 改為 ,所以表示的隊列變成 ,正是所需的隊尾加入。
若 非空,其頂部就是 的第一項,因此也是 的第一項。讀取頂部回傳隊首;彈出它則恰好移除隊列第一項。
若 為空,原輸入序列為 ,完整轉移後得到 、。新抽象序列為 ,與舊隊列相同。之後可按上一段論證讀取或移除輸出頂部。因此,入隊、查看隊首及出隊都實現所述序列條件。
反例模式
把新到元素倒進非空輸出堆疊會破壞 FIFO
由 、 開始,它表示隊列 。若把 9 轉移到非空輸出堆疊,便得到 、,所表示隊列變成 。
最新項目跳到了較舊等待項目前面。因此,「輸出為空」是正確性條件,不只是效能改善。
轉移過程有自己的迴圈不變量
反轉只完成一部分時,簡單的公開抽象式未必仍描述舊隊列。我們需要另一個迴圈不變量,不能太早讀取答案。
引理 2.3.3
(轉移迴圈不變量)
設 為轉移前的輸入序列, 為空。轉移迴圈每一輪都有 ;迴圈在 輪後結束,此時 、。
證明
(舊輸入序列分為尚未轉移與已轉移兩部分)
設轉移前輸入序列為 ,輸出初始為空。迴圈中把 分為 ,其中 、。等價地,
初始 、。從 彈出最後一項再推進 ,就是把該元素放到已轉移後綴 的前端,保留這個分解。每輪令 減一,所以迴圈會終止。
終止時 ,於是 ,公開隊列解讀再次成立。程式會先完成這個內部轉移,才回傳隊首或完成出隊。
反例模式
第一個轉移的是最新元素,不是隊首
對 、,只移動一項後,得到 、。若此時讀取輸出頂部,會回傳 9,但隊首其實是 4。
迴圈不變量仍把舊序列記為 。在轉移完成前,它不支持用公開公式 代表舊隊列。內部中間表示不能被誤當成已完成操作。
追蹤舊元素尚在等待時的新到項目
例題 2.3.4
(兩次轉移服務多次隊首與出隊操作)
表格中的堆疊都按由底至頂排列。回傳欄的破折號表示入隊不回傳隊列元素。
| 操作 | 之後的輸入 I | 之後的輸出 O | 回傳 | 之後的抽象隊列 |
|---|---|---|---|---|
| 入隊 4 | — | |||
| 入隊 7 | — | |||
| 查看隊首 | ||||
| 入隊 9 | — | |||
| 出隊 | ||||
| 入隊 2 | — | |||
| 出隊 | ||||
| 查看隊首 | ||||
| 出隊 |
第一次 front 反轉兩項,第二次則反轉兩個較後到來的項目。兩次查看隊首都不改變抽象隊列序列。9、2 留在輸入堆疊等待,直至較舊的輸出組別已被取完。
例題 2.3.5
(一次昂貴的隊首調用,精確計費)
把 入隊到空隊列,於是 、、。調用 front 從 彈出 、、 並推入 ,得到 、,再讀取頂部,即 。所計工作是 次彈出、 次推入和 次讀取,共 ,其中 。勢能由 降到 ,所以攤銷收費是 。之後緊接的第二次 front 只需 ,不改變勢能。
例題 2.3.6
(空隊列與值 None)
在新建的隊列上,front() 調用 _prepare_front,但輸入串列為空,所以甚麼也不做。輸出串列也是空的,於是引發 IndexError,沒有任何堆疊被改變,工作量為常數。enqueue(None) 之後,front() 轉移唯一的項目,使 _outgoing == [None]。對這個非空串列,not self._outgoing 為假,所以調用回傳 None,隊列長度仍是 。分辨空隊列與存放了 None 的,是例外,而不是回傳值。
因此,隊首操作是抽象隊列的觀察操作,卻未必保持內部表示不變。一旦已有輸出組別,重複查看就只讀取同一頂部。只使用隊列操作的客戶,無論項目當時在哪個內部堆疊,都觀察到相同數值與長度。
把成本計入每次入隊項目的單向旅程
先採用精確成本模型:每次堆疊推入、彈出或讀取頂部各計一單位。出隊用一次可回傳數值的彈出,不是先讀再彈。其他控制與長度檢查,每輪或每次公開調用增加常數工作,不改變漸近結論。假設儲存操作成功。
每次入隊的項目只推入 一次,之後最多從 彈出一次、推入 一次,最後可能從 彈出一次。它永不回到 。即使數值相等,不同入隊項目仍分開計算。
若由空隊列開始,有 次入隊、 次成功出隊、 次成功查看隊首,所計堆疊工作至多為
第一個 支付輸入推入,至多 支付轉移, 支付輸出彈出與讀取。這是總量論證:部分入隊項目可能仍留在 或 ,所以上界未必取等。
用勢能函數證明同一界限
定義狀態勢能 。它非負,初始空狀態為零。操作的攤銷收費,定義為所計實際工作加上勢能改變。
| 成功操作 | 實際工作 c | 勢能改變 | 攤銷收費 |
|---|---|---|---|
| 入隊 | |||
| 輸出非空時查看或出隊 | |||
| 先轉移 k 個輸入項目再查看或出隊 |
轉移一行的 。每次到來儲存的勢能,足以支付日後從 彈出及推入 的工作。實作不會真的儲存這種餘額;勢能是數學記帳工具。
定理 2.3.7
(由空狀態開始的線性總工作量)
由空狀態開始,任何含 次入隊、 次成功出隊和 次成功查看隊首的合法操作序列,所計總工作量至多為 。
證明
(任意合法操作序列的勢能變化會消去)
把狀態編號為 ,設 是所計實際工作,。相加得到
由空狀態開始,、,所以實際總工作不超過總攤銷收費 。若分析開始時輸入堆疊已有項目,必須保留初始勢能項 ,不能直接套用空起點界限。
證明透視
為何勢能是輸入堆疊大小的兩倍
中的係數由轉移一行決定。轉移的 個項目各彈出一次、推入一次,成本約為 ,所以必須由約 的勢能下降來支付。若取 ,下降只有 ,轉移的攤銷收費便是 ,並非常數。同一係數也令每次入隊存入兩單位,得出收費 。 非負及 ,才使消去後的等式變成實際工作量的上界。證明只計抽象堆疊基本操作,所以對底層陣列的擴容沒有任何結論。
例題中共有四次輸入推入、八次轉移基本操作、三次輸出彈出及兩次頂部讀取,總計 17。界限給出 ,而最後輸入堆疊為空,沒有未用勢能留下。
單次操作仍然可以很昂貴。先把 項入隊,再調用 front,該次調用本身就有 次所計基本操作,即 工作。它的攤銷收費是一,因為釋放了先前入隊累積的 勢能。攤銷常數時間描述整串操作的總量保證,不是每次調用的固定延遲承諾,也不是對隨機輸入取平均。
常見錯誤
(把攤銷常數當成每次調用都是常數)
先入隊 次之後,單次 front 調用要執行 次所計基本操作。它的攤銷收費是 ,只因為先前的入隊已存入 單位勢能。整串 次入隊加一次 front 的成本是 ,是線性的,但那一次調用並不是常數時間。需要每次調用都有上界的應用,須使用另一種設計。
長度、空否查詢,以及空隊列上被拒絕的查看或出隊,每次只增加常數工作,勢能不變。計算公開調用總數時,可另外把它們計入。
直接使用兩個端點存取堆疊的實作
以下 Python 串列把右端當成堆疊頂部。只有公開隊列操作屬於客戶介面,直接修改內部串列會令證明失效。空隊列的 front、dequeue 會引發 IndexError,抽象隊列仍為空。None 等值是普通元素,因此例外可分清空隊列與成功回傳 None。
class TwoStackQueue:
def __init__(self):
self._incoming = []
self._outgoing = []
def __len__(self):
return len(self._incoming) + len(self._outgoing)
def is_empty(self):
return not self._incoming and not self._outgoing
def enqueue(self, value):
self._incoming.append(value)
def _prepare_front(self):
if not self._outgoing:
while self._incoming:
self._outgoing.append(self._incoming.pop())
def front(self):
self._prepare_front()
if not self._outgoing:
raise IndexError("front of an empty queue")
return self._outgoing[-1]
def dequeue(self):
self._prepare_front()
if not self._outgoing:
raise IndexError("dequeue from an empty queue")
return self._outgoing.pop()
例如,先把 4、7 入隊,調用 front(),再把 9 入隊,然後調用三次 dequeue()。查看回傳 4,之後移除依次回傳 。長度是兩個堆疊長度之和,不需要轉移元素。
精確勢能表計算的是抽象堆疊基本操作,沒有證明每次機器層級串列操作都具最壞常數成本:動態陣列堆疊可能調整容量。要取得該後端的執行時間界限,必須把線性基本操作數,與堆疊本身的攤銷容量分析合併。若 次基本調用合共需 堆疊成本,隊列總執行時間加上每次調用常數開銷後仍為線性。隊列勢能本身不是陣列容量成本的另一個證明。
共有 個仍在等待的項目,分佈在兩個堆疊。額外底層陣列容量依賴堆疊的增長及收縮政策,與邏輯元素數量不同。鏈結堆疊有不同配置行為,但 FIFO 與單向轉移論證一樣。循環陣列或鏈結隊列可避免這種批量反轉,並有自己的表示及延遲分析。
練習與詳解
快速檢查
(1. 按正確方向讀取兩個堆疊)
輸入為 ,輸出為 ,都按由底至頂排列。抽象隊列是甚麼?先出隊一次、再查看隊首,各回傳甚麼?之後兩個堆疊如何排列?
解答 · 解答 1
隊列是 。出隊回傳 7,令輸出為空。查看會轉移兩個輸入項目,得到輸入 、輸出 ,並回傳 9。查看之後,隊列仍為 。
快速檢查
(2. 找出不應進行的轉移)
輸入為 、輸出為 ,為甚麼查看隊首應讀取現有輸出頂部,而不是先轉移新項目?寫出舊抽象序列及錯誤改動後的序列。
解答 · 解答 2
舊序列是 ,隊首為 4。把 9 推到輸出,令它變成 ,代表 ,最新項目走到了最前。只有輸出為空時才轉移。
快速檢查
(3. 使用內部轉移不變量,而不是太早取答案)
由輸入 、輸出空開始,只轉移 9 後,迴圈不變量如何恢復舊隊列?為甚麼此時讀取輸出頂部,不能當成已完成的隊首結果?
解答 · 解答 3
迴圈解讀是 。輸出頂部是 9,但正確隊首為 4。只有反轉完成後,公開解讀 才重新代表舊隊列。
快速檢查
(4. 計算轉移五項的收費)
輸出為空,輸入有五項。一次成功查看隊首會轉移它們。求所計實際工作、前後勢能及攤銷收費。
解答 · 解答 4
五次輸入彈出、五次輸出推入,再讀取頂部一次,成本 11。勢能由十降至零,所以攤銷收費為 。該次調用實際仍須完成十一項基本操作。
快速檢查
(5. 分析操作後綴時保留初始狀態)
分析在 k 項已經入隊至輸入、輸出為空之後開始,只計下一次 front。為甚麼不能直接對這個單次調用後綴套用空起點界限?
解答 · 解答 5
後綴成本為 ,不是一。它開始時已有 初始勢能,所以消去公式給出實際成本等於攤銷收費一,再加這項初始勢能,即 。早前入隊累積了信用;把它們排除在所計操作序列外,不會令已儲存的工作消失。
快速檢查
(6. 分清入隊項目記帳與堆疊調整容量)
同一數值入隊十次,算一次項目旅程還是十次?抽象堆疊基本操作的界限,本身是否證明每次 Python 串列 append 都有常數最壞執行時間?
解答 · 解答 6
共有十次獨立入隊項目,各有自己的單向旅程與兩單位轉移勢能。數值相等不會把隊列項目合併。基本操作數沒有證明最壞串列操作時間;動態陣列後端還需要自身的容量分析。把其總成本界限與隊列的線性基本操作數合併,才得到相應的攤銷執行時間保證。