數(shù)據(jù)結(jié)構(gòu)第3章-棧和隊列

第3章棧和隊列

3.1棧

3.2棧的應(yīng)用3.3隊列3.1.1棧的定義及其運(yùn)算定義：在表尾一端進(jìn)行刪除和插入操作的線性表叫棧(stack)。允許插入和刪除操作的一端稱為棧頂(top)，另一端稱為棧底(bottom)。處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素。不含任何數(shù)據(jù)元素的棧稱為空棧。3.1棧2.基本運(yùn)算棧的操作不能在棧的中間進(jìn)行，其插入操作和刪除操作都在棧頂進(jìn)行。設(shè)棧為S，下面是棧的基本運(yùn)算。（1）入棧push(S,x)：將元素插入到棧中，使x成為棧S的棧頂元素。（2）出棧pop(S)：取棧頂元素，并從棧中刪除棧頂元素。（3）取棧頂元素GetTop(S)：取棧頂元素。（4）判空Empty(S)：判斷棧是否為空。3.1棧3.1.2棧的順序存儲結(jié)構(gòu)使用線性表的順序存儲結(jié)構(gòu)來表示棧叫棧的順序存儲結(jié)構(gòu)，一般稱為順序棧。（1）類型說明定義3.1順序棧定義3.1棧classSequenceStack(object):def__init__(self):self.MaxStackSize=100self.s=[Noneforxinrange(0,self.MaxStackSize)]self.top=-1 （2）順序棧入棧操作算法3.1順序棧入棧算法3.1棧defPush(self,x):ifself.top<self.MaxStackSize-1:self.top=self.top+1self.s[self.top]=xelse:print("棧滿")return（3）順序棧出棧操作算法3.2順序棧出棧算法3.1棧defPop(self):ifself.IsEmptyStack():print("棧為空")returnelse:iTop=self.topself.top=self.top-1returnself.s[iTop]（4）順序棧取棧頂元素算法3.3順序棧取棧頂元素3.1棧defGetTop(self):ifself.IsEmptyStack():print("棧為空")returnelse:returnself.s[self.top]（4）順序棧判空算法3.4順序棧判空算法3.1棧defIsEmptyStack(self):ifself.top==-1:iTop=True#空棧返回Trueelse:iTop=False#棧不為空返回FalsereturniTop3.1.3棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)與線性表一樣，棧也可以使用鏈表來表示，此時棧叫鏈棧。（1）類型說明定義3.2鏈棧結(jié)點(diǎn)定義3.1棧classStackNode(object):def__init__(self):self.data=Noneself.next=None

4.棧的鏈表存儲結(jié)構(gòu)及基本操作與線性表一樣，棧也可以使用鏈表來表示，此時棧叫鏈棧。（1）類型說明定義3.3鏈棧類定義3.1棧classLinkStack(object):def__init__(self):self.top=StackNode()

