教學過程教學環節教學內容與過程（教學內容、教學方法、組織形式、教學手段）課前組織做好上課前的各項準備工作（打開計算機、打開課件、打開軟件、打開授課計劃、教案等），吸引學生注意力。課程說明【課前說明】從二叉樹的基本概念引入本章學習內容。【目的】使學生從了解本節課的學習目標、學習重點、考評方式等方面明確課程學習的要求和目標。課程內容描述10.1Python中二叉樹的遞歸遍歷10.1.1二叉樹的基本概念計算機中，數據元素在不同的場合還可以被稱作“結點”“頂點”“記錄”等。在二叉樹這種數據結構中，把數據元素統稱為“結點”。“二叉樹”是一個由結點組成的有限集合。這個集合或者為空，或者由一個稱為“根”的結點及兩棵不相交的二叉樹組成，這兩棵二叉樹分別稱為這個根結點的“左子樹”和“右子樹”。當二由二叉樹的定義可以知道，它其實是一個遞歸式的定義，因為在定義一棵二叉樹時，又用到了二叉樹這個術語：一個結點的左、右子樹也是二叉樹。如果子樹是空的，那么這時就說該結點沒有“左孩子”或者沒有“右孩子”。綜上所述，二叉樹有如下的特征：●二叉樹可以是空的，空二叉樹沒有任何結點。●二叉樹上的每個結點最多可以有兩棵子樹，這兩棵子樹是不相交的。●二叉樹上一個結點的兩棵子樹有左、右之分，次序是不能顛倒的。例10-1下圖所示的是二叉樹的幾種圖形表示。上圖（a）所示為一棵空二叉樹，我們用符號“Ф”來表示；上圖（b）所示為一棵只有一個結點的二叉樹，這個結點就是這棵二叉樹的根結點，由于該二叉樹只有一個根結點，所以也可以說這是一棵左、右子樹都為空的二叉樹；上圖（c）所示為由一個根結點、左子樹的根結點B、右子樹的根結點C組成的一棵二叉樹；上圖（d）所示為一棵只含左子樹的二叉樹（當然，也可以有只含右子樹的二叉樹，這里沒有給出）；上圖（e）所示為一棵普通的二叉樹，其左子樹只有根結點B，右子樹則由若干個結點組成，整棵二叉樹可以劃分為4層，分別是第0層～第3層。二叉樹是一種非線性結構，人們無法使用熟悉的順序（也就是線性）方法知道一個結點的“下一個”是誰，只有人為地做出限定，才能去訪問某結點中的數據。所謂“遍歷”二叉樹，是指按照規定的路線對二叉樹進行搜索，以保證里面的每個結點被訪問一次，而且只被訪問一次。由于一棵非空二叉樹是由根結點及兩棵不相交的左、右子樹3個部分組成的，因此如果人為規定一種順序，在到達每一個結點時，都按照這個規定去訪問與該結點有關的3個部分，那么就可以訪問二叉樹上的所有結點，且每個結點只被訪問一次。若用T、L和R分別表示二叉樹的根結點、左子樹和右子樹，那么在到達每一個結點時，訪問結點的順序可以有以下6種不同的組合形式：●TLR——先訪問根結點，再訪問左子樹，最后訪問右子樹。●LTR——先訪問左子樹，再訪問根結點，最后訪問右子樹。●LRT——先訪問左子樹，再訪問右子樹，最后訪問根結點。●TRL——先訪問根結點，再訪問右子樹，最后訪問左子樹。●RTL——先訪問右子樹，再訪問根結點，最后訪問左子樹。●RLT——先訪問右子樹，再訪問左子樹，最后訪問根結點。前3個規定的特點是到達一個結點后，對左、右子樹來說，總是“先訪左、后訪右”；后3個規定的特點是到達一個結點后，對左、右子樹來說，總是“先訪右、后訪左”。如果對左、右子樹，我們約定總是“先訪左、后訪右”，那么訪問結點的6種順序就只剩下3種不同的組合形式：TLR、LTR、LRT。通常，稱TLR為二叉樹的先根遍歷或先序遍歷（因為T在最前面），稱LTR為中根遍歷或中序遍歷（因為T在中間），稱LRT為后根遍歷或后序遍歷（因為T在最后面）。例10-2以先根遍歷（TLR）的順序訪問下圖所示的二叉樹，并給出遍歷后的結點訪問序列。先根遍歷的總體規定是每到達二叉樹的一個結點后，就先訪問根結點，然后訪問它的左子樹上的所有結點，最后訪問右子樹上的所有結點。現在從圖10-2所示的二叉樹根結點A開始出發遍歷。在訪問了根結點A之后，由于它有左子樹，因此根據規定應該前進到它的左子樹去。到達左子樹后，根據規定先訪問該二叉樹的根結點B，再去訪問B的左子樹。由于B有左子樹，因此前進到它的左子樹。到達左子樹后，仍先訪問它的根結點D，再去訪問D的左子樹。這時左子樹為空，因此根據規定去訪問它的右子樹。但D的右子樹也為空，至此，結點B的左子樹上的所有結點都已訪問完畢，根據規定就應該去訪問它的右子樹上的結點了。結點B的右子樹是以結點E為根的二叉樹。到達結點E后，按照先根遍歷的規定，先訪問根結點E，然后訪問它的左子樹。在訪問了左子樹的根結點H后，由于H的左、右子樹都為空，因此結點E的左子樹上的所有結點都訪問完畢，轉去訪問它的右子樹。由于結點E的右子樹為空，于是結點B的右子樹上的所有結點都已訪問完畢。至此，結點A左子樹上的所有結點都已訪問完畢，按先根遍歷的規定，應該轉去訪問它的右子樹上的所有結點了。結點A的右子樹的根結點是C。先訪問結點C，然后去訪問它的左子樹。這時左子樹的根結點為F，于是訪問F，然后去訪問F的左子樹。由于左子樹為空，因此去訪問它的右子樹。結點F的右子樹的根結點是I，于是訪問結點I。由于I的左、右子樹均為空，至此，結點C的左子樹上結點全部訪問完畢，轉去訪問它的右子樹。結點C的右子樹的根結點是G，于是訪問結點G。由于結點G的左、右子樹都為空，至此，結點A的右子樹上的所有結點都訪問完畢，對該二叉樹的先根遍歷也就到此結束。歸納對該二叉樹結點的“訪問”次序，可以得到對圖10-2所示的二叉樹的先根遍歷序列：A→B→D→E→H→C→F→I→G通過此例可以知道，求一個二叉樹的某種遍歷序列，最重要的是在到達每一個結點時都必須堅持該遍歷的原則，只有這樣才能得出正確的結點遍歷序列，確保每個結點都只被訪問一次。例10-3以中根遍歷（LTR）的順序訪問圖10-2所示的二叉樹，并給出遍歷后的結點序列。中根遍歷規定，在到達二叉樹的一個結點后，不是先訪問該結點，而是先去訪問該結點的左子樹，只有在訪問完左子樹后，才去訪問該結點，最后訪問該結點的右子樹。現在從圖10-2所示的二叉樹的根結點A開始遍歷。到達A后，先不能訪問它，而是要去訪問它的左子樹，于是進到左子樹的根結點B。到達B后，根據中根遍歷規定，不能訪問B，而是要先訪問它的左子樹，于是又進到結點D。到達D后，仍然不能訪問D，而是要先訪問它的左子樹。但D的左子樹為空，因此訪問D的左子樹的任務完成。由于訪問完D的左子樹，根據中根遍歷規定，這時才能訪問結點D。可見，中根遍歷二叉樹時，最先訪問的結點是該二叉樹最左邊的那個結點。訪問完結點D之后，應該訪問D的右子樹。由于D的右子樹為空，于是，以D為根的二叉樹的遍歷結束，也就是以結點B為根的二叉樹的左子樹的遍歷結束，因此根據中根遍歷規定，這時才訪問結點B，然后去訪問以B為根結點的右子樹。到達右子樹的根結點E后，根據中根遍歷規定，不能訪問E，而是要先訪問它的左子樹，于是進到結點H。H的左子樹為空，因此這時才訪問結點H。由于H的右子樹為空，至此，對以結點B為根的右子樹遍歷完畢，即以結點A為根的左子樹遍歷完畢。到這個時候，才可以訪問結點A。可見，中根遍歷二叉樹時，左子樹上的結點都先于二叉樹的根結點得到訪問，因此在遍歷序列里它們都位于根結點的左邊，而右子樹上的結點都位于根結點的右邊。訪問完二叉樹的根結點A之后，根據中根遍歷規定，將對二叉樹的右子樹進行遍歷。到達右子樹根結點C后，不能訪問它，應該先去訪問它的左子樹，于是進到結點F。進到結點F后，不能訪問它，應該先去訪問它的左子樹。由于它的左子樹為空，因此才訪問結點F。訪問完結點F，應該訪問它的右子樹，于是進到結點I。I的左子樹為空，所以訪問結點I，然后訪問它的右子樹。因為I的右子樹為空，故以結點C為根的二叉樹的左子樹已遍歷完畢，所以訪問結點C，然后進到右子樹的結點G。結點G的左子樹為空，因此訪問結點G，然后訪問G的右子樹。因為G的右子樹為空，至此，以結點A為根的右子樹全部遍歷完畢，也就是對整個二叉樹遍歷完畢。可見，中根遍歷二叉樹時，最后訪問的結點應該是二叉樹上最右邊的那個結點。綜上所述，對圖10-2所示的二叉樹進行中根遍歷時，遍歷的結點序列是：D→B→H→E→A→F→I→C→G不難總結出其規律：對于任何一棵二叉樹，先根遍歷時整棵樹的根結點總是處于遍歷序列之首；中根遍歷時整棵樹的根結點的位置總是“居中”，它的左子樹的所有結點都在其左邊，右子樹的所有結點都在其右邊；后根遍歷時整棵樹的根結點的位置總是在最后，其所有結點都在它的左邊。這個總結，對整棵二叉樹成立，對各子二叉樹也成立。10.1.2遞歸的概念前面提及：“由二叉樹的定義可以知道，它其實是一個遞歸式的定義，因為在定義一棵二叉樹時，又用到了二叉樹這個術語。”什么是“遞歸”呢？在程序設計中，遞歸其實應該屬于函數調用的范疇。我們知道，一個函數是可以調用另一個函數的。在特定的條件下，一個函數也可以調用它自己。這就是所謂函數的“遞歸”調用。看一個簡單的例子。計算整數n的階乘：n！=1×2×…×(n-1)×n，嚴格的數學定義如下。也就是說：當n=0時，其階乘就是1；當n>0時，其階乘等于n-1的階乘的n倍。不難看出，在這個階乘例如，可以用如下的Python函數fact()來實現整數n的遞歸調用：deffact(n): ifn==0: return1 else: returnn*fact(n-1)為了驗證它的正確性，編寫程序如下：deffact(n): ifn==0: return1 else: returnn*fact(n-1)#主程序print(fact(3))執行后，輸出結果為6，完全正確。程序里沒有循環，很少的幾條語句顯得簡潔、清晰。但它的執行路線卻不簡單，下圖描述了fact(3)的計算調用過程：求fact(3)時，需要調用fact(2)，而求fact(2)時又要調用fact(1)，直至到達求fact(0)。根據函數定義，它直接返回結果1。這樣一來，前面的一系列調用都能夠得到應有的結果，從而按順序一級一級返回，最終得到fact(3)的計算結果6。例10-4數學中有一個所謂的Fibonacci（斐波那契）數列：1，1，2，3，5，8，13，21，34，55，89，…它是通過如下的遞歸方式來定義的：F0=1，F1=1，F2=F0+F1，…，Fn=Fn-1+Fn-2(n>1)即除第1、2項外，從第3項開始，數列中的各項的值是它前兩項之和。該數列項值的增長速度是很快的。很明顯，求Fibonacci數列各項的值是一個遞歸過程。編寫程序，以遞歸方式處理Fibonacci數列：deffibon(x): ifx<=1: returnx else: returnfibon(x-1)+fibon(x-2) #主程序outn=[] #定義一個空列表foriteminrange(12): outn.append(fibon(itrm)) print('Fibonacci數列:',outn)運行該程序，結果如圖所示。程序中，考慮到Fibonacci數列從0或1開始，因此通過if語句返回0或1來終止整個遞歸過程。整個遞歸過程是由else語句來處理的，當Fibonacci數列大于或等于2時，就將前面的兩項數值相加，得出新的項，并由return語句將該項取值返回。究竟要遞歸多少次，每次輸出Fibonacci數列列表中的什么內容，將由for循環中的函數range()及調用函數fibon()時傳遞的參數item來決定。10.1.3二叉樹遍歷的Python算法為了對二叉樹進行3種不同的遍歷，先要創建一棵二叉樹，然后再考慮遞歸遍歷的問題。這一切都可以由如下定義的二叉樹類BinaryTree來實現。程序編寫如下：#定義二叉樹類BinaryTreeclassBinaryTree: def__init__(self,value): self.left=None self.right=None self.data=value #創建左子樹函數 definsertLeftChild(self,value): ifself.left: print('Leftchildtreealreadyexists.') else: self.left=BinaryTree(value) returnself.left #創建右子樹函數 definsertRightChild(self,value): ifself.right: print('Rightchildtreealreadyexists.') else: self.right=BinaryTree(value) returnself.right #先根遍歷函數 defpreOrder(self): print(self.data) #輸出根結點的值 ifself.left: self.left.preOrder()#遍歷左子樹 ifself.right: self.right.preOrder()#遍歷右子樹 #后根遍歷函數 defpostOrder(self): ifself.left: self.left.postOrder()#遍歷左子樹 ifself.right: self.right.postOrder()#遍歷右子樹 print(self.data) #輸出根結點的值 #中根遍歷函數 definOrder(self): ifself.left: self.left.inOrder()#遍歷左子樹 print(self.data) #輸出根結點的值 ifself.right: self.right.inOrder()#遍歷右子樹該類由以下6個函數組成。一是初始化函數__init__(self,value)。它的任務是給出一棵空二叉樹的架構，它既沒有左子樹，也沒有右子樹，參數value是根結點的取值。二是創建左子樹函數insertLeftChild(self,value)。它的任務是到達該結點后，先判斷它是否有左子樹，如果有，則輸出“Leftchildtreealreadyexists.”（左子樹已存在）的信息；否則由傳遞過來的參數value建立該結點左子樹的根結點。三是創建右子樹函數insertRightChild(self,value)。它的任務是到達該結點后，先判斷它是否有右子樹，如果有，則輸出“rightchildtreealreadyexists.”（右子樹已存在）的信息；否則由傳遞過來的參數value建立該結點右子樹的根結點。四是先根遍歷函數preOrder(self)。它的任務是完成對二叉樹的先根遍歷，具體是到達一個結點后，先是輸出該結點的值（體現了先根遍歷的特點）；然后如果有左子樹，則通過遞歸方式完成對左子樹的遍歷；如果有右子樹，則通過遞歸方式完成對右子樹的遍歷，從而完成對整個二叉樹的先根遍歷。五是后根遍歷函數postOrder(self)。它的任務是完成對二叉樹的后根遍歷，具體是到達一個結點后，如果有左子樹，則通過遞歸方式完成對左子樹的遍歷；如果有右子樹，則通過遞歸方式完成對右子樹的遍歷；最后輸出該結點的值（體現了后根遍歷的特點），從而完成對整個二叉樹的后根遍歷。六是中根遍歷函數inOrder(self)。它的任務是完成對二叉樹的中根遍歷，具體是到達一個結點后，如果有左子樹，則通過遞歸方式完成對左子樹的遍歷；然后輸出該結點的值（體現了中根遍歷的特點）；最后如果有右子樹，則通過遞歸方式完成對右子樹的遍歷，從而完成對整個二叉樹的中根遍歷。把這一段代碼保存成“Tree10.py”文件，例如保存在D盤根目錄下，這樣誰想使用它，都可以通過“importTree10”將模塊導入。例10-5試importTree10#導入二叉樹模塊root=Tree10.BinaryTree('root')#創建該二叉樹的根結點rootb=root.insertLeftChild('B')c=root.insertRightChild('C')d=b.insertLeftChild('D')e=b.insertRightChild('E')h=e.insertLeftChild('H')f=c.insertLeftChild('F')i=f.insertRightChild('I')g=c.insertRightChild('G')print('中根遍歷序列是：')root.inOrder()print('先根遍歷序列是：')root.preOrder()print('后根遍歷序列是：')root.postOrder()print('從B結點開始的中根遍歷序列是：')b.inOrder()運行該程序，下圖中只顯示了先根、后根及從B結點開始的中根遍歷序列結果。10.2Python中的堆排序所謂“排序”，是指把一系列雜亂無章的無序數據排列成有序序列的過程。給定一組結點r1、r2、…、rn，對應的關鍵字分別為k1、k2、…、kn。將這些結點重新排列成rs1、rs2、…、rsn，使得對應的關鍵字滿足ks1≤ks2≤…≤ksn的升序條件。這種重排一組結點、使其關鍵字值具有非遞減順序的過程就稱為“排序”。當然，讓關鍵字排序后表現出一種非遞增關系也是可以的，這也是“排序”。排序時依據的關鍵字類型，可以是字符、字符串、數字等，只要存在一種能夠比較關鍵字之間順序的辦法即可。我們討論時關注的是決定結點順序的關鍵字，而不是它的內容。10.2.1堆的定義二叉樹中有一種所謂的“完全二叉樹”，是指該二叉樹除最后一層外，其余各層的結點都是滿的，且最后一層的結點都集中在左邊，右邊可以連續缺少若干個結點。下圖所示的兩棵二叉樹都是完全二叉樹。對下圖（a）來說，雖然最后一層少了3個結點，但這3個結點是最右邊的連續3個結點，符合完全二叉樹的定義；對下圖（b）來說，雖然最后一層只有最左邊的一個結點，但少的是右邊連續的7個結點，符合完全二叉樹的定義。“堆”是一棵完全二叉樹，且各結點的關鍵字值滿足如下條件：從根結點到任何一個孩子結點的路徑上的關鍵字值都是非遞減的，也就是說，根結點和任何分支結點的關鍵字值均小于或等于其左、右孩子結點（如果有的話）的關鍵字值。形式上，可以這樣來定義堆。有n個結點的關鍵字序列k1、k2、…、kn，若它們之間滿足條件：ki≤k2i，并且ki≤k2i+1（i=1，2，…，n/2，且2i+1≤n）那么該序列被稱為一個“堆”。可以把關鍵字序列的每個ki看作是這棵有n個結點的完全二叉樹的第i個結點，其中k1是該完全二叉樹的根結點。例10-6有關鍵字序列10、23、18、68、94、72、71、83，由它構成的下圖所示的完全二叉樹是一個堆，因為該完全二叉樹上結點的關鍵字之間滿足堆的條件，即有：10≤23≤68≤83，10≤23≤94，10≤18≤71，10≤18≤72對于堆，要注意如下3點：●在一個堆里，k1（即完全二叉樹的根結點）是堆中所有結點里關鍵字值最小的記錄。●堆的任何一棵子樹本身也是一個堆。●堆中任一結點的關鍵字值都不大于左、右兩個孩子結點的關鍵字值（如果有的話），但是左、右孩子結點的關鍵字值之間沒有大小關系存在。例如，上圖所示的堆，其根結點的關鍵字值10是堆中所有關鍵字值里最小的；例如，以23為根結點的子樹，也滿足堆的條件，是一個堆；例如，10的左孩子結點的關鍵字23大于其右孩子結點的關鍵字18，但18的左孩子結點的關鍵字71卻小于右孩子結點的關鍵字72。10.2.2對堆排序過程的描述由堆的定義知道，堆里根結點的關鍵字值k1是堆中最小的。在利用堆進行排序時，首先可以輸出根結點k1，然后通過一定的規則對余下的結點進行調整，使它們之間又成為一個堆，這樣再輸出新的根結點。如此下去，最終由輸出的結果可以得到一個由小到大的序列。這就是堆排序的基本思想。例10-7關鍵字序列10、23、18、68、94、72、71、83是一個堆，相應的完全二叉樹如下圖（a）所示，對它進行堆排序，得出一個遞增的序列。堆排序不可能一蹴而就，而是一個“不斷輸出根結點→調整剩余結點→形成一個新堆”的過程，如下圖下圖下圖下圖下圖下圖下圖下圖下圖不斷重復地去做這樣的工作：輸出堆頂元素、用當時堆中最后一個元素代替堆頂元素、以使完全二叉樹上的結點滿足堆的定義，直到堆中元素全部輸出為止。輸出的結點就是對初始堆的排序結果，即：10、18、23、68、71、72、83、94。10.2.3Python中的堆排序方法Python中提供了一個標準庫模塊——heapq，該模塊給出了一些方法，能夠很容易地實現上述復雜的堆排序過程。不過程序中要使用它時，必須先將其導入（import）。1．heappush()具體使用：heapq.heappush(<堆>,<關鍵字>)其中<堆>是要創建的堆的堆名，它必須是一個列表；<關鍵字>是要插入堆里的結點的關鍵字。2．heappop()具體使用：heapq.heappop(<堆>)其中<堆>是已存在的堆名，它必須是一個列表。功能：從<堆>里彈出（即刪除）頂元素并返回，隨之自動調整堆中的剩余關鍵字，以保持完全二叉樹堆的性質不變。利用方法heappush()可以創建出一棵滿足堆性質的完全二叉樹；利用方法heappop()可以從堆的頂端逐一彈出（刪除）堆的最小關鍵字，完成對堆中結點的升序排列，達到堆排序的目的。3．heapify()具體使用：heapq.heapify(<列表>)功能：將<列表>轉換為一個具有堆特性的完全二叉樹。4．heapreplace()具體使用：heapq.heapreplace(<堆>,<關鍵字>)功能：用給出的<關鍵字>替換<堆>中的最小元素，自動重新構建成一個堆。5．nlargest()具體使用：heapq.nlargest(n,<堆>)功能：以降序方式返回<堆>中n個結點的關鍵字。6．nsmallest()具體使用：heapq.nsmallest(n,<堆>)功能：由升序方式返回<堆>中n個結點的關鍵字。因此，如果需要獲取整個堆中關鍵字值的降序排列或升序排列，就可以使用方法heapq.nlargest()或heapq.nsmallest()。7．<堆>[0]功能：查看<堆>中的最小關鍵字值，元素不彈出。如果只是想獲取而不是彈出（刪除）最小關鍵字值，則可使用此方法。下面舉幾個例子，說明Python中堆的各種方法的應用。例10-8了解方法heappush()和heappop()的功能。importheapq#創建一個堆heap1=[]nums=[75,79,71,68,94,16,11,28]foriinnums:heapq.heappush(heap1,i)print('堆中已有元素：',heap1)print('\n')#從堆中彈出關鍵字完成排序lis=[]foriinrange(len(nums)):x=heapq.heappop(heap1)lis.append(x)print('出堆元素：'+str(x),end='')print('堆中剩余元素：',heap1)#輸出堆排序結果print('\n')print('堆排序的結果：',lis)該程序分為3個部分，第1部分是給出一個列表：nums=[75,79,71,68,94,16,11,28]通過for循環，調用方法heappush()，不斷把列表nums中的關鍵字插入堆heap1中，最終形成一個待排序的堆heap1。下圖所示的第1部分展現了利用完全二叉樹創建該堆的過程。這其實就是借助完全二叉樹實現建堆的過程。上圖所示的第1部分輸出8組數據，被標注了（1）～（8），它們對應下圖中給出的（1）～（8）。下圖（a）表明完全二叉樹只有一個根結點。下圖（b）是按照完全二叉樹的組成方式，把關鍵字79安排在根結點75的左子樹上。下圖（c）和（d）是按照完全二叉樹的組成方式，把關鍵字71安排在根結點75的右子樹上。這時為了滿足堆的性質，必須把結點75和71對調，所以上圖所示的第1部分第（3）行輸出的完全二叉樹是71,79,75。進到第4次循環時，把關鍵字68插入結點79的左子樹，如下圖（e）所示，它破壞了堆的性質，因此要將68與79對調，再將68與71對調，這時的完全二叉樹如下圖（g）所示。這樣一次次地在完全二叉樹上做插入工作，插入后可能會引起結點間位置的調整，因此，為滿足堆的性質，就有了下圖（l）~（q），便完成了整個堆的創建。程序的最后是輸出列表lis中記錄的對堆heap1的升序排序結果。例10-9了解方法heapify()和heapreplace()的功能：importheapqmls=[25,2,33,5,7,18,1,4,10,242]print('列表mls的元素是：',mls,'\n')heapq.heapify(mls)print('堆mls的元素是：',mls,'\n')heapq.heapreplace(mls,80)print('用80替換最小堆元素后，新堆是：',mls,'\n')程序中給出的mls是一個列表，作為參數傳遞給heapq的方法heapify()，實現將mls改造成堆的過程，因此在下圖的前兩行輸出的內容就不一樣了，第1行輸出的是列表mls的內容，第2行輸出的則是將mls轉換成堆以后堆中的關鍵字內容。下圖最后一行輸出的是用80代替堆mls中的最小關鍵字1后，重新組成的堆的內容，這時原來的最小值1沒有了，80調整到了它應該在的位置上。例10-10了解方法nlargest()、nsmallest()、heap[0]的功能：importheapqmls=[25,2,33,5,7,18,1,4,10,242]print('堆元素的降序排列是:',heapq.nlargest(10,mls),'\n')print('堆前4個元素的升序排列是：',heapq.nsmallest(4,mls),'\n')print('堆中的最小元素是:',mls[0])10.3Python中的隊列Python中有3種隊列：先進先出隊列、后進先出隊列（又名“棧”），以及優先級隊列。它們在數據結構課程中都有討論，在操作系統設計中有著廣泛的應用。10.3.13種隊列的概念1．先進先出隊列——FIFO若對Python中的有序可變數據結構（例如列表）加以限定，使得對其的插入操作在一端進行，刪除操作在另一端進行，那么這種被限定的有序可變數據結構就稱為“隊列”，有時也稱為“排隊”。由此定義可以得知：●隊列是一種有序可變的數據結構，隊列中的各個數據元素之間呈線性關系；●進入隊列（即插入）被限制在隊列的一端進行，退出隊列（即刪除）被限制在隊列的另一端進行，進隊和出隊的操作位置是不能隨意改變的。在計算機操作系統中，經常要把它所管理的各種資源（例如CPU、存儲器、設備）分配給申請者使用，這時采用的分配策略，大多是讓申請者排成一個隊列進行等候，也就是采用隊列管理的辦法。在隊列中，被允許進入隊列的一端常稱為“隊尾”，退出隊列的一端常稱為“隊首”。當一個元素從隊列的隊尾插入時，稱為“進隊”，進入的元素成為新的隊尾元素；從當前的隊首刪除一個元素時，稱為“出隊”，這時隊列中被刪除元素的下一個元素即成為新的隊首。可見，在隊列的運行過程中，隨著數據元素的不斷進隊、出隊，隊尾、隊首元素都在不停地變化著。當隊列里不含有任何數據元素時，稱其為“空隊列”。對于一個空隊列，因為它已經沒有了元素，所以不能再對它進行出隊操作了，否則就會出錯。假設有隊列Q=[a1,a2,a3,…,an?1,an]，如圖所示。那么意味著該隊列中的元素是以a1、a2、a3、…、an?1、an的順序一個接一個進入隊列的。如果要出隊，第1個由此不難理解，最先進入隊列的那個元素肯定是最先從隊列中出去的。因此把隊列稱作具有“先進先出（First-In-First-Out，FIFO）”或“后進后出（Last-In-Last-Out，LILO）”邏輯特點的數據結構，意思是元素到達隊列的順序與離開隊列的順序是完全一致的。下圖描述了進隊操作和出隊操作對隊尾、隊首的影響。元素10進隊時，由于原先隊列為空，因此隊列上就只有10這個元素；元素8進隊后，隊列上就有了兩個元素；元素10出隊，隊列上又只有8這一個元素了；接著元素14和9進隊，整個隊列上有了3個元素；最后元素8出隊，隊列上就只剩下14和9兩個元素了。對于隊列來說，由于隊首和隊尾兩個方向的元素都在不斷地變化著，所以對其操作和管理所要考慮的問題就要多一些，要復雜一些。2．后進先出隊列——LIFO在數據結構課程中，后進先出隊列常被稱為“棧”。若對Python中的有序可變數據結構（例如列表）加以限定，使插入和刪除操作只能在固定的同一端進行，那么這種有序可變的數據結構就被稱為所謂的“堆棧”，簡稱為“棧”。由此定義可以得知：●棧是一種有序可變的數據結構，棧中各個數據元素之間呈線性關系；●對棧的插入和刪除操作被限制在棧的同一端進行，不能任意改變。子彈夾就是一個棧：往彈夾里壓入子彈，就是對棧進行插入操作；扣動扳機進行射擊，就是對棧進行刪除操作。插入和刪除都限定在彈夾口這端進行。在一個棧中，被允許進行插入和刪除的那一端稱為“棧頂”，不能進行插入和刪除的那一端稱為“棧底”。從當前棧頂處插入一個新的元素稱為“進棧”，有時也稱“入棧”“壓棧”，插入的這個元素就成為當前新的棧頂；從當前棧頂處刪除一個元素稱為“出棧”，有時也稱“退棧”“彈棧”，棧頂元素出棧后下一個元素就成為新的棧頂元素。可見，在棧的工作過程中，隨著數據元素的進棧、出棧，只有棧頂元素在不斷地發生變化。當一個棧里不含有任何數據元素時，稱其為“空棧”。對于一個空棧，因為它已經沒有元素了，所以不能再對它進行出棧操作，否則就會出錯。按照棧的定義，最后被插入棧頂的那個元素肯定最先從棧中移出。因此，常把棧稱作具有“后進先出（Last-In-First-Out，LIFO）”或“先進后出（First-In-Last-Out，FILO）”邏輯特點的數據結構，意思是元素到達棧的順序與元素離開棧的順序恰好是相反的。例如，下圖（a）所示為一個空棧，棧頂（top）和棧底（bottom）都位于棧的最底部；下圖（b）所示為3個元素a1、a2、a3依次進棧后棧的示意圖。從圖中看出，a1最先進棧，a2次之，a3最后進棧。如果在棧中的這幾個元素要出棧的話，那么應該是a3最先出棧，a2次之，a1最后出棧。3．優先級隊列——Priority申請使用系統資源時，為申請者規定一個使用的優先級別，依指定的級別高低，將申請者進行排隊，級別高的先獲得使用權，級別低的后獲得使用權。這樣的隊列就是一個所謂的“優先級隊列”。不難看出，在一個申請者進入優先級隊列時，就要按照優先級的大小，對該隊列重新進行一次調整；在資源分配時，總是把資源分配給排在隊列的第1個申請者，并讓該申請者退出隊列。通常總是規定優先數越小，優先級越高。系統中的每一種資源數量總是有限的，因此當一個申請者向系統提出資源申請時，不一定能夠立刻得到滿足。在申請者得不到所需要的資源時，系統就可能會暫時使它無法運行下去，需要讓它等一等。這時就稱該申請者處于“阻塞”或“等待”狀態。一個處于阻塞狀態的申請者，只有在獲得了所需要的資源之后，才能夠繼續運行下去。例10-11設有6個元素a1、a2、a3、a4、a5、a6，它們以此順序依次進棧（即a1必須最先進棧，然后是a2進棧，最后才是a6進棧）。假定要求它們的出棧順序是a2、a3、a4、a6、a5、a1，那么應該如何安排它們的進棧和出棧操作序列呢？這個棧的容量至少要有多大呢？這6個元素以下面的順序進棧和出棧，就能保證出棧順序是a2、a3、a4、a6、a5、a1。為了保證第1個出棧的是a2，必須連續做兩次進棧操作，使a1、a2兩個元素進棧。然后做一次出棧操作，使當時位于棧頂的a2出棧，這樣棧里還剩一個元素a1。為了保證第2個出棧的是a3，必須做一次進棧操作，使a3進棧。緊接著做一次出棧操作，使當時位于棧頂的a3出棧，這樣棧里仍只剩一個元素a1。為了保證第3個出棧的是a4，必須做一次進棧操作，使a4進棧。緊接著做一次出棧操作，使當時位于棧頂的a4出棧，這樣棧里仍只剩一個元素a1。為了保證第4個出棧的是a6，必須連續做兩次進棧操作，使a5、a6兩個元素進棧。然后做兩次出棧操作，使當時位于棧頂的a6出棧，再使當時位于棧頂的a5出棧，這樣棧里仍只剩一個元素a1。最后做一次出棧操作，使當時位于棧頂的a1出棧，棧由此變為空。可見，對這個棧的進棧（push）和出棧（pop）操作序列應該是：進棧、進棧、出棧、進棧、出棧、進棧、出棧、進棧、進棧、出棧、出棧、出棧。從進、出棧的過程中可以看出，該棧里面最多同時會有3個元素存在（例如是a6、a5、a1），因此該棧至少應該能夠同時容納3個元素。10.3.2Python中與隊列有關的方法Python提供了創建、操作隊列的模塊，名字是queue。該模塊能夠創建出3種不同類型的隊列對象：FIFO、LIFO以及Priority。（1）創建FIFO隊列：importqueueque=queue.Queue(maxsize=0)這兩條語句表明通過導入queue模塊后，創建了一個名為que的FIFO隊列對象（實例），在該對象里可以容納maxsize個數據元素。maxsize限定隊列的容量，若maxsize<=0，那么創建的隊列的尺寸就是無限制的；否則當插入元素的個數達到maxsize規定的上限時，就會阻止元素進入隊列。插入FIFO這種隊列里的第1個元素，就是第1個退出隊列的元素。（2）創建LIFO隊列：importqueueque=queue.LifoQueue(maxsize=0)這兩條語句表明通過導入queue模塊后，創建了一個名為que的LIFO隊列對象（實例），在該對象里可以容納maxsize個數據元素。maxsize的具體含義如上所述。插入這種隊列里的最后一個元素，肯定是第1個退出隊列的元素。（3）創建Priority隊列：importqueueque=queue.PriorityQueue(maxsize=0)這兩條語句表明通過導入queue模塊后，創建了一個名為que的Priority隊列對象（實例），在該對象里可以容納maxsize個數據元素。maxsize的具體含義如上所述。對于這種隊列，插入元素后會自動對元素實施堆排序（使用heapq模塊），堆頂元素（優先級最高，優先數最小）將是第1個退出隊列的元素。1．方法qsize()功能：返回隊列中當前擁有的元素個數。用法：<隊列名>.qsize()其中<隊列名>是欲求該隊列中的元素個數的名字。2．方法empty()功能：如果隊列為空，返回True；否則返回False。用法：<隊列名>.empty()3．方法full()功能：如果隊列已滿，則返回True；否則返回False。用法：<隊列名>.full()4．方法put()功能：往隊列里插入一個元素。用法：<隊列名>.put(item,

