數(shù)據(jù)結(jié)構(gòu)--3章棧和隊(duì)(已修改)
2025-08-17 07:33 本頁(yè)面
【正文】 2022721 數(shù)據(jù)結(jié)構(gòu) 第三章 棧和隊(duì)列 引言：對(duì)線性表 L=(a1,a2,...,an), 可在任意第 i(i=1,2,...n,n+1)個(gè)位置插入新元素， 或刪除任意第 i(i=1,2,...n)個(gè)元素 受限數(shù)據(jù)結(jié)構(gòu) 插入和刪除受限制的線性表。 (stack), (queue). (stack) ▲ 棧 限定在表尾作插入、刪除操作的線性表。 (a1,a2, ,...， an） ← 插入元素 (進(jìn)棧 ) ↑ ↑ ↘ 刪除元素 (出棧） 表頭 表尾 (棧底 ) (棧頂） an a1 棧頂 (top) 棧底 (bottom) 出棧 (pop) 進(jìn)棧 (push) ▲ 進(jìn)棧 插入一個(gè)元素到棧中?；?:入棧、推入、壓入、 push。 ▲ 出棧 從棧刪除一個(gè)元素?；颍?退棧、上托、彈出、 pop。 ▲ 棧頂 表中允許插入、刪除元素的一端 (表尾 )。 ▲ 棧頂元素 處在棧頂位置的元素。 ▲ 棧底 表中不允許插入、刪除元素的一端。 ▲ 空棧 不含元素的棧。 棧的示意圖 ▲ 棧的元素的進(jìn)出原則 : “后進(jìn)先出 ” ,“Last In First Out”。 ▲ 棧的別名 : “后進(jìn)先出 ” 表、 “ LIFO”表、反轉(zhuǎn)存儲(chǔ)器、地窖 。 (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。 (1)輸入 A,B,C,產(chǎn)生輸出 A,B,C的過程： A B,C (1)A進(jìn)棧 B,C (2)A出棧 B C (3)B進(jìn)棧 (4)B出棧 C (5)C進(jìn)棧 (6)C出棧 C A,B,C A A,B A,B A (2)輸入 A,B,C,產(chǎn)生輸出 C,B,A的過程： A B,C (1)A進(jìn)棧 B A C (2)B進(jìn)棧 C B A (3)C進(jìn)棧 B A (4)C出棧 C (5)B出棧 (6)A出棧 C,B,A C C,B (3)輸入 A,B,C,產(chǎn)生輸出 B,C,A的過程 : A B,C (1)A進(jìn)棧 B A C (2)B進(jìn)棧 A C (3)B出棧 C A (4)C進(jìn)棧 A (5)C出棧 (6)A出棧 B,C,A B B,C B 當(dāng) A,B,C依次進(jìn)棧， C出棧后，由于棧頂元素是 B,棧底 元素是 A,而 A不能先于 B出棧 ,所以不能在輸出序列中 , 使 A 成為 C的直接后繼 , 即不可能由輸入 A,B,C產(chǎn)生輸出 C,A,B。 一般地，輸入序列 (...,ai,...,aj,...,ak,...)到 棧中 ,不能得到輸出序列 (...,ak,...,ai,...,aj,...)。 (1)初始狀態(tài) C B A (2)A,B,C進(jìn)棧 B A (3)C出棧 C A,B,C (4)輸入 A,B,C,不能產(chǎn)生輸出 C,A,B: 設(shè)依次輸入元素 A,B,C到棧中 ,可得哪幾種輸出 ? 設(shè)依次輸入元素 C,B,A到棧中 ,可得哪幾種輸出 ? A,B,C (1) A,B,C (2) A,C,B (3) B,A,C (4) B,C,A (5) C,A,B (6) C,B,A C,B,A (1) A,B,C (2) A,C,B (3) B,A,C (4) B,C,A (5) C,A,B (6) C,B,A 討論 ： 假定輸入元素 A,B,C,D 到棧中 ,能得當(dāng)哪幾種輸出 ? 不能得到哪幾種輸出序列？ (1) A,B,C,D (7)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1