（2）鏈棧入棧操作算法3.5鏈棧入棧算法3.1棧defPush(self,da):tStackNode=StackNode()tStackNode.data=datStackNode.next=self.top.nextself.top.next=tStackNodeprint("當(dāng)前入棧元素為：",da)（3）鏈棧出棧操作算法3.6鏈棧出棧算法3.1棧defPop(self):ifself.IsEmpty()==True:print(“空?！?;

returnelse:tStackNode=self.top.nextself.top.next=tStackNode.nextreturntStackNode.data（4）鏈棧取棧頂元素算法3.7鏈棧取棧頂元素3.1棧defGetTop(self):ifself.IsEmpty()==True:print("空棧")returnelse:returnself.top.next.data（5）鏈棧判空操作算法3.8鏈棧判空操作3.1棧defIsEmpty(self):ifself.top.next==None:return1#空棧返回1else:return0第3章棧和隊列

3.1棧 3.2棧的應(yīng)用3.3隊列3.2.1數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換是一種常見的計算。在十進(jìn)制轉(zhuǎn)換成二進(jìn)制時，根據(jù)除2取余法，先得到的余數(shù)是結(jié)果數(shù)的低位數(shù)，最后得到的是結(jié)果數(shù)的最高位，如果直接打印，會使結(jié)果成為倒序數(shù)字。為了得到正確的結(jié)果，借助棧，可以把每次計算的余數(shù)壓入棧，最先得到的余數(shù)在棧底，最后得到的余數(shù)在棧頂，然后從棧中分別彈出各個余數(shù)并打印，可以得到正確的順序。3.2棧的應(yīng)用算法3.9十進(jìn)制數(shù)與其他數(shù)制的轉(zhuǎn)換3.2棧的應(yīng)用s=LinkStack()defDigit_conversion():x=int(input("請輸入一個十進(jìn)制正整數(shù)："))y=int(input("請輸入要轉(zhuǎn)換成的目標(biāo)進(jìn)制:"))whilex:s.Push(x%y)x=x//y算法3.9十進(jìn)制數(shù)與其他數(shù)制的轉(zhuǎn)換3.2棧的應(yīng)用defDigit_conversion():#上述程序續(xù)while!s.IsEmpty():k=s.Pop()print("%d"%k)3.2.2算術(shù)表達(dá)式轉(zhuǎn)換1.算術(shù)表達(dá)式求值例3.2寫出表達(dá)式“3+4/25*8-6”操作數(shù)棧和運(yùn)算符棧的變化情況。解：建立操作數(shù)棧S和算符棧F，操作數(shù)棧S存放掃描表達(dá)式時的數(shù)字，算符棧F用于存放算符。3.2棧的應(yīng)用例3.2寫出表達(dá)式“3+4/25*8-6”操作數(shù)棧和運(yùn)算符棧的變化情況。為操作方便，給表達(dá)式的左右兩邊分別標(biāo)記符號“#”，作為表達(dá)式掃描的起點(diǎn)和終點(diǎn)。操作時，從表達(dá)式的左邊開始掃描，算法如下：(1)若是操作數(shù)，壓入S，繼續(xù)掃描下一個元素。3.2棧的應(yīng)用例3.2寫出表達(dá)式“3+4/25*8-6”操作數(shù)棧和運(yùn)算符棧的變化情況。(2)若是操作符Δ，則進(jìn)入循環(huán)：①若F不空，則比較Δ與F頂元素⊕的優(yōu)先級。②若Δ>⊕,則轉(zhuǎn)（3），否則轉(zhuǎn)③。③使S退兩棧，退出的數(shù)分別為x1,x2；F退一棧，退出的運(yùn)算符為⊕，做運(yùn)算x3=x1⊕x2,x3壓入S。3.2棧的應(yīng)用例3.2寫出表達(dá)式“3+4/25*8-6”操作數(shù)棧和運(yùn)算符棧的變化情況。④重復(fù)①，②，③，直到Δ的優(yōu)先級高于F的頂元素，或F已空。(3)若Δ是結(jié)束符“#”，則算法結(jié)束，此時S中只有一個結(jié)果元素，否則Δ進(jìn)入F，繼續(xù)掃描下一元素，返回（1）。3.2棧的應(yīng)用例3.2寫出表達(dá)式“3+4/25*8-6”操作數(shù)棧和運(yùn)算符棧的變化情況。入棧和出棧的操作過程如圖所示：3.2棧的應(yīng)用

25

/

8

*

4

+

0.16

+

1.28

+

6

-

3

#

3

#

3

#

4.28

#

-1.72

#圖3.4算符棧和操作數(shù)棧的變化3.2.2算術(shù)表達(dá)式轉(zhuǎn)換2.表達(dá)式轉(zhuǎn)換通常在算術(shù)表達(dá)式中，運(yùn)算符放在兩個操作數(shù)之間叫中序式（infixnotation），計算機(jī)程序的編譯器在處理表達(dá)式時，通常不使用中序式，而是把中序式轉(zhuǎn)換成前序式或后序式，前序式叫波蘭式，后序式叫逆波蘭式。3.2棧的應(yīng)用3.2.2算術(shù)表達(dá)式轉(zhuǎn)換2.表達(dá)式轉(zhuǎn)換1)中序式變成前序式所謂的前序式是指運(yùn)算符放在操作數(shù)的前面的表達(dá)式，進(jìn)行轉(zhuǎn)換的規(guī)則如下：①將算式根據(jù)運(yùn)算優(yōu)先次序完全括起來；②移動所有算符取代所有左括弧，以最近為原則；③刪去所有的右括弧。3.2棧的應(yīng)用3.2.2算術(shù)表達(dá)式轉(zhuǎn)換2.表達(dá)式轉(zhuǎn)換1)中序式變成前序式例3.3把表達(dá)式A*B/C和（A+B）-C+D/E轉(zhuǎn)換成前序式。解：（（A*B）/C）/*ABC

（（（A+B）-C）+（D/E））+-+ABC/DE3.2棧的應(yīng)用3.2.2算術(shù)表達(dá)式轉(zhuǎn)換2.表達(dá)式轉(zhuǎn)換2)中序式變成后序式所謂的后序式是指運(yùn)算符放在操作數(shù)的后面的表達(dá)式，進(jìn)行轉(zhuǎn)換的規(guī)則如下：①將算式根據(jù)運(yùn)算優(yōu)先次序完全括起來；②移動所有算符取代所有右括弧，以最近為原則；③刪去所有的左括弧。3.2棧的應(yīng)用3.2.2算術(shù)表達(dá)式轉(zhuǎn)換2.表達(dá)式轉(zhuǎn)換2)中序式變成后序式例3.4把表達(dá)式A*B/C和（A+B）-C+D/E轉(zhuǎn)換成后序式。解：（（A*B）/C）AB*C/

