Ch棧和隊列實用實用教案

1、重點(zhngdin)和難點 掌握棧和隊列的特點，以便能在應用問題中正確(zhngqu)使用。2021-11-241第1頁/共83頁第一頁，共84頁。知識點 順序棧 鏈棧 循環(huán)(xnhun)隊列 鏈隊列2021-11-242第2頁/共83頁第二頁，共84頁。課前思考(sko) 什么是線性結構？ 你見過餐館中一疊一疊的盤子嗎？如果它們是按1,2,n 的次序往上疊的，那么使用時候的次序應是什么樣的？ 在日常生活中，為了維持(wich)正常的社會秩序而出現(xiàn)的常見現(xiàn)象是什么？2021-11-243第3頁/共83頁第三頁，共84頁。 棧和隊列都是線性數(shù)據(jù)結構 棧：后進先出 隊列：先進先出 和線性表相比，

2、它們的插入和刪除操作受更多的約束和限定(xindng)，故稱為受限的線性表結構。2021-11-244插入刪除線性表I n s e r t ( L , i , x ) (1in+1)Delete(L,i) (1in)線性表允許在表內任一位置進行插入和刪除棧Insert(L,n+1,x)Delete(L,n)棧只允許在表尾一端進行插入和刪除隊列Insert(L,n+1,x)Delete(L,1)隊列只允許在表尾一端進行插入，在表頭一端進行刪除。棧和隊列(duli)第4頁/共83頁第四頁，共84頁。棧2021-11-245第5頁/共83頁第五頁，共84頁。棧的類型定義 棧（Stack）是限定只能在

3、表的一端進行插入和刪除操作的線性表。 表中進行插入、刪除操作的一端稱為(chn wi)棧頂（top），棧頂保存的元素稱為(chn wi)棧頂元素。相對的，表的另一端稱為(chn wi)棧底（bottom）。 當棧中沒有數(shù)據(jù)元素時稱為(chn wi)空棧；向一個棧插入元素又稱為(chn wi)進?；蛉霔?；從一個棧中刪除元素又稱為(chn wi)出棧或退棧。2021-11-246第6頁/共83頁第六頁，共84頁。棧的類型定義 堆棧(duzhn)的特點：后進先出（Last In First Out，簡稱LIFO）2021-11-247第7頁/共83頁第七頁，共84頁。棧 入棧和出棧2021-11-2

4、48第8頁/共83頁第八頁，共84頁。堆棧(duzhn)的抽象數(shù)據(jù)類型定義2021-11-249第9頁/共83頁第九頁，共84頁。堆棧(duzhn)的抽象數(shù)據(jù)類型定義2021-11-2410第10頁/共83頁第十頁，共84頁。堆棧(duzhn)的java接口2021-11-2411第11頁/共83頁第十一頁，共84頁。堆棧(duzhn)中的異常 堆棧(duzhn)為空時出?；蛉ｍ斣貟伋霎惓?021-11-2412第12頁/共83頁第十二頁，共84頁。棧的順序存儲實現(xiàn)(shxin) 順序棧是使用順序存儲結構實現(xiàn)的堆棧，即利用一組地址連續(xù)的存儲單元依次存放堆棧中的數(shù)據(jù)元素。 根據(jù)數(shù)組操作的特性

5、(txng)，選擇數(shù)組下標大的一端，即線性表順序存儲的表尾來作為棧頂。2021-11-2413第13頁/共83頁第十三頁，共84頁。Stack 的順序存儲實現(xiàn)(shxin)2021-11-2414第14頁/共83頁第十四頁，共84頁。Stack 的順序存儲實現(xiàn)(shxin)2021-11-2415第15頁/共83頁第十五頁，共84頁。Stack 的順序存儲實現(xiàn)(shxin)2021-11-2416第16頁/共83頁第十六頁，共84頁。棧的鏈式存儲(cn ch)實現(xiàn) 鏈棧即采用鏈表作為存儲結構實現(xiàn)的棧。 當采用單鏈表存儲線性表后，根據(jù)單鏈表的操作特性(txng)選擇單鏈表的頭部作為棧頂。 入棧操

