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

第三章、棧和隊列目標(biāo)1、掌握棧和隊列的定義和特點2、熟練掌握順序棧的的基本操作實現(xiàn)算法3、熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法棧用鐵路調(diào)度站表示棧棧的定義和特點1、定義：只能在表的一端（棧頂）進(jìn)行插入和刪除運算的線性表2、邏輯結(jié)構(gòu)：與線性表相同，仍為一對一關(guān)系3、存儲結(jié)構(gòu)：用順序?；蜴湕４鎯?，但以順序棧更常見4、運算規(guī)則：只能在棧頂運算，且訪問結(jié)點時依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）

的原則5、實現(xiàn)方式：關(guān)鍵是編寫入棧和出棧函數(shù)隊列隊列是一種先進(jìn)先出的線性表.

在表一端插入,在另一端刪除。隊列的定義和特點1、定義：只能在表的一端（隊尾）進(jìn)行插入，在另一端（隊頭）進(jìn)行刪除運算的線性表2、邏輯結(jié)構(gòu)：與線性表相同，仍為一對一關(guān)系3、存儲結(jié)構(gòu)：用順序隊列或鏈隊存儲均可4、運算規(guī)則：先進(jìn)先出5、實現(xiàn)方式：關(guān)鍵是編寫入隊和出隊函數(shù)，具體實現(xiàn)依順序隊或鏈隊的不同而不同棧、隊列與一般線性表的區(qū)別棧、隊列是一種特殊（操作受限）的線性表區(qū)別：僅在于運算規(guī)則不同一般線性表邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序表、鏈表運算規(guī)則：隨機(jī)、順序存取棧邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序棧、鏈棧運算規(guī)則：后進(jìn)先出隊列邏輯結(jié)構(gòu)：一對一存儲結(jié)構(gòu)：順序隊、鏈隊運算規(guī)則：先進(jìn)先出順序棧的初始化順序棧的初始化操作就是為順序棧動態(tài)分配一個預(yù)定義大小的數(shù)組空間。順序棧入棧(1)判斷是否棧滿，若滿則出錯(2)元素e壓入棧頂(3)棧頂指針加1def

push(self,e):#將元素壓入棧ifself.top-self.base==self.stack_size:#棧滿

raiseException('棧空間已滿')self.elem[self.top]=e#元素e壓入棧頂,棧頂指針加1self.top+=

1順序棧出棧(1)判斷是否?？?，若空則出錯(2)棧頂指針減1，棧頂元素出棧def

pop(self):#將棧頂元素彈出ifself.top==self.base:raiseException('棧已空')self.top-=1#棧頂指針減1，并返回棧頂元素

returnself.elem[self.top]取棧頂元素(1)

判斷是否空棧，若空則返回錯誤(2)

否則通過棧頂指針獲取棧頂元素隊列的順序表示front=rear=0空隊標(biāo)志：

front==rear入隊：

rear+=

1base[rear]=x出隊：

front+=

1x=base[front]順序隊列存在的問題（假溢出）front=0rear=M時再入隊—真溢出front≠0rear=M時再入隊—假溢出設(shè)大小為M鏈隊列鏈隊列的初始化def

init

(self):#構(gòu)造一個空隊列self.front=QNode()#生成新結(jié)點作為頭結(jié)點，隊頭和隊尾指針指向此結(jié)點self.rear=self.front鏈隊列的初始化操作就是構(gòu)造一個只有一個頭結(jié)點的空隊列鏈隊列的入隊defen_queue(self,e):#插入元素e為新的隊尾元素p=

QNode(e)self.rear.next=p#將新結(jié)點插入到隊尾self.rear=p#修改隊尾指針鏈隊列的出隊def

de_queue(self):#刪除隊頭元素，并返回if

self.front==self.rear:#若隊列空，則拋出異常raiseException('隊列已空')

p=self.front.next#p指向隊頭元素e=p.data#e保存隊頭元素的值self.front.next=p.next#修改頭結(jié)點的指針域if

self.rear==p:#最后一個元素被刪，隊尾指針指向頭結(jié)點

self.rear=self.frontreturnp鏈隊列的取隊頭元素defget_head(self):#返回隊頭元素，不修改隊頭指針

ifself.front!=self.rear:#