數(shù)據(jù)結(jié)構(gòu)03-棧隊(duì)列.ppt

第3章棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)主講教師：祝建華華中科技大學(xué)計(jì)算機(jī)學(xué)院2引言：對(duì)線性表L=(a1,a2,.,an),可在任意第i(i=1,2,.n,n+1)個(gè)位置插入新元素，或刪除任意第i(i=1,2,.n)個(gè)元素受限數(shù)據(jù)結(jié)構(gòu)-插入和刪除受限制的線性表。1.棧(stack)2.隊(duì)列(queue)3.雙隊(duì)列(deque)都屬于插入和刪除受限制的線性表。華中科技大學(xué)計(jì)算機(jī)學(xué)院33.1棧(stack)3.1.1棧的定義和操作1.定義和術(shù)語(yǔ)棧：限定在表尾作插入、刪除操作的線性表。(a1,a2,.，an）插入元素(進(jìn)棧)刪除元素(出棧）表頭表尾(棧底)(棧頂）華中科技大學(xué)計(jì)算機(jī)學(xué)院4ana1棧頂(top)棧底(bottom)出棧(pop)進(jìn)棧(push)進(jìn)棧：插入一個(gè)元素到棧中。或稱(chēng):入棧、推入、壓入、push。出棧：從棧刪除一個(gè)元素?；蚍Q(chēng)：退棧、上托、彈出、pop。棧頂：允許插入、刪除元素的一端(表尾)。棧頂元素：處在棧頂位置的元素。棧底：表中不允許插入、刪除元素的一端?？諚＃翰缓氐臈?。棧的元素的進(jìn)出原則:“后進(jìn)先出”,“LastInFirstOut”。棧的別名:“后進(jìn)先出”表、“LIFO”表、反轉(zhuǎn)存儲(chǔ)器、地窖、堆棧。棧的示意圖華中科技大學(xué)計(jì)算機(jī)學(xué)院52.棧的基本操作(1)Initstack(s)：置s為空棧。(2)Push(s,e)：元素e進(jìn)棧s。若s已滿，則發(fā)生溢出。若不能解決溢出，重新分配空間失敗，則插入失敗。(3)Pop(s,e)：刪除棧s的頂元素，并送入e。若s為空棧,發(fā)生“下溢”(underflow)；為空棧時(shí)，表示某項(xiàng)任務(wù)已完成。(4)Gettop(s,e)：棧s的頂元素拷貝到e。若s為空棧，則結(jié)束拷貝。(5)Empty(s)：判斷s是否為空棧。若s為空棧,則Empty(s)為true；否則為false。華中科技大學(xué)計(jì)算機(jī)學(xué)院6輸入端A,B,C進(jìn)棧進(jìn)棧出棧輸出端調(diào)度站(棧）3.理解棧操作（模擬鐵路調(diào)度站）討論：假設(shè)依次輸入3個(gè)元素(車(chē)廂)A,B,C到棧(調(diào)度站)中,可得當(dāng)哪幾種不同輸出？華中科技大學(xué)計(jì)算機(jī)學(xué)院7AB,C(1)A進(jìn)棧B,C(2)A出棧BC(3)B進(jìn)棧(4)B出棧C(5)C進(jìn)棧(6)C出棧CA,B,CAA,BA,BA(1)輸入A,B,C,產(chǎn)生輸出A,B,C的過(guò)程：華中科技大學(xué)計(jì)算機(jī)學(xué)院8AB,C(1)A進(jìn)棧BAC(2)B進(jìn)棧CBA(3)C進(jìn)棧BA(4)C出棧A(5)B出棧(6)A出棧C,B,ACC,B(2)輸入A,B,C,產(chǎn)生輸出C,B,A的過(guò)程：華中科技大學(xué)計(jì)算機(jī)學(xué)院9AB,C(1)A進(jìn)棧BAC(2)B進(jìn)棧AC(3)B