6、作的實現(xiàn)： 出棧操作的實現(xiàn)：2021-11-2417將top 后移第17頁/共83頁第十七頁，共84頁。棧的鏈式存儲(cn ch)實現(xiàn) 思考：能否(nn fu)將鏈棧中的指針方向反過來，從棧底到棧頂？2021-11-2418不行，如果反過來的話，刪除棧頂元素時，為修改其前驅指針(zhzhn)，需要從棧底一直找到棧頂。第18頁/共83頁第十八頁，共84頁。堆棧(duzhn)的鏈式存儲實現(xiàn)2021-11-2419第19頁/共83頁第十九頁，共84頁。堆棧(duzhn)的鏈式存儲實現(xiàn)2021-11-2420第20頁/共83頁第二十頁，共84頁。堆棧(duzhn)的鏈式存儲實現(xiàn)2021-11-2421

7、第21頁/共83頁第二十一頁，共84頁。棧的應用(yngyng)舉例 數(shù)制轉換 括弧匹配檢驗 迷宮求解(qi ji)問題 表達式求值問題 遞歸函數(shù)的實現(xiàn)2021-11-2422第22頁/共83頁第二十二頁，共84頁。數(shù)制轉換(zhunhun) 數(shù)制轉換原理： N = (N div d)d + N mod d 例如：(1348)10 = (2504)8 ，動畫演示 思考：怎樣將一個(y )十進制的數(shù)值轉換成一個(y )八進制的數(shù)值呢？2021-11-2423第23頁/共83頁第二十三頁，共84頁。用棧實現(xiàn)(shxin)數(shù)制轉換2021-11-2424第24頁/共83頁第二十四頁，共84頁。思考(

8、sko) 用棧處理(chl)數(shù)制轉換問題的好處在哪里？2021-11-2425第25頁/共83頁第二十五頁，共84頁。括弧匹配(ppi)檢驗假設表達式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，如（ （）或（ ）等為正確的匹配，（ ）或（ （ ）或 ( ( ) ) ）均為錯誤的匹配。檢驗括號是否(sh fu)匹配的方法可用“期待的急迫程度”這個概念來描述。即后出現(xiàn)的“左括弧”，它等待與其匹配的“右括弧”出現(xiàn)的“急迫”心情要比先出現(xiàn)的左括弧高。2021-11-2426第26頁/共83頁第二十六頁，共84頁。括弧匹配(ppi)檢驗 例如考慮下列括號序列： 錯誤匹配的情況： 來的右括弧非是

9、所期待的； 來的是不速之客； 直到(zhdo)結束，也沒有到來所期待的。2021-11-2427()12345678第27頁/共83頁第二十七頁，共84頁。括弧匹配(ppi)檢驗 三類“錯誤匹配”情況對應到棧的操作(cozu)： 和棧頂?shù)淖罄ɑ〔幌嗥ヅ洌?棧中并沒有左括弧等在哪里； 棧中還有左括弧沒有等到和它相匹配的右括弧。 思考： 試著寫這個算法，你的算法調試成功了嗎？如果不正確的話，那么你看看哪些細節(jié)沒有考慮到？2021-11-2428第28頁/共83頁第二十八頁，共84頁。2021-11-2429第29頁/共83頁第二十九頁，共84頁。2021-11-2430第30頁/共83頁第三十頁，

10、共84頁。迷宮(mgng)求解問題 思考：你做過迷宮的游戲嗎？你從入口進去之后(zhhu)是如何找到出口的？2021-11-2431第31頁/共83頁第三十一頁，共84頁。迷宮(mgng)的二維數(shù)組模擬2021-11-2432第32頁/共83頁第三十二頁，共84頁。迷宮(mgng)求解問題 求迷宮中一條路徑的算法的基本思想是： 若當前位置可通，則納入(nr)當前路徑，并繼續(xù)朝下一位置探索； 若當前位置不可通，則應順著來的方向退回到前一通道塊，然后朝著除來向之外的其他方向繼續(xù)探索； 若該通道塊的四周四個方塊均不可通，則應從當前路徑上刪除該通道塊。2021-11-2433第33頁/共83頁第三十三

