5 栈和队列
第五章? 棧和隊(duì)列
在常用的數(shù)據(jù)結(jié)構(gòu)中，有一批結(jié)構(gòu)被稱為容器。一個(gè)容器結(jié)構(gòu)里總包含一組其他類型的數(shù)據(jù)對(duì)象，稱為元素，容器支持對(duì)這些元素的存儲(chǔ)、管理和使用。一組容器具有相同性質(zhì)，支持同一組操作，可以被定義為一個(gè)抽象數(shù)據(jù)類型。
線性表就是一類容器，該類數(shù)據(jù)對(duì)象除了可以保存元素，支持元素訪問和刪除外，還記錄了元素之間的一種順序關(guān)系。
另外兩類最常用的容器是棧(stack)和隊(duì)列(queue)，它們都是使用最廣泛的基本數(shù)據(jù)結(jié)構(gòu)。
?
5.1 概述
棧和隊(duì)列主要用于在計(jì)算過程中保存臨時(shí)數(shù)據(jù)，這些數(shù)據(jù)是計(jì)算中發(fā)現(xiàn)或產(chǎn)生的，在后續(xù)的計(jì)算中可能需要使用它們。如果可能生成的數(shù)據(jù)項(xiàng)數(shù)在編程時(shí)就可確定，問題比較簡單，可以設(shè)置幾個(gè)變量作為臨時(shí)存儲(chǔ)。但如果需要存儲(chǔ)的數(shù)據(jù)項(xiàng)數(shù)不能事先確定，就必須采用更復(fù)雜的機(jī)制存儲(chǔ)和管理，這種機(jī)制被稱為緩沖存儲(chǔ)或緩存。棧和隊(duì)列就是使用最多的緩沖存儲(chǔ)結(jié)構(gòu)。
5.1.1 棧、隊(duì)列和數(shù)據(jù)使用順序
在計(jì)算中，中間數(shù)據(jù)對(duì)象的生成有早有晚，存在時(shí)間上的先后順序。在后續(xù)使用這些元素時(shí)，也可能需要考慮它們生成的時(shí)間順序。最典型的兩種順序是：先進(jìn)先出和后進(jìn)先出。
從實(shí)現(xiàn)的角度看，應(yīng)該考慮最簡單而且自然的技術(shù)。由于計(jì)算機(jī)存儲(chǔ)器的特點(diǎn)，要實(shí)現(xiàn)棧或隊(duì)列，最自然的技術(shù)就是用元素存儲(chǔ)的順序表示它們的時(shí)間順序。也就是說，應(yīng)該使用線性表作為棧和隊(duì)列的實(shí)現(xiàn)結(jié)構(gòu)。
5.1.2 應(yīng)用環(huán)境
可直接使用list實(shí)現(xiàn)棧的功能。python標(biāo)準(zhǔn)庫提供了一種支持隊(duì)列用途的結(jié)構(gòu)deque。
?
5.2 棧：概念和實(shí)現(xiàn)
存入棧中的元素之間沒有任何具體關(guān)系，只有到來的時(shí)間先后順序。棧的基本性質(zhì)保證了，在任何時(shí)刻可以訪問、刪除的元素都是在此之前最后存入的那個(gè)元素，因此，棧確定了一種默認(rèn)元素訪問順序。
5.2.1 棧抽象數(shù)據(jù)類型
棧的基本操作是一個(gè)封閉的集合(與線性表的情況不同)。下面是一個(gè)棧的抽象數(shù)據(jù)類型描述，其中定義的操作包括：棧的創(chuàng)建、判斷棧是否為空、入棧、出棧、訪問最后入棧元素(不刪除)。最后兩個(gè)操作都遵循LIFO原則。另外，對(duì)這兩個(gè)操作，棧為空時(shí)操作無定義。
棧的線性表實(shí)現(xiàn)
棧可以實(shí)現(xiàn)為在一端插入/刪除的線性表。在表實(shí)現(xiàn)中，執(zhí)行插入/刪除操作的一端被稱為棧頂，另一端被稱為棧底。訪問和彈出的都是棧頂元素。
用線性表實(shí)現(xiàn)棧時(shí)，操作只在表的一端進(jìn)行，不涉及另一端，更不涉及表的中間部分。由于這種情況，自然應(yīng)該選擇實(shí)現(xiàn)最方便并且保證兩個(gè)主要操作效率最高的那一端作為棧頂。
1）對(duì)于順序表，尾端插入和刪除是O(1)操作，應(yīng)該用這一端作為棧頂。
2）對(duì)于鏈接表，首端插入和刪除是O(1)操作，應(yīng)該用這一端作為棧頂。
在實(shí)際中，棧都采用這兩種技術(shù)實(shí)現(xiàn)。
5.2.2 棧的順序表實(shí)現(xiàn)
實(shí)現(xiàn)棧之前，先考慮為操作失敗的處理定義一個(gè)異常類。由于操作時(shí)棧不滿足需要(如空棧彈出)可以看作參數(shù)值錯(cuò)誤，因此自定義異常類可以繼承ValueError。
1 class StackUnderflow(ValueError): 2 pass # 不提供ValueError之外的新功能，只是與其他ValueError異常有所區(qū)分。必要時(shí)可以定義專門的異常處理操作。采用順序表技術(shù)實(shí)現(xiàn)棧，首先會(huì)遇到實(shí)現(xiàn)順序表時(shí)提出的各類問題，如：是采用簡單順序表，還是動(dòng)態(tài)順序表？如果采用簡單順序表就可能出現(xiàn)棧滿的情況，繼續(xù)壓入元素就會(huì)溢出，應(yīng)該檢查和處理。而如果采用動(dòng)態(tài)順序表，棧的存儲(chǔ)區(qū)滿時(shí)可以替換一個(gè)更大的存儲(chǔ)區(qū)，這種情況又會(huì)出現(xiàn)存儲(chǔ)區(qū)的置換策略問題，以及分期付款式的O(1)時(shí)間復(fù)雜度問題。
list及其操作實(shí)際上提供了與棧的使用方式有關(guān)的功能，可以直接作為棧來使用。
由于list類型采用的是動(dòng)態(tài)順序表技術(shù)，入棧操作具有分期付款式的O(1)時(shí)間復(fù)雜度，其他操作都是O(1)時(shí)間復(fù)雜度。
把list當(dāng)作棧使用，完全可以滿足應(yīng)用的需要。但是，這樣建立的對(duì)象還是list，提供了list類型的所有操作，特別是提供了一大批棧結(jié)構(gòu)原本不應(yīng)該支持的操作，威脅到棧的使用安全性(例如棧要求未經(jīng)彈出的元素應(yīng)該存在，但表允許任意刪除)。另外，這樣的“棧”不是一個(gè)獨(dú)立類型，因此沒有獨(dú)立類型的所有重要性質(zhì)。
可以自定義一個(gè)棧類，把list隱藏在這個(gè)類的內(nèi)部，作為其實(shí)現(xiàn)基礎(chǔ)。
基于list實(shí)現(xiàn)的棧，(沿用list的擴(kuò)容方式)
1 class SStack(): 2 def __init__(self): 3 self._elems = [] 4 5 def is_empty(self): 6 return self._elems == [] 7 8 def top(self): 9 if self.is_empty(): 10 raise StackUnderflow("in SStack.top()") 11 return self._elems[-1] 12 13 def push(self, elem): 14 self._elems.append(elem) 15 16 def pop(self): 17 # if self._elems == []: 18 if self.is_empty(): 19 raise StackUnderflow("in SStack.top()") 20 return self._elems.pop()初始創(chuàng)建對(duì)象時(shí)建立一個(gè)空棧；top和pop操作都需要先檢查棧的情況，在棧空時(shí)引發(fā)異常。
屬性_elems是只在內(nèi)部使用的屬性，這里采用下劃線開頭。
1 st1 = SStack() 2 st1.push(3) 3 st1.push(5) 4 while not st1.is_empty(): 5 print(st1.pop())5.2.3 棧的鏈表實(shí)現(xiàn)
基于順序表實(shí)現(xiàn)的棧可以滿足絕大部分的實(shí)際需要。考慮基于鏈表的棧，主要是因?yàn)轫樞虮淼膬蓚€(gè)特點(diǎn)所帶來的問題：擴(kuò)大存儲(chǔ)需要做一次高代價(jià)操作(替換存儲(chǔ)區(qū))；順序表需要完整的大塊存儲(chǔ)區(qū)。采用鏈表技術(shù)，在這兩個(gè)問題上都有優(yōu)勢，鏈表的缺點(diǎn)是更多依賴于解釋器的存儲(chǔ)管理，每個(gè)結(jié)點(diǎn)的鏈接開銷，以及鏈接結(jié)點(diǎn)在實(shí)際計(jì)算機(jī)內(nèi)存中任意散布可能帶來的操作開銷。
由于棧操作都在線性表一端進(jìn)行，采用鏈表技術(shù)，自然應(yīng)該把表頭一端作為棧頂，表尾作為棧底。
1 class LStack(): 2 def __init__(self): 3 self._top = None 4 5 def is_empty(self): 6 return self._top == None 7 8 def top(self): 9 if self.is_empty(): 10 raise LinkedListUnderflow('in pop') 11 return self._top.elem 12 13 def push(self, elem): 14 # 鏈表首端添加 15 self._top = LNode(elem, self._top) 16 17 def pop(self): 18 if self.is_empty(): 19 raise LinkedListUnderflow('in pop') 20 e = self._top.elem 21 self._top = self._top.next 22 return e?
5.3 棧的應(yīng)用
基本用途基于兩個(gè)方面：
順序反轉(zhuǎn)，只需把所有元素按原來的順序全部入棧，再順序出棧，就能得到反序后的序列。整個(gè)操作需要O(n)時(shí)間。
1 l1 = [1, 3, 5, 7, 9] 2 l2 = [] 3 ls1 = LStack() 4 for i in l1: 5 ls1.push(i) 6 7 while not ls1.is_empty(): 8 l2.append(ls1.pop()) 9 print(l2) # [9, 7, 5, 3, 1]如果入棧和出棧操作任意交錯(cuò)，可以得到不同的元素序列。
5.3.1 簡單應(yīng)用：括號(hào)匹配問題
括號(hào)配對(duì)原則：在掃描正文過程中，遇到的閉括號(hào)應(yīng)該與此前最近遇到且尚未獲得匹配的開括號(hào)配對(duì)。如果最近的未匹配開括號(hào)與當(dāng)前閉括號(hào)不配對(duì)，或者找不到這樣的開括號(hào)，就是匹配失敗，說明這段正文里的括號(hào)不配對(duì)。
由于存在多種不同的括號(hào)對(duì)，每種括號(hào)都可能出現(xiàn)任意多次，而且還可能嵌套。為了檢查是否匹配，掃描中必須保存遇到的開括號(hào)。由于編程時(shí)無法預(yù)知要處理的正文里會(huì)有多少括號(hào)需要保存，因此不能用固定數(shù)目的變量保存，必須使用緩存結(jié)構(gòu)。
由于括號(hào)的出現(xiàn)可能嵌套，需要逐對(duì)匹配：當(dāng)前閉括號(hào)應(yīng)該與前面最近的尚未配對(duì)的開括號(hào)匹配，下一個(gè)閉括號(hào)應(yīng)該與前面次近的開括號(hào)匹配。這說明，需要存儲(chǔ)的開括號(hào)的使用原則是后進(jìn)先出的。
進(jìn)而，如果一個(gè)開括號(hào)已配對(duì)，就應(yīng)該刪除這個(gè)括號(hào)，為隨后的匹配做好準(zhǔn)備。
上面這些情況說明，用棧保存遇到的開括號(hào)可以正確支持匹配工作。
思路：
1）順序掃描被檢查正文(一個(gè)字符串)里的一個(gè)個(gè)字符。
2）檢查中跳過無關(guān)字符(非括號(hào)字符都是無關(guān)字符)。
3）遇到開括號(hào)將其入棧。
4）遇到閉括號(hào)時(shí)彈出棧頂元素與之匹配，如果匹配成功則繼續(xù)，否則以失敗結(jié)束。
書中的示例是錯(cuò)的：
1 def check_parens(text): 2 parens = '()[]{}' 3 open_parens = '([{' 4 opposite = {')': '(', ']': '[', '}': '{'} 5 6 ls = LStack() 7 for i in text: 8 if i not in parens: 9 continue 10 if i in open_parens: 11 ls.push(i) 12 continue 13 14 try: 15 s = ls.pop() 16 except: # 當(dāng)出現(xiàn)一個(gè)閉括號(hào)，但是沒有與之相對(duì)的開括號(hào)時(shí) 17 print('匹配失敗') 18 return False 19 if opposite[i] != s: 20 print('匹配失敗') 21 return False 22 23 if ls.is_empty(): 24 print('匹配成功') 25 return True 26 else: 27 print('匹配失敗') 28 return False 29 30 31 def check_parens2(text): 32 parens = '()[]{}' 33 open_parens = '([{' 34 opposite = {')': '(', ']': '[', '}': '{'} 35 36 def parentheses(text): 37 i, text_len = 0, len(text) 38 while True: 39 while i < text_len and text[i] not in parens: 40 i += 1 41 if i >= text_len: 42 return 43 yield text[i], i 44 i += 1 45 46 ls = LStack() 47 for pr, i in parentheses(text): 48 if pr in open_parens: 49 ls.push(pr) 50 elif ls.pop() != opposite[pr]: 51 print('匹配失敗') 52 return False 53 print('匹配成功') 54 return True 55 56 57 text = '((((' 58 check_parens(text) 59 check_parens2(text)5.3.2 表達(dá)式的表示、計(jì)算和交換
中綴表示很難統(tǒng)一地貫徹。首先是一元和多元運(yùn)算符都難以中綴形式表示。其次是不足以表示所有可能的運(yùn)算順序，需要通過輔助符號(hào)、約定和 /或輔助描述機(jī)制。
后綴表達(dá)式特別適合計(jì)算機(jī)處理。
前綴表達(dá)式和后綴表達(dá)式都不需要引進(jìn)括號(hào)，也不需要任何有關(guān)優(yōu)先級(jí)或結(jié)合性的規(guī)定。對(duì)于前綴表示，每個(gè)運(yùn)算符的運(yùn)算對(duì)象，就是它后面出現(xiàn)的幾個(gè)完整表達(dá)式，表達(dá)式個(gè)數(shù)由運(yùn)算符元數(shù)確定。對(duì)于后綴表示，情況類似但位置相反。
中綴表達(dá)式的表達(dá)能力最弱，而給中綴表達(dá)式增加了括號(hào)后，幾種表達(dá)式具有同等表達(dá)能力。
。。。
?
5.3.3 棧與遞歸
如果在一個(gè)定義中引用了被定義的對(duì)象本身，這種定義被稱為遞歸定義。類似地，如果在一種數(shù)據(jù)結(jié)構(gòu)中的某個(gè)或某幾個(gè)部分具有與整體同樣的結(jié)構(gòu)，這也是一種遞歸結(jié)構(gòu)。
在遞歸定義或結(jié)構(gòu)中，遞歸部分必須比原來的整體簡單，這樣才有可能達(dá)到某種終結(jié)點(diǎn)(即遞歸定義的出口)，這種終結(jié)點(diǎn)必須是非遞歸的。例如，單鏈表中，結(jié)點(diǎn)鏈的空鏈接就是遞歸的終點(diǎn)。
階乘函數(shù)的遞歸運(yùn)算
以fact(6)為例，
這種后進(jìn)先出的使用方式和數(shù)據(jù)項(xiàng)數(shù)的無明確限制，就說明需要用一個(gè)棧來支持遞歸函數(shù)的實(shí)際運(yùn)行，這個(gè)棧被稱為程序運(yùn)行棧(算法圖解上叫調(diào)用棧)。
棧與遞歸/函數(shù)調(diào)用
對(duì)遞歸定義的函數(shù)，實(shí)現(xiàn)方式就是用一個(gè)運(yùn)行棧，對(duì)函數(shù)的每個(gè)調(diào)用都在這個(gè)棧上為之開辟一塊區(qū)域，其中保存這個(gè)調(diào)用的相關(guān)信息，這個(gè)區(qū)域稱為一個(gè)函數(shù)幀。
一般的函數(shù)調(diào)用和退出的方式也與此類似。例如函數(shù)f里調(diào)用函數(shù)g，函數(shù)g里調(diào)用函數(shù)h，函數(shù)h里調(diào)用函數(shù)r，其執(zhí)行流程與遞歸完全一樣。
遞歸和非遞歸
對(duì)遞歸定義的函數(shù)，每個(gè)實(shí)際調(diào)用時(shí)執(zhí)行的都是該函數(shù)體的那段代碼，只是需要在一個(gè)內(nèi)部運(yùn)行棧里保存各次調(diào)用的局部信息。這種情況說明，完全有可能修改函數(shù)定義，把一個(gè)遞歸定義的函數(shù)改造為一個(gè)非遞歸的函數(shù)。在函數(shù)里自己完成上面這些工作，用一個(gè)棧保存計(jì)算中的臨時(shí)信息，完成同樣的計(jì)算工作。
1 def norec_fact(n): 2 res = 1 3 ls = LStack() 4 while n > 0: 5 ls.push(n) 6 n -= 1 7 while not ls.is_empty(): 8 res *= ls.pop() 9 return res實(shí)際上，任何一個(gè)遞歸定義的函數(shù)，都可以通過引入一個(gè)棧保存中間結(jié)果的方式，翻譯為一個(gè)非遞歸的過程。
棧的應(yīng)用：簡單背包問題
。。。
?
5.4 隊(duì)列
5.4.1 隊(duì)列抽象數(shù)據(jù)類型
隊(duì)列的基本操作也是一個(gè)封閉集合，通常包括創(chuàng)建新隊(duì)列對(duì)象、判斷隊(duì)列是否為空、入隊(duì)、出隊(duì)、檢查隊(duì)列當(dāng)前元素。
隊(duì)列操作與棧操作一一對(duì)應(yīng)，但通常采用另一套習(xí)慣的操作名：
5.4.2 隊(duì)列的鏈接表實(shí)現(xiàn)
采用線性表技術(shù)實(shí)現(xiàn)隊(duì)列，就是利用元素位置的順序表示入隊(duì)時(shí)間的先后關(guān)系。隊(duì)列操作要求先進(jìn)先出，這就要求在表的兩端進(jìn)行操作，所以實(shí)現(xiàn)起來也稍微麻煩一些。
由于需要在鏈接表的兩端操作，在一端插入元素，在另一端刪除。最簡單的單鏈表只支持首端高效操作，在另一端操作需要O(n)時(shí)間，不適合作為隊(duì)列的實(shí)現(xiàn)基礎(chǔ)。
帶表尾指針的單鏈表，支持O(1)時(shí)間的尾端插入操作，再加上表首端的高效訪問和刪除，可作為隊(duì)列的實(shí)現(xiàn)基礎(chǔ)。
5.4.3 隊(duì)列的順序表實(shí)現(xiàn)
基于順序表實(shí)現(xiàn)隊(duì)列的困難
另一種可能是隊(duì)首元素出隊(duì)后表中元素不前移，但記住新隊(duì)首位置。從操作效率上看，每個(gè)操作都是O(1)時(shí)間，但表中隊(duì)列卻好像隨著操作向表尾方向”移動(dòng)“，表前端留下越來越多的空位。
這樣經(jīng)過反復(fù)的入隊(duì)和出隊(duì)操作，一定會(huì)在某次入隊(duì)時(shí)出現(xiàn)隊(duì)尾溢出的情況，而此時(shí)隊(duì)首卻有大量空位，所以這是一種假性溢出，并不是真的用完了整個(gè)元素區(qū)。假如元素存儲(chǔ)區(qū)能自動(dòng)增長，隨著操作進(jìn)行，表首端就會(huì)留下越來越大的空區(qū)，而且這片空區(qū)永遠(yuǎn)也不會(huì)用到。顯然不應(yīng)該允許程序中出現(xiàn)這種情況。
從圖5.7可以看到：在反復(fù)入隊(duì)和出隊(duì)操作中，隊(duì)尾最終會(huì)到達(dá)存儲(chǔ)區(qū)末端。但與此同時(shí)，存儲(chǔ)區(qū)首端可能有些空位可以利用。這樣就得到了一種順理成章的設(shè)計(jì)：如果入隊(duì)時(shí)隊(duì)尾已滿，應(yīng)該考慮轉(zhuǎn)到存儲(chǔ)區(qū)開始的位置去入隊(duì)新元素。
循環(huán)順序表
1）在隊(duì)列使用中，順序表的開始位置并未改變。變量q.elems始終指向表元素區(qū)開始。
2）隊(duì)頭變量q.head記錄當(dāng)前隊(duì)列里第一個(gè)元素的位置；隊(duì)尾變量q.rear記錄當(dāng)前隊(duì)列里最后元素之后的第一個(gè)空位。
3）隊(duì)列元素保存在順序表的一段連續(xù)單元里，python的寫法是[q.head, q.rear]，左閉右開區(qū)間。
上面這幾條也是這種隊(duì)列的操作必須維護(hù)的性質(zhì)。初始時(shí)隊(duì)列為空，應(yīng)該讓q.hear和q.rear取相同的值，表示順序表里一個(gè)空段。具體取值無關(guān)緊要。不變操作都不改變有關(guān)變量的值，不會(huì)破壞上述性質(zhì)；變動(dòng)操作可能修改有關(guān)變量的值，因此要特別注意維護(hù)上面的性質(zhì)。
出隊(duì)和入隊(duì)操作分別需要更新變量q.head和q.rear。
1 q.head = (q.head+1) % q.len # 出隊(duì) # 通過求余控制循環(huán) 2 q.rear = (q.rear+1) % q.len # 入隊(duì)判斷隊(duì)列狀態(tài)。q.head == q.rear表示隊(duì)空。
從圖5.8的隊(duì)列狀態(tài)出發(fā)做幾次入隊(duì)操作，可以到達(dá)圖5.9所示的狀態(tài)，這時(shí)隊(duì)列里已有7個(gè)元素。如果再加入一個(gè)元素順序表就滿了，但又會(huì)出現(xiàn)q.head == q.rear的情況，這個(gè)狀態(tài)與隊(duì)列空的判斷無法區(qū)分。
一種解決辦法是直接把圖5.9“看作”隊(duì)列已滿，即把隊(duì)滿條件定義為
1 (q.rear+1) % q.len == q.head # 隊(duì)尾攆上隊(duì)首了采用這種方法，將在表里留下一個(gè)不用的空位。基于循環(huán)順序表，存在多種隊(duì)列實(shí)現(xiàn)方式。
5.4.4 隊(duì)列的 list 實(shí)現(xiàn)
最直截了當(dāng)?shù)膶?shí)現(xiàn)方法將得到一個(gè)O(1)時(shí)間的enqueue操作和O(n)時(shí)間的dequeue操作。
現(xiàn)在考慮定義一個(gè)可以自動(dòng)擴(kuò)充存儲(chǔ)的隊(duì)列類。這里很難直接利用list的自動(dòng)存儲(chǔ)擴(kuò)充機(jī)制，兩個(gè)原因：首先是隊(duì)列元素的存儲(chǔ)方式與list元素的默認(rèn)存儲(chǔ)方式不一致。list元素總在其存儲(chǔ)區(qū)的最前面一段，而隊(duì)列元素可能是其中的任意一段，有時(shí)還分為頭尾兩端(圖5.9就是這樣，但隊(duì)列本身仍然是連續(xù)的)。如果list自動(dòng)擴(kuò)充，其中的隊(duì)列元素就有可能失控。另一方面，list沒提供檢查元素存儲(chǔ)區(qū)容量的機(jī)制，隊(duì)列操作中無法判斷系統(tǒng)何時(shí)擴(kuò)容。由于沒有很好的辦法處理這些困難，下面考慮自己管理存儲(chǔ)。
基本設(shè)計(jì)
首先，隊(duì)列可能為空而無法dequeue，為此自定義一個(gè)異常：
1 class QueueUnderflow(ValueError): 2 pass基本設(shè)計(jì)：
1）在SQueue對(duì)象里用一個(gè)list類型的成分_elems存放隊(duì)列元素。
2）_head記錄隊(duì)列首元素所在位置的下標(biāo)。
3）_num記錄表中元素個(gè)數(shù)。
4）_len記錄當(dāng)前表的長度，必要時(shí)替換存儲(chǔ)區(qū)。
數(shù)據(jù)不變式
變動(dòng)操作可能會(huì)改變一些對(duì)象屬性的取值，如果操作的實(shí)現(xiàn)有錯(cuò)誤，可能會(huì)破壞對(duì)象的狀態(tài)。實(shí)現(xiàn)一種數(shù)據(jù)結(jié)構(gòu)里的操作時(shí)，最基本的問題就是這些操作需要維護(hù)對(duì)象屬性之間的正確關(guān)系，這樣一套關(guān)系被稱為這種數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)不變式。(1)對(duì)象的初始狀態(tài)應(yīng)該滿足數(shù)據(jù)不變式。(2)每個(gè)對(duì)象操作都應(yīng)該保證不破壞數(shù)據(jù)不變式。有了這兩條，這類對(duì)象在使用中就能始終處于良好狀態(tài)。
下面是隊(duì)列實(shí)現(xiàn)中考慮的數(shù)據(jù)不變式：
1）_elems屬性引用著隊(duì)列的元素存儲(chǔ)區(qū)，它是一個(gè)list對(duì)象，_len屬性記錄存儲(chǔ)區(qū)的有效容量(python無法獲知list對(duì)象的實(shí)際大小)。
2）_head是隊(duì)首元素的下標(biāo)，_num始終記錄著隊(duì)列中元素的個(gè)數(shù)。
3）隊(duì)列里的元素總保存在_elems里從_head開始的連續(xù)位置中，新入隊(duì)元素存入_head+_num算出的位置，但如果需要把元素存入下標(biāo)_len的位置時(shí)，改為在下標(biāo)0位置存入該元素(前提是隊(duì)列未滿，0位置處有空位，否則擴(kuò)容)。
4）在_num == _len時(shí)(隊(duì)滿時(shí))出現(xiàn)入隊(duì)操作，就擴(kuò)大存儲(chǔ)區(qū)。
總之，需要時(shí)刻注意_elems、_len、_head、_num四個(gè)變量的狀態(tài)。
隊(duì)列類的實(shí)現(xiàn)
根據(jù)前面的設(shè)計(jì)，隊(duì)列的首元素在self._elems[self._head]，peek和dequeue操作應(yīng)該取這里的元素；下一個(gè)空位在self._elems[(self._head+self._num) % self._len]，入隊(duì)的新元素應(yīng)該存入這里。
另外，隊(duì)列空就是self._num == 0，當(dāng)前隊(duì)列滿就是self._num = self._len，這時(shí)應(yīng)該替換存儲(chǔ)區(qū)。
完整實(shí)例：
1 #!coding:utf8 2 3 class QueueUnderflow(ValueError): 4 pass 5 6 class SQueue(): 7 def __init__(self, init_len=8): 8 self._len = init_len 9 self._elems = [0]*init_len # 感覺用None比較好 10 self._head = 0 11 self._num = 0 12 13 def is_empty(self): 14 return self._num == 0 15 16 def peek(self): 17 if self.is_empty(): 18 raise QueueUnderflow('none') 19 return self._elems[self._head] 20 21 # 時(shí)刻注意四個(gè)變量的狀態(tài) 22 # 不能直接使用pop，pop隊(duì)首的時(shí)間為O(n) 23 def dequeue(self): 24 if self.is_empty(): 25 raise QueueUnderflow('none') 26 e = self._elems[self._head] 27 self._head = (self._head + 1) % self._len 28 self._num -= 1 29 return e 30 31 # 不能直接使用append 32 # 可能出現(xiàn)擴(kuò)容操作 33 def enqueue(self, e): 34 if self._num == self._len: 35 self.__extend() # 擴(kuò)容 36 37 self._elems[(self._head + self._num) % self._len] = e 38 self._num += 1 39 40 # 擴(kuò)容(2倍) 41 def __extend(self): 42 old_len = self._len 43 self._len *= 2 44 new_elems = [0]*self._len # 這個(gè)一直沒有理解？？ 45 for i in range(old_len): 46 new_elems[i] = self._elems[(self._head + i) % self._len] 47 self._elems, self._head = new_elems, 0特別提醒：peek和dequeue操作都需要事先判斷隊(duì)列是否為空。
基于循環(huán)順序表實(shí)現(xiàn)的隊(duì)列，加入和取出操作都是O(1)操作。循環(huán)順序表實(shí)際上是為了解決假性溢出問題。
小結(jié)：基于鏈表的隊(duì)列，鏈表是指帶尾端指針的鏈表；基于順序表的隊(duì)列，順序表是指循環(huán)順序表。
?
5.5 迷宮求解和狀態(tài)空間搜索
5.5.1 迷宮求解：分析和設(shè)計(jì)
迷宮問題
搜索從入口到出口的路徑，具有遞歸性質(zhì)：
1）從迷宮的入口開始檢查，這是初始的當(dāng)前位置。
2）如果當(dāng)前位置就是出口，已經(jīng)找到出口，問題解決。
3）如果從當(dāng)前位置已無路可走，當(dāng)前正在進(jìn)行的探查失敗，需要按一定方式另行繼續(xù)搜索。
4）從可行方向中取一個(gè)，向前進(jìn)一步，從那里繼續(xù)探索通往出口的路徑。
先考慮一種簡單形式的迷宮。如圖5.10左圖，
其形式是一組位置構(gòu)成的矩形陣列，空白格子表示可通行，陰影格子表示不可通行。這種迷宮是平面的，形式比較規(guī)范，每個(gè)空白位置的上/下/左/右四個(gè)方向有可能也是空白位置，每次允許在某個(gè)方向上移動(dòng)一步。這種迷宮可以直接映射到二維的0/1矩陣，因此很容易在計(jì)算機(jī)里表示。
迷宮問題分析
問題的目標(biāo)是找到從入口到出口的一條路徑，而不是所有的可行路徑。
由于不存在其他指導(dǎo)信息，這里的工作方式只能是試探并設(shè)法排除無效的探索方向。這顯然需要緩存一些信息：如果當(dāng)前位置有多個(gè)可能的繼續(xù)探查方向，由于下一步只能探查一種可能，因此必須記錄不能立即考慮的其他可能方向。不記錄而丟掉了重要信息，就可能出現(xiàn)實(shí)際有解但不能找到的情況。
存在不同的搜索方式，可以比較冒進(jìn)，也可以穩(wěn)扎穩(wěn)打。如果搜索到當(dāng)前位置還沒找到出口，可以繼續(xù)向前走，直到無路可走才考慮后退，換一條沒走過的路繼續(xù)。也可以在每一步都從最早記錄的有選擇位置向前進(jìn)，找到下一個(gè)可達(dá)位置并記錄它。
顯然這里需要保存已經(jīng)發(fā)現(xiàn)但尚未探索的分支方向信息。由于無法確定需要保存的數(shù)據(jù)項(xiàng)數(shù)，只能用某種緩存結(jié)構(gòu)，首先應(yīng)該考慮使用棧或隊(duì)列。搜索過程只要求找到目標(biāo)，對(duì)如何找到?jīng)]有任何約束，因此這兩種結(jié)構(gòu)都有可能使用。采用不同的緩存結(jié)構(gòu)，會(huì)對(duì)所實(shí)現(xiàn)的搜索過程有重要影響：
1）按棧的方式保存和使用信息，實(shí)現(xiàn)的探索過程是每步選擇一種可能方向一直向前，直到無法前進(jìn)才退回到此前最后選擇點(diǎn)，換路徑繼續(xù)該過程。
2）按隊(duì)列方式保存和使用信息，就是總從最早遇到的搜索點(diǎn)不斷拓展。這種方式倒不好理解。。。
問題表示和輔助結(jié)構(gòu)
要解決上述迷宮問題，首先要設(shè)計(jì)一種問題表示形式。用計(jì)算機(jī)解決問題，第一步就是選擇合適的數(shù)據(jù)表示。python里可以用二維數(shù)組表示。迷宮入口和出口可以各用一對(duì)下標(biāo)表示。
有一個(gè)情況需要注意：搜索過程有可能在某些局部路徑中兜圈子，這樣即使存在到出口的路徑，程序也可能無休止地運(yùn)行卻永遠(yuǎn)也找不到解。為防止出現(xiàn)這種情況，程序運(yùn)行中必須采用某種方法記錄已經(jīng)探查過的位置，方法是把對(duì)應(yīng)矩陣元素標(biāo)記為2。計(jì)算中發(fā)現(xiàn)元素值為2就不再去探索。(0表示可通行，1表示不可通行，2表示已探查)
還需要找到一種確定當(dāng)前位置可行方向的技術(shù)。在到達(dá)某個(gè)位置后，搜索過程需要選一個(gè)方向前進(jìn)。如果再次退回到這里就需要改走另一方向，直到所有方向都已探查為止，如果還沒找到出口就應(yīng)該退一步。
這里需要記錄方向信息。顯然，每個(gè)格子有四個(gè)相鄰位置，為正確方便地處理這幾個(gè)可能方向，需要確定一種系統(tǒng)檢查方法。對(duì)于單元(i, j)，其四個(gè)相鄰位置的數(shù)組元素下標(biāo)如圖所示：(i 表示上下，j 表示左右)
為了方便地計(jì)算相鄰位置，需要定義一個(gè)二元組列表，其元素是從位置(i, j)得到其四鄰位置應(yīng)該加的數(shù)對(duì)：dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
為了使算法的描述更加方便，先定義兩個(gè)簡單的輔助函數(shù)。其中參數(shù)pos都是形式為(i, j)的二元序?qū)Α?/p> 1 def mark(maze, pos): # 給迷宮maze的pos位置標(biāo)2，表示“到過了” 2 maze[pos[0]][pos[1]] = 2 3 4 def passable(maze, pos): # 檢查迷宮maze的位置pos是否可行 5 return maze[pos[0]][pos[1]] == 0
5.5.2 求解迷宮的算法
迷宮的遞歸求解
示例，
1 def mark(maze, pos): # 給迷宮maze的pos位置標(biāo)2，表示“到過了” 2 maze[pos[0]][pos[1]] = 2 3 4 def passable(maze, pos): # 檢查迷宮maze的位置pos是否可行 5 return maze[pos[0]][pos[1]] == 0 6 7 def find_path(maze, pos, end): 8 mark(maze, pos) 9 if pos == end: 10 print(pos, end=' ') 11 return True 12 13 for i in range(4): 14 nextP = (pos[0]+dirs[i][0], pos[1]+dirs[i][1]) 15 if passable(maze, nextP): 16 if find_path(maze, nextP, end): 17 print(pos, end=' ') 18 return True 19 return False 20 21 maze = [ 22 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 23 [1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1], 24 [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1], 25 [1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1], 26 [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1], 27 [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1], 28 [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1], 29 [1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1], 30 [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1], 31 [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1], 32 [1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1], 33 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 34 ] 35 pos = (1, 1) 36 end = (10, 12) 37 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] 38 print(find_path(maze, pos, end))棧和回溯法
迷宮的回溯法求解
1 def mark(maze, pos): # 給迷宮maze的pos位置標(biāo)2，表示“到過了” 2 maze[pos[0]][pos[1]] = 2 3 4 def passable(maze, pos): # 檢查迷宮maze的位置pos是否可行 5 return maze[pos[0]][pos[1]] == 0 6# 自己翻譯的， 7 def find_path(maze, start, end): 8 if start == end: 9 print(start) 10 return 11 ls = LStack() 12 ls.push(start) 13 while not ls.is_empty(): 14 pos = ls.pop() 15 for dir in dirs: 16 nextp = pos[0]+dir[0], pos[1]+dir[1] 17 if nextp == end: 18 print(nextp) 19 while not ls.is_empty(): 20 print(ls.pop()) 21 return 22 if passable(maze, nextp): 23 ls.push(pos) 24 ls.push(nextp) 25 break 26 mark(maze, pos) 27
# 書上的，在棧中保存的是(位置序?qū)? 探索方向)序?qū)Α?28 def find_path2(maze, start, end): 29 if start == end: 30 print(start) 31 return 32 ls = LStack() 33 mark(maze, start) 34 ls.push((start, 0)) 35 while not ls.is_empty(): 36 pos, nxt = ls.pop() 37 for i in range(nxt, 4): 38 nextp = pos[0]+dirs[i][0], pos[1]+dirs[i][1] 39 if nextp == end: 40 print(nextp) 41 while not ls.is_empty(): 42 print(ls.pop()) 43 return 44 if passable(maze, nextp): 45 ls.push((pos, i+1)) 46 mark(maze, nextp) 47 ls.push((nextp, 0)) 48 break 49 print('not found') 50 51 maze = [ 52 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 53 [1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1], 54 [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1], 55 [1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1], 56 [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1], 57 [1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1], 58 [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1], 59 [1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1], 60 [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1], 61 [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1], 62 [1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1], 63 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 64 ] 65 pos = (1, 1) 66 end = (10, 12) 67 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] 68 find_path(maze, pos, end)
兩種方法的區(qū)別在于標(biāo)記的時(shí)機(jī)不同：方法1是標(biāo)記當(dāng)前位置，方法2是標(biāo)記可達(dá)位置。兩種方法的關(guān)鍵點(diǎn)相同：一是棧中所存元素相同，一次操作入棧的都是當(dāng)前位置和可達(dá)位置。二是到達(dá)出口后打印路徑的方式相同(書中沒給)。
5.5.3 迷宮問題和搜索
狀態(tài)空間搜索：棧和隊(duì)列
基于棧和隊(duì)列的搜索過程
?*深度和寬度優(yōu)先搜索的性質(zhì)
5.6.1 幾種與棧或隊(duì)列相關(guān)的結(jié)構(gòu)
雙端隊(duì)列
python的deque類
5.6.2 幾個(gè)問題的討論
?
轉(zhuǎn)載于:https://www.cnblogs.com/yangxiaoling/p/9924474.html
總結(jié)
- 上一篇： STS安装lombok
- 下一篇： python-23 xml.etree