（（（A+B）-C）+（D/E））AB+C-DE/+3.2棧的應(yīng)用3.2.2算術(shù)表達(dá)式轉(zhuǎn)換2.表達(dá)式轉(zhuǎn)換3)中序式變后序式的分析中序式轉(zhuǎn)變成后序式時棧的算法如下。(1)將算式根據(jù)運(yùn)算優(yōu)先次序完全括起來；左右括號的運(yùn)算優(yōu)先級別比運(yùn)算符低。3.2棧的應(yīng)用3.2.2算術(shù)表達(dá)式轉(zhuǎn)換2.表達(dá)式轉(zhuǎn)換3)中序式變后序式的分析中序式轉(zhuǎn)變成后序式時棧的算法如下。(2)從左到右掃描算術(shù)表達(dá)式，令讀入的符號為Δ，若Δ是操作數(shù)，則將Δ輸出到后序式字符串中，若Δ是運(yùn)算符，則有以下情況要考慮：①Δ=左括號，Δ入棧；3.2棧的應(yīng)用3.2.2算術(shù)表達(dá)式轉(zhuǎn)換2.表達(dá)式轉(zhuǎn)換3)中序式變后序式的分析中序式轉(zhuǎn)變成后序式時棧的算法如下。②Δ=右括號，彈出棧頂運(yùn)算符，若不是左括號，則將取出的運(yùn)算符輸出到后序串中，并重復(fù)此步直到取出左括號為止，然后將Δ與最后彈出的左括號丟棄，返回（2）；3.2棧的應(yīng)用3.2.2算術(shù)表達(dá)式轉(zhuǎn)換2.表達(dá)式轉(zhuǎn)換3)中序式變后序式的分析中序式轉(zhuǎn)變成后序式時棧的算法如下。③Δ=運(yùn)算符（+-*/^）:(i)設(shè)棧頂?shù)乃惴麨楱挘籀さ膬?yōu)先權(quán)大于⊕，則將Δ入棧；3.2棧的應(yīng)用3.2.2算術(shù)表達(dá)式轉(zhuǎn)換2.表達(dá)式轉(zhuǎn)換3)中序式變后序式的分析中序式轉(zhuǎn)變成后序式時棧的算法如下。(ii)若Δ的優(yōu)先權(quán)小于或等于⊕，則彈出棧頂算符⊕并輸出到后序串中，返回(i)。(3)最后，若棧不空，則將棧頂算符彈出到后序字串中，直到?？諡橹埂?.2棧的應(yīng)用3.2.2算術(shù)表達(dá)式轉(zhuǎn)換2.表達(dá)式轉(zhuǎn)換例3.5以（A+B）-C+D/E為例，說明中序表達(dá)式轉(zhuǎn)換成后序式的操作棧的使用情況。解：先根據(jù)算術(shù)運(yùn)算的優(yōu)先順序完善括號：（（（A+B）-C）+（D/E））。教材中表3.1給出了中序表達(dá)式轉(zhuǎn)換成后序式的操作棧使用情況和轉(zhuǎn)換過程。3.2棧的應(yīng)用3.2.3子程序調(diào)用在子程序調(diào)用中，當(dāng)子程序完成后，應(yīng)該正確地返回主程序調(diào)用該子程序的地方。在計算機(jī)技術(shù)中使用棧來完成此工作。具體做法是在調(diào)用子程序時，用棧把主程序調(diào)用處的所有參數(shù)保存起來，當(dāng)子程序調(diào)用完成時，從棧中彈出調(diào)用主程序斷點(diǎn)處的所有參數(shù)，使主程序能夠正確地從斷點(diǎn)處繼續(xù)執(zhí)行后續(xù)程序。3.2棧的應(yīng)用3.2.3子程序調(diào)用下面是一個用Python語言描述的程序多層調(diào)用的問題：defB():……③C()……defA():……②B()……deffunc():……①A()……3.2棧的應(yīng)用3.2.3子程序調(diào)用圖3.5是上面程序調(diào)用時棧的使用情況，為簡單起見，調(diào)用A()、B()、C()處的現(xiàn)場信息分別用A、B、C表示。分析如下。（1）開始時，func()在①處調(diào)用A()，程序在調(diào)用處的現(xiàn)場信息A被壓入棧保護(hù)起來；當(dāng)被調(diào)用的子程序A()結(jié)束時，返回func()調(diào)用A()時的現(xiàn)場信息A，使func()得以繼續(xù)進(jìn)行下去。3.2棧的應(yīng)用3.2.3子程序調(diào)用（2）A()在執(zhí)行中調(diào)用B()（②的位置），系統(tǒng)又把程序A()中調(diào)用處的現(xiàn)場信息B壓入棧保護(hù)起來；B()完成后，返回A()中調(diào)用B()時的現(xiàn)場信息B，使A()繼續(xù)執(zhí)行直至完成。（3）B()在執(zhí)行中又調(diào)用了C()（③的位置），系統(tǒng)再次把B()中調(diào)用處的現(xiàn)場信息C壓入棧。當(dāng)C()執(zhí)行完成后，從棧中彈出B()中調(diào)用C()時的現(xiàn)場信息C，使B()繼續(xù)執(zhí)行直至完成。3.2棧的應(yīng)用3.2.3子程序調(diào)用這樣一層一層的調(diào)用，并使用棧來保護(hù)調(diào)用點(diǎn)的現(xiàn)場信息，是計算機(jī)處理程序的重要形式，調(diào)用點(diǎn)的現(xiàn)場信息包括（以X86處理器為例）：（1）處理器的標(biāo)志寄存器信息；（2）處理器中的指令寄存器IP中的內(nèi)容；（3）處理器中代碼段寄存器CS中的內(nèi)容。3.2棧的應(yīng)用3.2.4遞歸調(diào)用遞歸調(diào)用是通過自身調(diào)用解決問題的一種辦法。遞歸現(xiàn)象是自然界存在的一種奇妙的現(xiàn)象，能夠用遞歸調(diào)用解決的問題，必須滿足下列條件：①問題要有出口，否則遞歸調(diào)用將成為死循環(huán)；②問題是有限規(guī)模的。遞歸調(diào)用與棧的使用密切相關(guān)，下面以漢諾塔問題為例討論遞歸調(diào)用問題。3.2棧的應(yīng)用3.2.4遞歸調(diào)用Hanoi塔Hanoi塔問題這樣描述：有三個塔座X、Y、Z，在X上有n個盤，從頂?shù)降滓来尉幪枮?、2、3、…n，每個的盤的半徑依次增加?，F(xiàn)在要求把X座上的n個盤逐個移動倒Z座，依然是原來在X座上的形態(tài)。3.2棧的應(yīng)用3.2.4遞歸調(diào)用Hanoi塔盤移動的規(guī)則為：A、每次只能移動一個盤。B、盤可以插在X、Y、Z中的任何一個上。C、任何時刻都不能將大盤壓在小盤上。3.2棧的應(yīng)用3.2.4遞歸調(diào)用Hanoi塔求解Hanoi塔的算法如下。當(dāng)n=1時，直接把盤從X移到Z；當(dāng)n>1時，需要用Y作為輔助塔，解法為：①把X上的n-1個盤移到Y(jié)，移動中借助Z；②把X上的n號盤移到Z；③把Y上的n-1個盤移到Z，移動時借助X。3.2棧的應(yīng)用算法3.10Hanoi塔遞歸調(diào)用算法3.2棧的應(yīng)用defHanoi(n,x,y,z):ifn==1:move(1,x,z)else:Hanoi(n-1,x,z,y)move(n,x,z)Hanoi(n-1,y,x,z)其中，move()的算法可以設(shè)計為：defmove(m,u,v):print(“disk%dfrom%c,to,%c”%(m,u,v))算法3.10的時間復(fù)雜度為T(n)。設(shè)Hanoi函數(shù)的執(zhí)行時間為f(n)，移動盤子的操作時間為1，當(dāng)n=1時，if語句執(zhí)行1次，則f(1)=1，有：所以，T(n)=O(2n)，當(dāng)n很大時，執(zhí)行此算法很困難。3.2棧的應(yīng)用f(n)=f(n-1)+1+f(n-1)=2f(n-1)+1=……=2if(n-i)+2i-1+…+2+1=(2if(n-i)+2i-1)=……=2n-1f(1)+2n-1-1=2n-1Hanoi塔三個盤的Hanoi塔遞歸調(diào)用過程分析如圖3.7所示。系統(tǒng)在進(jìn)行Hanoi塔的遞歸調(diào)用時，自動創(chuàng)建棧來保存遞歸調(diào)用中的函數(shù)調(diào)用關(guān)系。3.2棧的應(yīng)用3.2.5序列進(jìn)出棧的排列問題對于一個有序序列，由于序列入棧與出棧的順序不同將導(dǎo)致出棧序列與原序列順序不同的問題，如何解決這個問題？下面先討論出棧的序列數(shù)問題，其次討論哪些排列是不可能的。對于n個元素的序列順序進(jìn)棧，出棧共有多少可能排列Cn？經(jīng)過計算可以得到排列數(shù)為：3.2棧的應(yīng)用3.2.5序列進(jìn)出棧的排列問題在這些排列中，哪些是可能的輸出，哪些是不可能的輸出？對于初始輸入序列1,2,3,…,n，利用棧得到輸出序列p1p2…pi…pn，則在p1p2…pi…pn中，如果有i<j<k，則對于一個輸入序列pi<pj<pk，即：…pi，…pj，…pk(pi<pj<pk)不存在這樣的輸出序列：…pk，…pi，…pj。因為pk后進(jìn)先出，滿足棧的特點(diǎn)，而pi在pj的前面進(jìn)入，卻在pj的前面出來，這是不可能的（因為不滿足后進(jìn)先出的原則）。3.2棧的應(yīng)用3.2.5序列進(jìn)出棧的排列問題例3.6已知輸入序列為abcde，請給出部分不可能的輸出序列。解：根據(jù)上面的討論，不可能的輸出序列有：cabde、adbce、abecd、aedbc，因為對于cabde，c在ab后進(jìn)入，先出來是正確的，但a在b先進(jìn)，卻在b前先出來，這是不可能的。對于adbce，a先進(jìn)入就出來，d后進(jìn)先出，但b在c先進(jìn)，卻在c前先出來，這是不可能的。類似地可以分析abecd、aedbc。3.2棧的應(yīng)用3.2.5序列進(jìn)出棧的排列問題例3.6已知輸入序列為abcde，請給出部分不可能的輸出序列。解：根據(jù)上面的討論，下面的輸出序列都是可行的，如：abcde、abced、abdce、abdec、edcba。對于具有5個元素的輸入序列，共有42種排列，所以只給出了部分輸出結(jié)果。讀者可以自己嘗試尋找其他的可能或不可能的序列。3.2棧的應(yīng)用第3章棧和隊列

