第三章棧與隊(duì)列(已修改)
2025-09-11 21:46 本頁(yè)面
【正文】 第 三 章 棧與隊(duì)列 東南大學(xué)計(jì)算機(jī)學(xué)院 方效林 本課件借鑒了清華大學(xué)殷人昆老師 和哈爾濱工業(yè)大學(xué)張巖老師的課件 本章主要內(nèi)容 ? 棧 ? 棧的應(yīng)用：表達(dá)式求值 ? 棧與遞歸 ? 隊(duì)列 ? 隊(duì)列的應(yīng)用：電路布線 2 棧 ? 定義：只允許在表的末端進(jìn)行插入和刪除的線性表 ? 特點(diǎn)：先進(jìn)后出 ? 棧的操作 ? 進(jìn)棧 push() ? 出棧 pop() ? 棧頂 top() ? 置空 setEmpty() ? 判斷是否為空 isEmpty() ? 棧滿 isFull() 3 棧 ? 棧的數(shù)組表示 ? 棧的操作 ? 進(jìn)棧 push() ? 出棧 pop() ? 棧頂 top() ? 置空 makeEmpty() ? 判斷是否為空 isEmpty() ? 棧滿 isFull() 4 top a b top c top 空棧 top 棧 ? 棧的單鏈表表示 ? 棧的數(shù)組表示可能棧滿 ? 棧的單鏈表表示無(wú)棧滿問題 ? 入棧在表頭進(jìn)行插入操作 ? 出棧在表頭進(jìn)行刪除操作 5 top c b a null 棧 ? 進(jìn)棧順序?yàn)?(1,2,3)，出棧順序能否為 (3,1,2)? ? 不能， 3出棧時(shí)，說(shuō)明 2和 1都在棧里，而且 2必須先于 1出棧 6 3 2 1 top 作業(yè)： 1， 2， 3， 4， 5， 6依次進(jìn)棧，若出棧順序?yàn)?2， 3， 4， 6， 5， 1 則棧大小至少為多少？ 棧的應(yīng)用：表達(dá)式求值 ? 一個(gè)表達(dá)式由操作數(shù) (亦稱運(yùn)算對(duì)象 )、操作符 (亦稱運(yùn)算符 ) 和分界符組成。 ? 算術(shù)表達(dá)式三種表示 ? 中綴 (infix)表示 ? 操作數(shù) 操作符 操作數(shù) ，如 A+B； ? 前綴 (prefix)表示 ? 操作符 操作數(shù) 操作數(shù) ，如 +AB； ? 后綴 (postfix)表示 ? 操作數(shù) 操作數(shù) 操作符 ，如 AB+； 7 棧的應(yīng)用：表達(dá)式求值 ? 中綴表達(dá)式： A + B * ( C D ) E / F ? 后綴表達(dá)式： A B C D * + E F / ? 表達(dá)式中相鄰兩個(gè)操作符的計(jì)算次序?yàn)椋? ? 優(yōu)先級(jí)高的先計(jì)算； ? 優(yōu)先級(jí)相同的自左向右計(jì)算； ? 當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開始計(jì)算。 ? 前綴和中綴表達(dá)式求值需要兩個(gè)棧；后綴表達(dá)式求值只需一個(gè)棧，相對(duì)簡(jiǎn)單些。 8 棧的應(yīng)用：表達(dá)式求值 ? 從左向右掃描表達(dá)式，用一個(gè)棧暫存掃描到的操作數(shù)或計(jì)算結(jié)果。 ? 后綴表達(dá)式的計(jì)算順序中已隱含了加括號(hào)的優(yōu)先次序，括號(hào)在后綴表達(dá)式中不出現(xiàn) 9 R1 R2 R3 R4 R5 A B C D * + E F / R1 R2 R3 R4 R5 A+B*(CD)E/F 中綴表達(dá)式： 后綴表達(dá)式： 10 作業(yè)： 寫出下列中綴表達(dá)式的后綴表達(dá)式 1. A*B*C 2. A+BC+D 3. A*(B)+C 4. (A+B)*D+E/(F+A*D)+C 5. Aamp。amp。B||!(EF) 6. !(A amp。amp。 !((BC) || (CD))) || (CE) 棧的應(yīng)用：表達(dá)式求值 ? 后綴表達(dá)式求值過(guò)程 ? 順序掃描后綴表達(dá)式每一項(xiàng) ? 若該項(xiàng)是 操作數(shù) ，則進(jìn)棧 ? 若該項(xiàng)是 操作符 op， ?若是單目運(yùn)算符，則出棧一個(gè)操作數(shù) X，并將計(jì)算結(jié)果 opX進(jìn)棧 ?若是雙目運(yùn)算符，則連續(xù)出棧兩個(gè)操作數(shù) X和 Y，并將計(jì)算結(jié)果 X op Y進(jìn)棧 ? 當(dāng)表達(dá)式的所有項(xiàng)都掃描并處理完后，棧頂存放的就是最后的計(jì)算結(jié)果。 11 棧的應(yīng)用：表達(dá)式求值 12 步 輸入 類型 動(dòng)作 棧中內(nèi)容 1 置空棧 2 A 操作數(shù) 進(jìn)棧 A 3 B 操作數(shù) 進(jìn)棧 A B 4 C 操作數(shù) 進(jìn)棧 A B C 5 D 操作數(shù) 進(jìn)棧 A B C D 6 操作符 D、 C退棧，計(jì)算 R1=CD進(jìn)棧 A B R1 7 * 操作符 R B退棧，計(jì)算 R2=B*R1進(jìn)棧 A R2 8 + 操作符 R A退棧，計(jì)算 R3=A+R2進(jìn)棧 R3 9 E 操作數(shù) 進(jìn)棧 R3 E 10 F 操作數(shù) 進(jìn)棧 R3 E F 11 / 操作符 F、 E退棧，計(jì)算 R4=E / F進(jìn)棧 R3 R4 12 操作符 R R3退棧，計(jì)算 R5=R3R4進(jìn)棧 R5 top 空棧 top B A C D top top top A B C D * + E F / 后綴表達(dá)式求值過(guò)程： 棧的應(yīng)用：表達(dá)式求值 13 步 輸入 類型 動(dòng)作 棧中內(nèi)容 1 置空棧 2 A 操作數(shù) 進(jìn)棧 A 3 B 操作數(shù) 進(jìn)棧 A B 4 C 操作數(shù) 進(jìn)棧 A B C 5 D 操作數(shù) 進(jìn)棧 A B C D 6 操作符 D、 C退棧，計(jì)算 R1=CD進(jìn)棧 A B R1 7 * 操作符 R B退棧，計(jì)算 R2=B*R1進(jìn)棧 A R2 8 + 操作符 R A退棧，計(jì)算 R3=A+R2進(jìn)棧 R3 9 E 操作數(shù) 進(jìn)棧 R3 E 10 F 操作數(shù) 進(jìn)棧 R3 E F 11 / 操作符 F、 E退棧，計(jì)算 R4=E / F進(jìn)棧 R3 R4 12 操作符 R R3退棧，計(jì)算 R5=R3R4進(jìn)棧 R5 B A C D top top top R1=CD A B C D * + E F / 后綴表達(dá)式求值過(guò)程： 棧的應(yīng)用：表達(dá)式求值 14 步 輸入 類型 動(dòng)作 棧中內(nèi)容 1 置空棧 2 A 操作數(shù) 進(jìn)棧 A 3 B 操作數(shù) 進(jìn)棧 A B 4 C 操作數(shù) 進(jìn)棧 A B C 5 D 操作數(shù) 進(jìn)棧 A B C D 6 操作符 D、 C退棧，計(jì)算 R1=CD進(jìn)棧 A
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1