11、頁，共84頁。迷宮求解(qi ji)問題 所謂“下一位置”指的是“當前位置”四周四個方向（下、右、上、左）上相鄰的方塊(fn kui)。 假設以棧S記錄當前路徑，則棧頂中存放的是當前路徑上最后一個通道塊。 納入路徑的操作即為當前位置入棧； 從當前路徑上刪除前一通道塊的操作即為出棧。2021-11-2434第34頁/共83頁第三十四頁，共84頁。初始化，將起點加入堆棧(duzhn)；while(堆棧(duzhn)不空)取出棧頂位置作為當前位置；如果 當前位置是終點，則 使用堆棧(duzhn)記錄的路徑標記從起點至終點的路徑；否則 按照向下、右、上、左的順序將當前位置下一個可以探索的位置入棧；/從

12、堆棧(duzhn)取出的探索方向順序則是左、上、右、下如果 當前位置四周均不可通則 當前位置出棧；35第35頁/共83頁第三十五頁，共84頁。迷宮(mgng)單元的定義2021-11-2436第36頁/共83頁第三十六頁，共84頁。迷宮中從起點(qdin)到終點路徑的求解2021-11-2437第37頁/共83頁第三十七頁，共84頁。2021-11-2438第38頁/共83頁第三十八頁，共84頁。2021-11-2439第39頁/共83頁第三十九頁，共84頁。2021-11-2440第40頁/共83頁第四十頁，共84頁。2021-11-2441第41頁/共83頁第四十一頁，共84頁。表達式求值

13、問題(wnt) 表達式定義：表達式:= 操作數(shù) 運算符 操作數(shù) 操作數(shù):= 簡單( jindn)變量 | 表達式簡單( jindn)變量:= 標識符 | 無符號整數(shù) 二元表達式的三種標識方法： 假設 Exp = S1 + OP + S2，則 稱 OP + S1 + S2 為表達式的前綴表示法（簡稱前綴式） 稱 S1 + OP + S2 為表達式的中綴表示法（簡稱中綴式） 稱 S1 + S2 + OP 為表達式的后綴表示法（簡稱后綴式）2021-11-2442第42頁/共83頁第四十二頁，共84頁。表達式求值問題(wnt) 例如(lr)： 若a*b+(c-d/e)*f，則它的 前綴式為：+*ab

14、*-c/def 中綴式為：a*b+c-d/e*f 后綴式為：ab*cde/-f*+（動畫演示） 2021-11-2443第43頁/共83頁第四十三頁，共84頁。表達式求值問題(wnt) 綜合比較它們之間的關系可得下列結論： 三式中的 “操作數(shù)之間的相對次序相同”； 三式中的 “運算符之間的相對次序不同”； 中綴式丟失(dis)了括弧信息，致使運算的次序不確定； 前綴式的運算規(guī)則為：連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前且緊靠它們的運算符構成一個最小表達式； 后綴式的運算規(guī)則為： 運算符在式中出現(xiàn)的順序恰為表達式的運算順序； 每個運算符和在它之前出現(xiàn)且緊靠它的兩個操作數(shù)構成一個最小表達式；2021-1

15、1-2444第44頁/共83頁第四十四頁，共84頁。表達式求值問題(wnt) 討論后綴式的情況。 即轉換過程中不改變原表達式中操作數(shù)之間的相對次序； 即轉換過程主要是改變原表達式中各個運算符之間的相對次序； 因此，中綴式?jīng)]什么用； 雖然前綴式中已經(jīng)沒有原表達式中的括弧，但它已經(jīng)包含了原表達式中運算的規(guī)則； 若將原表達式轉換成它的后綴式，那么(n me)我們就可以按后綴式中運算符出現(xiàn)的先后次序來對表達式進行運算了。2021-11-2445第45頁/共83頁第四十五頁，共84頁。表達式求值問題(wnt)如何按后綴式進行運算？求值規(guī)則：先找運算符，后找操作數(shù)。思考：這個(zh ge)算法不難吧？你頭

16、腦中是不是已經(jīng)有了這個(zh ge)算法的大致模樣了？動畫演示2021-11-2446第46頁/共83頁第四十六頁，共84頁。表達式求值問題(wnt) 如何由原表達式轉換成后綴式？ 例一原表達式：a*b/c*d-e+f后綴式：ab*c/d*e-f+ （動畫演示(ynsh)） 例二原表達式：a+b*c-d/e*f后綴式：abc*+de/f*- 優(yōu)先數(shù)2021-11-2447運算符#(+-*/*優(yōu)先數(shù)-1011223第47頁/共83頁第四十七頁，共84頁。表達式求值問題(wnt) 從原表達式求得后綴式的規(guī)則為： 設立運算符棧； 設表達式的結束符為“#”，預設運算符棧的棧底為“#”； 若當前字符是操