3.1棧 3.2棧的應(yīng)用3.3隊列3.3.1隊列的定義定義：在表的一端進(jìn)行刪除操作而在另一端進(jìn)行插入操作的線性表叫隊列(queue)。允許刪除操作的一端稱為隊頭，允許插入操作的一端稱為隊尾，如圖3.9所示。新插入的元素只能被加到隊尾，被刪除的元素只能是隊頭元素。3.3隊列2.基本運(yùn)算隊列是特殊的線性表，先進(jìn)先出(firstinfirstout)結(jié)構(gòu)。設(shè)隊列為Q，下面是隊列的基本運(yùn)算。（1）初始化__init__(Q)：創(chuàng)建一個空隊列Q。（2）入隊列AddQ(Q,x)：入隊操作，將元素插入到隊列中，使x成為隊列Q的元素。（3）出隊列DelQ(Q)：出隊操作，取隊頭元素，并從隊列中刪除隊頭元素。3.3隊列2.基本運(yùn)算隊列是特殊的線性表，先進(jìn)先出(firstinfirstout)結(jié)構(gòu)。設(shè)隊列為Q，下面是隊列的基本運(yùn)算。（4）取隊頭元素GetFront(Q)：取隊列頂元素，該元素不出隊列。（5）判空Empty(Q)：判斷隊列是否為空。3.3隊列3.3.2隊列的順序存儲結(jié)構(gòu)隊列的順序存儲是指采用一組物理上連續(xù)的存儲單元來存放隊列中的所有元素。（1）類型說明定義3.4順序隊列定義3.3隊列classSequenceQueue:def__init__(self):self.MAXSIZE=10self.data=[None]*self.MAXSIZEself.front=0self.rear=0 （2）順序隊列的基本操作順序隊列的操作如圖3.10示。3.3隊列（2）順序隊列的基本操作順序隊列的操作如圖3.10示。圖3.10(a)表示空隊列，此時隊列的front=rear=0。圖3.10(b)表示隊列中已經(jīng)有元素A，rear加1，使rear=1。圖3.10(c)表示隊列中連續(xù)進(jìn)入元素B、C、D、E，此時隊尾頂指針rear=5。3.3隊列（2）順序隊列的基本操作順序隊列的操作如圖3.10示。圖3.10(d)表示在圖3.10(c)的基礎(chǔ)上，元素A出隊列，此時，front加1，front=1。圖3.10(e)表示在圖3.10(d)的基礎(chǔ)上多次進(jìn)行出隊操作，隊列已經(jīng)為空隊列，rear=front=5。3.3隊列4.循環(huán)順序隊列及基本操作在圖3.10(e)中，因為rear和front已經(jīng)達(dá)到隊列尾部，rear==MAXSIZE-1，要再插入元素，隊列已滿，無法插入，因而產(chǎn)生了溢出，但實(shí)際上隊列為空。這種現(xiàn)象叫假“溢出”。解決這個問題的辦法是把隊列首尾連接起來，構(gòu)成循環(huán)順序隊列。（1）類型說明定義3.4循環(huán)順序隊列定義3.3隊列4.循環(huán)順序隊列及基本操作（1）類型說明算法3.13循環(huán)順序隊列初始化3.3隊列classCircularSequenceQueue:def__init__(self):self.MAXSIZE=10self.data=[None]*self.MAXSIZEself.front=0self.rear=0