block,

timeout)其中<隊列名>是欲進行插入操作的隊列名稱；item是要插入的元素；block及timeout通常取默認值，可忽略。5．方法get()功能：從隊列里彈出一個元素。用法：<隊列名>.get(block,

timeout)其中<隊列名>是欲進行彈出操作的隊列名稱；block及timeout常取默認值，可忽略。6．方法clear()功能：清空一個隊列。用法：<隊列名>.clear()其中<隊列名>是欲清空的隊列名稱。例10-12在FIFO隊列里調用方法qsize()、put()、get()：importqueueq=queue.Queue(maxsize=10) #q是一個FIFO的隊列對象print('\n','當前隊列q中的元素個數是：',q.qsize(),'個')foriinrange(10):q.put(i) #往隊列里插入10個元素print('\n','當前隊列q中的元素有：',q.queue)print('\n','當前隊列q中的元素個數是：',q.qsize(),'個')x=q.get() #從隊列q里彈出一個元素print('\n','當前退出隊列q的元素是：',x)print('\n','當前隊列q中還有元素：',q.queue)print('\n','當前隊列q中的元素個數是：',q.qsize(),'個')例10-13在LIFO隊列里調用方法qsize()、put()、get()：importqueuelq=queue.LifoQueue(maxsize=10)print('\n','當前棧lq中的元素個數是：',lq.qsize(),'個')foriinrange(10):lq.put(i)print('\n','當前棧lq中的元素有：',lq.queue)print('\n','當前棧lq中的元素個數是：',lq.qsize(),'個')x=lq.get()print('\n','當前出棧lq的元素是：',x)x=lq.get()print('\n','當前出棧lq的元素是：',x)print('\n','當前棧lq中還有元素：',lq.queue)print('\n','當前棧lq中的元素個數是：',lq.qsize(),'個')程序中，兩次調用了方法get()。從下圖可以看出，LIFO隊列確實是一種“后進先出”性質的隊列，對其操作過程中，棧尾保持不變，棧頂在不斷地變化著。例10-14在Priority隊列里調用方法qsize()、put()、get()：importqueuepq=queue.PriorityQueue(maxsize=10)print('\n','當前優先級隊列pq中的元素個數是：',pq.qsize(),'個')pq.put(4)pq.put(7)pq.put(2)pq.put(9)pq.put(14)pq.put(5)print('\n','當前優先級隊列pq中的元素有：',pq.queue)print('\n','當前優先級隊列pq中的元素個數是：',pq.qsize(),'個')x=pq.get()print('\n','當前出優先級隊列pq的元素是：',x)x=pq.get()print('\n','當前出優先級隊列pq的元素是：',x)print('\n','當前優先級隊列pq中還有元素：',pq.queue)print('\n','當前優先級隊列pq中的元素個數是：',pq.qsize(),'個')下圖所示是該程序運行的結果。前面已提及，在優先級隊列里是使用heapq模塊來對隊列中的元素進行排序的。程序中先是用5條put語句讓4、7、2、9、14、5這6個元素插入隊列。插入過程中，Python不斷調整完全二叉樹，最終隊列中的元素組成一棵下圖（a）所示的、排好序的完全二叉樹，它對應上圖中標有①的內容。在程序中第1次調用方法get()后，彈出隊列的元素是2。為了保持堆的特性，將余下的元素進行調整，如下圖（b）和（c）所示。在程序中第2次調用方法get()后，彈出隊列的元素是4。為了保持堆的特性，再次將余下的元素進行調整，如下圖（d）和（e）所示。這棵完全二叉樹的輸出對應上圖中的②。例10-15在FIFO隊列里調用方法full()和empty()。在程序中設置一個能夠存放10個元素的FIFO隊列，先往隊列里插入10個元素1～10，由于隊列滿，于是彈出一個元素再插入一個元素，直至隊列滿。最后將隊列中的元素全部彈出。程序編寫如下：importqueuekq=queue.Queue(10)#定義一個大小為10的隊列count=0j=0foriinrange(1,19): ifkq.full(): #如果隊列滿，就讓隊首元素出隊 print('\n') x=kq.get() print("彈出：",x,'',end='') kq.put(i) print('插入:',i,'',end='') count+=1 if(count%5==0): print('\n')i=1count=0print('\n')whilenotkq.empty(): print('彈出:',kq.get(),'',end='') i+=1 count+=1 if(count%5==0): print('\n')下圖所示是程序的運行結果。10.3.3FIFO、LIFO隊列的自定義實現優先級隊列多用于操作系統的資源管理中，它牽扯到資源的分配與回收，牽扯到申請者在系統中的狀態變化（例如申請不到資源時，其狀態由運行變為阻塞）等，因此在此不涉及優先級隊列，只介紹FIFO及LIFO兩種隊列自定義實現的例子，供大家閱讀和參考。例10-16FIFO隊列的自定義實現：#定義類MyQueueclassMyQueue:def__init__(self,size=10):self.current=0self.size=sizeself.content=[]#入隊函數put()defput(self,v):ifself.current<self.size:self.content.append(v)self.current=self.current+1else:print("Thequeueisfull!")#出隊函數get()defget(self):ifself.content:self.current=self.current-1returnself.content.pop(0)else:print('Thequeueisempty!')#列出隊列當前所有元素defshow(self):ifself.content:print(self.content)else:print('Thequeueisempty!')#置隊列為空defempty(self):self.content=[]#測試隊列是否為空defisEmpty(self):ifnotself.content:returnTrueelse:returnFalse#測試隊列是否為滿defisfull(self):ifself.current==self.size:returnTrueelse:returnFalse#主程序q=MyQueue() #創建類MyQueue的一個對象qq.get() #①q.put(5)q.put(7)print(q.isfull()) #②q.put('A')q.put(3)q.show() #③q.put(10)q.put('B')q.put(6)q.put('x')q.show() #④q.put('Y')q.put('Z')q.put('w') #⑤q.show() #⑥q.get()q.get()q.get()q.show() #⑦下圖所示是該程序的運行結果，主程序中的①～⑦對應下圖中①～⑦的輸出內容，表明這個設計基本上是可以滿足FIFO隊列工作的。從設計中知道，程序是利用Python中的簡單數據結構列表（list）來實現隊列的，隊列名為content，其尺寸由變量size控制。初始化時，size被設定取值為10。在主程序中，調用者可以為size賦予所需的取值。調用方法put()，由變量current記錄應往列表的哪個位置添加元素（利用函數append()），同時它也表明當前列表里有多少個元素。調用方法get()，借助函數pop()，從列表頭（由pop(0)體現）彈出隊列的隊首元素。例10-17LIFO隊列的自定義實現：classStack: #定義棧類Stack def__init__(self,size=10): self.content=[] self.size=size self.current=0 #令棧為空 defempty(self): self.content=[] self.current=0 #測試棧是否為空，空時返回True，否則返回False defisempty(self): ifnotself.content: returnTrue else: returnFalse #如果要縮小棧空間，則可刪除指定大小之后的已有元素 defsetSize(self,size): ifsize<self.current: foriinrange(size,self.current,1): delself.content[i] self.current=size self.size=size #測試棧是否為滿，滿時返回True，否則返回False defisfull(self): ifself.current==self.size: returnTrue else: returnFalse #若棧有空位，則通過調用方法append()讓元素v進棧 defpush(self,v): iflen(self.content)<self.size: self.content.append(v) self.current=self.current+1 else: print('StackFull!') #若棧中有元素，則元素個數減1，棧頂元素出棧 defpop(self): ifself.content: self.current=self.current-1 returnself.content.pop() else: print('Stackisempty!') #輸出棧中元素 defshow(self): print(self.content) #輸出棧中當前的空位數 defshowRemainderSpace(self): print('StackcanstillPUSH',self.size-self.current,'elements.')#主程序importStacks=Stack.Stack()print(s.isempty()) #①print(s.isfull()) #②s.push(5)s.push(8)s.push('A')print(s.pop()) #③s.push('B')s.push('C')s.show() #④s.showRemainderSpace() #⑤s.setSize(3)print(s.isfull()) #⑥s.show() #⑦s.setSize(5)s.push('D')s.push('DDDD')s.push(3) #⑧s.show() #⑨該程序分為兩大部分，一是定義一個棧類Stack，將其存放在一個后綴為“.py”的模塊里，以供使用者調用；二是調用該類的主程序，如圖所示，把它存放在test1.py文件里。正因為如此，在主程序的開始處，用了導入語句“importStack”，將棧模塊導入使用。下圖所示是該程序的運行結果，主程序中的①～⑨對應下圖中①～⑨的輸出內容，表明這個設計基本上可以滿足LIFO隊列的工作。模塊Stack中出現的變量content、current、size的含義與前例相同。要解釋的是，主程序里明顯可以打印輸出的是print以及show，即主程序里的①～⑦和⑨，至于⑧輸出“StackFull！”，那是因為在執行語句“push（3）”時，將遇到棧滿的情況，不能把元素插入棧中，因此才輸出該信息。10.3.4FIFO、LIFO隊列的應用舉例例10-18約瑟夫問題：n個人圍成一個圈，從1開始按順序報數，報到k的人就退出圈，接著從退出圈的那個人下一個人開始再次從1順序報數，報到k的人又退出圈，不斷地重復這樣的工作，直到剩下最后一個人，該人即為獲勝者。例如，6個人圍坐成一個圈，如圖所示。k=8，規定總是按順時針報數（逆時針同樣也是可以的）。第1輪：2出局，剩余序列為3、4、5、6、1。第2輪：從3開始數，5出局，剩余序列為6、1、3、4。第3輪：從6開始數，4出局，剩余序列為6、1、3。…………如此循環，直到剩余最后一個3，于是退出隊列的順序是2、5、4、1、6、3，3堅持到了最后。下面，編寫一個Python小程序，打算利用隊列這種數據結構，模擬約瑟夫問題所描述的這一淘汰過程。基本思想是：如果報的數不是k，就讓此人插入隊尾；如果報的數是k，就讓其退出隊列。重復這樣的報數過程，直至剩下最后一個人。程序如下：#定義隊列類QueueclassQueue: #以列表items作為隊列的初始化def__init__(self):self.items=[]#清空隊列defempty(self):returnself.items==[]#將元素從索引為0處插入列表defenqueue(self,item):self.items.insert(0,item)#將列表尾元素彈出defdequeue(self):returnself.items.pop()#計算列表中元素個數defsize(self):returnlen(self.items)#對列表邊數數邊調整，將數到k的元素彈出defcircle(self,k,namelist):foriinrange(len(namelist)):queue1.enqueue(namelist[i])i=1 #開始數數whilequeue1.size()!=1:temp=queue1.dequeue() #哪個為第k個就將其存入臨時單元tempifi!=k:queue1.enqueue(temp) #不是第k個時就插入隊列else:print('這次出局的元素是：',temp)i=0i+=1return'獲勝者是：'+str(queue1.dequeue())#主程序queue1=Queue()namelist=['Bill','David','Susan','Jane','Kent','Brad']print(queue1.circle(12,namelist))namelist=[1,2,3,4,5,6]print(queue1.circle(8,namelist))作為隊列，最關鍵的是要確定哪一端是頭，將在這一端進行退出操作；哪一端是尾，將在這一端進行插入操作。類Queue中，函數enqueue()里通過列表items調用方法insert()，保證把要進入隊列的元素插入隊頭；函數dequeue()里則通過列表items調用方法pop()，保證把要退出隊列的元素彈出隊尾。所以，類中的隊列是從頭進入隊列、從尾退出隊列的。類Queue中關鍵的函數是circle()。主程序中調用它時，要傳遞過來兩個參數：一個是決定數到什么數時那個元素應該退出隊列的k值；另一個是把隊列對象queue1進行初始化的列表namelist（最初這里存放的是進行報數的人的名字，或其他什么內容）。然后函數circle()通過變量i數數，如果i不等于k，那么就將臨時工作單元temp中的內容插入隊列中；如果i等于k，那么就舍棄temp中的那個元素（將其從隊列里彈出），將i重新設置為1，開始下一次數數。下圖所示是運行的結果，即當namelist=['Bill','David','Susan','Jane','Kent','Brad']、數的數定為12時，每次輸出出局者，最終獲勝者是Susan；當namelist=[1,2,3,4,5,6]、數的數定為8時，每次輸出出局者，最終獲勝者是3。例10-19利用棧將十進制數轉換成二進制數。Python有提供數制之間轉換的函數，例如一個十進制數調用函數bin()、oct()、hex()，其返回值就是二進制數、八進制數、十六進制數。要注意的是，這些函數返回的結果都是字符串，且會帶有0b、0o、0o前綴，如圖所示。也可以用Python語言自定義函數來代替這樣的數制之間的轉換函數。下面是利用棧編寫的十進制數轉換成二進制數的自定義函數divideBy2()：#定義類StackclassStack:def__init__(self):self.values=[]#進棧函數defpush(self,value):self.values.append(value)#出棧函數defpop(self):returnself.values.pop()#將棧清空defis_empty(self):returnself.size()==0#返回棧的大小defsize(self):returnlen(self.values)#將十進制數轉換為二進制數defdivideBy2(decNumber):remstack=Stack()whiledecNumber>0:rem=decNumber%2print('rem=',rem,end='')#將余數逐個加入remstack.push(rem)decNumber=decNumber//2print('','decNumber=',decNumber)binString=""whilenotremstack.is_empty():binString=binString+str(remstack.pop())returnbinString#主程序x=int(input('請輸入十進制數！'))print('需要轉換的十進制數是：',x)print(divideBy2(233))下圖所示是主程序運行的結果，即十進制數233轉換成的二進制數是11101001。下圖所示是轉換函數divideBy2()的工作過程：把十進制數用2除后，讓余數（0或1）進入棧remstack，然后重復這一過程，直到十進制數為0時停止。然后反方向將remstack棧中的0、1數列彈出棧到binString字符串中，該字符串的內容就是轉換后的二進制值。下面給出由十進制數轉換成任意進制數的函數baseC()：#進制轉換（十進制數轉換成任意進制數）defbaseC(decNumber,base):digits="0123456789ABCDEF"temp=[]whiledecNumber>0:rem=decNumber%basetemp.append(rem)decNumber=decNumber//baseresult_String=""whilelen(temp):result_String+=digits[temp.pop()]returnresult_String#主程序print(baseC(25,2))print(baseC(25,8))print(baseC(25,16))print(baseC(78,16))下圖所示是主程序的執行結果。例10-20判斷一個序列是否為另一個入棧序列的出棧序列。當把序列中的元素依序插入棧時，它們從棧中彈出的次序可以與進入時的次序不同。例如元素進入棧時的次序是1、2、3、4、5，它們可以以4、5、3、2、1的次序彈出，即先讓元素1、2、3、4進入，然后彈出元素4，再讓元素5進入，最后把5、3、2、1彈出。于是，這時5個元素雖然是以1、2、3、4、5的順序進入的棧，但卻是以4、5、1、2、3的次序被彈出的棧。但這5個元素卻不能以4、3、5、1、2的次序彈出。下面編寫的小程序可以測試出一個序列是否為另一個入棧序列的出棧序列：#定義函數IsOrder()defIsOrder(pushV,popV):temp=[]foriinpushV:temp.append(i)whilelen(temp)andtemp[-1]==popV[0]:temp.pop()popV.pop(0)iflen(temp):returnFalseelse:returnTrue#主程序pushV=[1,2,3,4,5]popV=[4,5,3,2,1]print(IsOrder(pushV,popV))pushV=[1,2,3,4,5]popV=[4,3,5,1,2]print(IsOrder(pushV,popV))下圖所示是程序的運行結果。為什么是這樣？來看看程序中的4，3，5，1，2出棧序列。程序中設置一個臨時列表temp作為棧，用方法append()將pushV中的第1個元素放入temp中，這里是1；然后判斷棧頂元素是不是出棧順序的第1個元素（temp[-1]==popV[0]？）。由于此時popV[0]里是4，顯然1≠4，所以進入for循環的下一輪，繼續將pushV的下一個元素壓入temp棧。這樣的過程一直進行到滿足while循環中的相等條件，然后開始對popV做出棧操作。一個元素出棧，就將出棧順序向后移動一位，直到不相等，這樣的循環與壓棧過程結束，如果臨時棧temp不為空，說明彈出序列不是該棧的彈出順序，于是返回False。例10-21中綴表達式轉換為后綴表達式。在計算由中綴表達式轉換成后綴表達式的基本規則是：●如果遇到操作數，直接輸出到result。●棧空時遇到運算符，進入棧stack。●遇到左括號，進入棧stack。●遇到右括號，執行出棧stack操作，并將出棧的元素輸出到result，直到彈出棧的是左括號，左括號不輸出。●遇到其他運算符（如+、-、*、/）時，彈出所有優先級大于或等于該運算符的棧頂元素，然后將該運算符輸入棧stack。●最終將棧中的元素依次彈出棧stack，輸出至result。