17、作數(shù)，則直接發(fā)送給后綴式； 若當前字符為運算符且優(yōu)先數(shù)大于棧頂運算符，則進棧，否則退出棧頂運算符發(fā)送給后綴式； 若當前字符是結束符，則自棧頂至棧底依次將棧中所有運算符發(fā)送給后綴式； “(”對它之前后的運算符起隔離(gl)作用，則若當前運算符為“(”時進棧； )可視為自相應左括弧開始的表達式的結束符，則從棧頂起，依次退出棧頂運算符發(fā)送給后綴式直至棧頂字符為(止。2021-11-2448第48頁/共83頁第四十八頁，共84頁。遞歸函數(shù)的實現(xiàn)(shxin) 當一個函數(shù)在運行期間調用另一個函數(shù)時，在運行該被調用函數(shù)之前(zhqin)，需先完成三件事： 將所有的實在參數(shù)、返回地址等信息傳遞給被調用函數(shù)保

18、存； 為被調用函數(shù)的局部變量分配存儲區(qū)； 將控制轉移到被調用函數(shù)的入口。 從被調用函數(shù)返回調用函數(shù)之前(zhqin)，應該完成： 保存被調函數(shù)的計算結果； 釋放被調函數(shù)的數(shù)據(jù)區(qū)； 依照被調函數(shù)保存的返回地址將控制轉移到調用函數(shù)。2021-11-2449第49頁/共83頁第四十九頁，共84頁。遞歸函數(shù)的實現(xiàn)(shxin) 當多個函數(shù)嵌套調用時，由于函數(shù)的運行(ynxng)規(guī)則是：后調用先返回，因此各函數(shù)占有的存儲管理應實行棧式管理。2021-11-2450第50頁/共83頁第五十頁，共84頁。遞歸函數(shù)的實現(xiàn)(shxin) 在執(zhí)行遞歸函數(shù)的過程(guchng)中需要一個遞歸工作棧。它的作用是: 將

19、遞歸調用時的實在參數(shù)和函數(shù)返回地址傳遞給下一層執(zhí)行的遞歸函數(shù)； 保存本層的參數(shù)和局部變量，以便從下一層返回時重新使用它們。2021-11-2451第51頁/共83頁第五十一頁，共84頁。遞歸函數(shù)的實現(xiàn)(shxin) 遞歸過程執(zhí)行過程中占用的數(shù)據(jù)區(qū)，稱之為遞歸工作棧。 每一層的遞歸參數(shù)(cnsh)等數(shù)據(jù)合成一個記錄，稱之為遞歸工作記錄。 棧頂記錄指示當前層的執(zhí)行情況，稱之為當前活動記錄。 遞歸工作棧的棧頂指針，稱之為當前環(huán)境指針。2021-11-2452第52頁/共83頁第五十二頁，共84頁。遞歸函數(shù)的實現(xiàn)(shxin) 例：梵塔函數(shù)(hnsh) 動畫演示2021-11-2453第53頁/共83

20、頁第五十三頁，共84頁。import java.util.Stack; public class Hanoi public static void main(String args) Hanoi hnt = new Hanoi(6); public Hanoi(int count) this.count = count; hanoi(count,A,B,C,0);2021-11-2454第54頁/共83頁第五十四頁，共84頁。private void hanoi(int n,char start,char transit,char destination,int level) if(n = 1

21、) move(n,start,destination); return; level+; hanoi(n-1,start,destination,transit,level); move(n,start,destination); hanoi(n-1,transit,start,destination,level); 2021-11-2455第55頁/共83頁第五十五頁，共84頁。private class Element public int n,level; public char start,transit,destination; public Element(int n,char s

22、tart,char transit,char destination,int level) this.n = n; this.start = start; this.transit = transit; this.destination = destination; this.level = level; 56第56頁/共83頁第五十六頁，共84頁。private void hanoi_stack(int n,char start,char transit,char destination,int level) Stack stack = new Stack(); stack.push(new

23、 Element(n,start,transit,destination,level); while(!stack.empty() Element e = stack.pop(); if(e.n = 1) move(e.start,e.destination); else stack.push(new Element(n-1,e.transit,e.start,e.destination,level); move(e.start,e.destination); stack.push(new Element(n-1,e.start,e.destination,e.transit,level);

24、e = null; 2021-11-2457第57頁/共83頁第五十七頁，共84頁。private void move(int mark,char start,char destination) StringBuffer sb = new StringBuffer(); sb.append(move ); sb.append(mark); sb.append( from ); sb.append(start); sb.append( to ); sb.append(destination); sb.append(rn); System.out.print(sb.toString();sb.de

25、lete(0,sb.length(); 2021-11-2458第58頁/共83頁第五十八頁，共84頁。private void move(char start,char destination) StringBuffer sb = new StringBuffer(); sb.append(move ); sb.append(the top disk from ); sb.append(start); sb.append( to ); sb.append(destination); sb.append(rn); System.out.print(sb.toString(); sb.delet

26、e(0,sb.length(); private int count;/初始(ch sh)規(guī)模 2021-11-2459第59頁/共83頁第五十九頁，共84頁。隊列(duli)2021-11-2460第60頁/共83頁第六十頁，共84頁。隊列(duli)的定義 隊列（queue）簡稱隊，是一種特殊的線性表。僅允許在表的一端進行( jnxng)插入，而在表的另一端進行( jnxng)刪除。 在隊列中把插入數(shù)據(jù)元素的一端稱為隊尾（rear），刪除數(shù)據(jù)元素的一端稱為隊首（front）。 向隊尾插入元素稱為進隊或入隊，新元素入隊后成為新的隊尾元素；從隊列中刪除元素稱為離隊或出隊，元素出隊后，其后續(xù)元素

27、成為新的隊首元素。 隊列的特性：（First In First Out,簡稱FIFO）2021-11-2461第61頁/共83頁第六十一頁，共84頁。隊列(duli)的抽象數(shù)據(jù)類型定義2021-11-2462第62頁/共83頁第六十二頁，共84頁。隊列(duli)的抽象數(shù)據(jù)類型定義2021-11-2463第63頁/共83頁第六十三頁，共84頁。Queue 接口(ji ku)2021-11-2464第64頁/共83頁第六十四頁，共84頁。異常(ychng)類定義2021-11-2465第65頁/共83頁第六十五頁，共84頁。隊列(duli)的順序存儲實現(xiàn)2021-11-2466第66頁/共83頁

28、第六十六頁，共84頁。循環(huán)(xnhun)數(shù)組 設想數(shù)組A0. capacity-1中的單元不是(b shi)排成一行，而是圍成一個圓環(huán)，即A0接在Acapacity-1的后面。這種意義下的數(shù)組稱為循環(huán)數(shù)組。2021-11-2467第67頁/共83頁第六十七頁，共84頁。循環(huán)(xnhun)隊列 循環(huán)隊列(duli)是隊列(duli)的一種順序存儲表示。 為什么要稱作循環(huán)隊列(duli)而不說是順序隊列(duli)呢？ 動畫演示2021-11-2468第68頁/共83頁第六十八頁，共84頁。循環(huán)(xnhun)隊列的操作 入隊操作 將新元素入隊時，可在隊尾指針指示(zhsh)的單元中存入新元素，并將隊尾指針rear 按逆時針方向移一位。 出隊操作 將隊首指針front 依逆時針方向移一位。2021-11-2469第69頁/共83頁第六十九頁，共84頁。循環(huán)(xnhun)隊列的操作2021-11-2470第70頁/共83頁第七十頁，共84頁。思考(sko) 判別循環(huán)隊列為空的條件(tiojin)應該是什么？在隊列初始化的函數(shù)中，設置隊頭和隊尾指針均為0，那么能否由隊頭指針為0來作為隊列空的判別條件(tiojin)呢？ 由于順序存儲結構是一次性地分配空間，因此在入隊列的操作中首先應該判別當前隊列是否已經(jīng)滿了，那么隊列滿的判別條件(tiojin)又是什么呢？