（2）循環(huán)順序隊列入隊操作算法3.14循環(huán)順序隊列入隊操作3.3隊列defAddQ(self,x):if(self.rear+1)%self.MaxQueueSize!=self.front:self.rear=(self.rear+1)%self.MaxQueueSizeself.data[self.rear]=x#元素入隊

print("當(dāng)前進(jìn)隊元素為：",x)else:print("隊列已滿，無法入隊")return （3）循環(huán)順序隊列出隊操作算法3.15循環(huán)順序隊列出隊操作3.3隊列defDelQ(self):ifself.IsEmptyQueue():print("隊列為空，無法出隊")returnelse:self.front=(self.front+1)%self.MaxQueueSizereturnself.data[self.front]

（4）循環(huán)順序隊列取對頭元素算法3.16循環(huán)順序隊列取隊頭元素3.3隊列defGetFront(self):ifself.IsEmptyQueue():print("隊列為空，無法輸出隊首元素")returnelse:#返回隊頭元素item=self.data[(self.front+1)%self.MaxQueueSize

returnitem

（5）循環(huán)順序隊列判空操作算法3.17循環(huán)順序隊列判空操作3.3隊列defIsEmptyQueue(self):ifself.front==self.rear:return1#空隊列返回1else:return0#非空返回0

3.3.3隊列的鏈表存儲結(jié)構(gòu)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱鏈隊列。此時，每個結(jié)點(diǎn)增加一個鏈域。（1）類型說明定義3.5鏈隊列結(jié)點(diǎn)類定義3.3隊列classQueueNode:def__init__(self):self.data=Noneself.next=None