經過上面的步驟，result中得到的就是轉換完成的后綴表達式。例如，中綴表達式“9+(3-1)×3+8÷2”轉換為后綴表達式后的結果是“931-3*+82/+”，整個步驟如下：（1）初始化棧，以供符號進出棧使用。（2）第1個符號是數字“9”，根據規則，數字輸出到result，后面是“+”，進棧stack。（3）第3個符號是左括號“（”，非數字，進棧stack。（4）第4個符號是數字“3”，輸出到result。（5）第5個符號為“-”，非數字，進棧stack，此時棧內從棧底到棧頂為“+（-”。（6）第6個符號是數字“1”，輸出到result，此時按順序輸出表達式為“931”。（7）第7個符號是右括號“）”，需要去匹配之前的左括號“（”，于是棧頂元素依次出棧，直到出現左括號“（”，其上方只有“-”，輸出即可，此時表達式為“931-”。（8）第8個符號為“*”，因為此時棧頂符號為“+”，根據規則，“*”優先級高于“+”，故“*”直接進棧。（9）第9個符號為數字“3”，輸出到result，此時表達式為“931-3”。（10）第10個符號為“+”，此時的棧頂元素“*”優先級高于它，根據規則，棧中元素需要一次輸出，直到出現比“+”更低的優先級才停止，此時棧內元素優先級均不低于“+”，因此全部出棧，即表達式為“931-3*+”，然后這個“+”進棧stack。（11）第11個符號為數字8，輸出到result。（12）第12個符號為“÷”，比棧內符號“+”優先級高，進棧。（13）最后一個符號為數字“2”，輸出到result。（14）中綴表達式中的符號全部遍歷完，將棧stack中的符號依次輸出就可得到最后的后綴表達式結果。下面是編寫的由中綴表達式轉換為后綴表達式的函數IftoPf()，它將把從調用者那里傳遞過來的中綴表達式exp作為參數：defIftoPf(exp):result=[]#結果列表stack=[]#棧foriteminexp:ifitem.isnumeric():#如果當前字符為數字，那么直接放入列表resultresult.append(item)else:#如果當前字符為一切其他操作符iflen(stack)==0:#如果棧空，直接入棧stackstack.append(item)elifitemin'*/(':#如果當前字符為*/（，直接入棧stackstack.append(item)elifitem==')':#若遇右括號，則從stack彈出元素進入result，直到碰見左括號t=stack.pop()whilet!='(':result.append(t)t=stack.pop()#如果當前字符為加、減且棧頂為乘、除，則開始彈出elifitemin'+-'andstack[len(stack)-1]in'*/':ifstack.count('(')==0:#如果有左括號，彈出運算符到左括號為止whilestack:result.append(stack.pop())else:#如果沒有左括號，彈出所有t=stack.pop()whilet!='(':result.append(t)t=stack.pop()stack.append('(')stack.append(item)#彈出操作完成后將+、-入棧else:stack.append(item)#其余情況直接入棧（如當前字符為+，棧頂為+、-）#表達式遍歷完，但棧中還有操作符不滿足彈出條件，把棧中的東西全部彈出whilestack:result.append(stack.pop())#返回字符串str="" #定義一個空字符串returnstr.join(result)#主程序print('\n')exp="3+(6*7-2)+2*3"print('中綴表達式'+exp+'的后綴表達式是：',end='')print(IftoPf(exp))print('\n