（1）類型說明(續(xù)）定義3.6鏈隊列類定義3.3隊列classLinkQueue:def__init__(self):tQueueNode=QueueNode()self.front=tQueueNodeself.rear=tQueueNode

（2）鏈隊列的入隊操作算法3.18鏈隊列的入隊操作3.3隊列defAddQ(self,x):p=QueueNode()p.data=xself.rear.next=p#頭結(jié)點(diǎn)指針指向新入隊結(jié)點(diǎn)

self.rear=p#隊列尾指針指向新入隊結(jié)點(diǎn)

print("當(dāng)前進(jìn)隊的元素為：",x)

（3）鏈隊列的出隊操作算法3.19鏈隊列的出隊操作3.3隊列defDelQ(self):ifself.IsEmptyQueue():print("隊列為空");returnelifself.front.next.next==None:#隊列中只有一個元素

self.front.next=Noneself.rear=self.frontelse:p=self.front.next;self.front=p.nextreturnp.data （4）鏈隊列取隊頭元素算法3.20鏈隊列取隊頭元素3.3隊列defGetFront(self):ifself.IsEmptyQueue():print("隊列為空")returnelse:returnself.front.next.data

（5）鏈隊列判空操作算法3.21鏈隊列取隊頭元素3.3隊列defIsEmptyQueue(self):ifself.front==self.rear:return1#空隊列返回1else:return0#非空隊列返回0

3.3.4隊列的應(yīng)用在計算機(jī)領(lǐng)域，隊列有十分廣泛的應(yīng)用，網(wǎng)絡(luò)中在同一鏈路上傳輸?shù)臄?shù)據(jù)報文形成一個隊列，在網(wǎng)絡(luò)環(huán)境下各個客戶申請打印的作業(yè)在打印服務(wù)器中形成的隊列，在操作系統(tǒng)中，存在臨界資源的共享和互斥的問題等，都使用了隊列。下面是操作系統(tǒng)中使用隊列的問題示例——生產(chǎn)者與消費(fèi)者問題。這是一個利用循環(huán)