堆疊 Stack chapter 4 德明科技大學資訊科技系.

Presentation on theme: "堆疊 Stack chapter 4 德明科技大學資訊科技系."— Presentation transcript:

1 堆疊 Stack chapter 4 德明科技大學資訊科技系

2 堆疊 Stack 堆疊的定義 後進先出 last in first out (LIFO) p4-2
在一有序串列(ordered list)中，資料的新增與刪除都由同一端進行 後進先出 last in first out (LIFO) 德明科技大學資訊科技系

3 堆疊主要的動作 Push：將新項目加在堆疊的頂端 Pop：從堆疊頂端拿走一個項目 TopItem：讀出堆疊頂端的項目
輸入新資料進入堆疊 Pop：從堆疊頂端拿走一個項目 由堆疊輸出一個資料 TopItem：讀出堆疊頂端的項目 只是讀取，資料項目並不會減少 IsEmpty：看堆疊是否為空 空則傳回true，不空則傳回false。 IsFull：看堆疊是否已滿 滿則傳回true，未滿則傳回false 德明科技大學資訊科技系

4 p4-3 Push 與 Pop 德明科技大學資訊科技系

5 p4-4 德明科技大學資訊科技系

6 Push [4] [3] Push(A) Push(B) Push(C) [2] C [1] B B [0] A A A Top= -1
E E D D D Push(D) Push(E) Push(F) C C C B B B A A A Top= 3 Top= 4 Top= 4 Push失敗 德明科技大學資訊科技系

7 Pop [4] [3] Pop( ) Pop( ) Pop( ) [2] [1] B [0] A A Top= 1 Top= 0
德明科技大學資訊科技系

8 堆疊的應用 符合後進先出(LIFO)需求的特性 副程式(函數)呼叫的變數處理 運算式的轉換與求值 圖形的深度優先搜尋
每次呼叫副程式時，將現在的變數資訊放入系統的stack內 可以處理巢狀的函數呼叫，但是變數仍不會混亂 函數呼叫、遞迴呼叫、中斷處理、巨集呼叫等 運算式的轉換與求值 圖形的深度優先搜尋 資料反序輸出(例如: abc -> cba) 德明科技大學資訊科技系

9 函數呼叫處理 p4-5 德明科技大學資訊科技系

10 德明科技大學資訊科技系

11 函數呼叫 1. main() 2.{ 3. int i, j ; 4. printf(“main before
calling f1\n”); 5. f1(); 6. printf(“main returns from f1\n”); 7. } 1.void f1() { 3. int m, n ; 4. m = 2 ; 5. printf(“f1 before calling f2\n”); 6. f2(m); 7. printf(“f1 returns from f2\n”); 8. } 1.void f2( int k ) 2.{ printf(“f2 no more calling \n”); k++ ; 5.} main f1 f2 5 6 6 7 德明科技大學資訊科技系

12 函數呼叫 遞迴呼叫呢?? 1. main() 2.{ 3. int i, j ; 4. printf(“main before
calling f1\n”); 5. f1(); 6. printf(“main returns from f1\n”); 7. } 1.void f1() { 3. int m, n ; 4. m = 2 ; 5. printf(“f1 before calling f2\n”); 6. f2(m); 7. printf(“f1 returns from f2\n”); 8. } 1.void f2( int k ) 2.{ printf(“f2 no more calling \n”); k++ ; 5.} push pop push pop f1: m, n; (7) Top main: i, j; (6) main: i, j; (6) Top 遞迴呼叫呢?? 德明科技大學資訊科技系

13 以陣列來製作堆疊 產生堆疊結構： 製作堆疊最常用的方法就是利用一維陣列 宣告一個陣列結構。
p4-9 製作堆疊最常用的方法就是利用一維陣列 產生堆疊結構： 宣告一個陣列結構。 方法：Create(Stack) //建立一個空的Stack 製作：利用C語言 德明科技大學資訊科技系

14 將資料放入堆疊(Push動作) 將資料(item)插入到Stack中，並且成為Top頂端元素；如果堆疊已滿，則無法進行。
德明科技大學資訊科技系

15 取出資料(Pop動作) 刪除Stack的Top頂端元素，如果堆疊是空，則無法進行 方法：Pop(item,Stack)
德明科技大學資訊科技系

16 在空的Stack中連續加入A,B,C,D 4個資料項
德明科技大學資訊科技系

17 傳回堆疊Top頂端元素 傳回Stack的Top頂端元素，如果堆疊是空，則無法進行 方法：TopItem(Stack)
德明科技大學資訊科技系

18 判斷堆疊是否已滿 判斷Stack是否已滿(Top指標是否等於N-1)，若是則傳回True，否則傳回False
方法：IsFull(Stack) 德明科技大學資訊科技系

19 判斷堆疊是否是空的 判斷Stack是否是空(亦即Top值為-1)，若是則傳回True，否則傳回False。
方法：IsEmpty(Stack) 德明科技大學資訊科技系

20 運算式的表示法 X = A + B * C – ( D + E / F ) 運算式根據運算子的位置可以分為三種：
運算元 X = A + B * C – ( D + E / F ) 等號右邊是算術運算式 運算子 運算式根據運算子的位置可以分為三種： 1.   中序式 ( infix )：運算子在運算元的中間，例如 ： A + B 2.   後序式 ( postfix )：運算子在運算元的後面，例如 ： A B + 3.   前序式 ( prefix )：運算子在運算元的前面，例如 ： + A B 為甚麼需要後序或前序?? 德明科技大學資訊科技系

21 中序式→前序式 中序式為 A×B+C×D 欲轉換成前序式，步驟如下： 1.先用括號將優先順序分出來 ((A×B)＋(C×D))
p4-17 中序式為 A×B+C×D 欲轉換成前序式，步驟如下： 1.先用括號將優先順序分出來 ((A×B)＋(C×D)) 2.將運算子移到最接近且有括住此運算子的左括號右邊，則依優先順序為 ((×AB)＋(×CD)) (＋(×AB)(×CD)) 3.把括弧全部拿掉，即為所得 ＋×AB×CD 德明科技大學資訊科技系

22 中序式→後序式 中序式為 A×B+C×D 欲轉換成後序式，步驟如下： 1.先用括號將優先順序分出來 ((A×B)＋(C×D))
2.將運算子移到最接近且有括住此運算子的右括號左邊，則依優先順序為 ((AB×)＋(CD×)) ((AB×)(CD×)＋) 3.把括弧全部拿掉，即為所得 AB×CD×＋ 德明科技大學資訊科技系

23 中序運算式的計算 舉例: 中序運算式為 A+B*C-D p4-20 步驟1 建立運算元和運算子堆疊，並設初始為空的 步驟2
從左到右讀取運算式 讀到運算元則置入運算元堆疊(Stack1) 讀到運算子則置入運算子堆疊(Stack2) 德明科技大學資訊科技系

24 舉例: 中序運算式為 A+B*C-D 步驟3 讀取“*”時，由於“*”的優先權高於Stack2的top頂端運算子“+” ，故將“*”存入運算子堆疊 步驟4: 讀取 ’C’ 步驟5: 讀取“-”時，因為“-”優先權低於Stack2的top頂端運算子“*”，故取出“*”與兩個運算元進行計算，並將結果存回運算元堆疊 (Stack1)中。 德明科技大學資訊科技系

25 舉例: 中序運算式為 A+B*C-D 步驟6: 因為”-”時，優先權等於Stack2的頂端運算子”+”，故取出”+”與兩個運算元來進行計算，並將結果存回運算元堆疊(Stack1)中。將剛才未存入堆疊的”-”存入運算子堆疊 步驟7:讀取”D” 步驟8: 取出運算子“-”及運算元“A+B*C”及”D”進行計算，結果存回運算元堆疊 德明科技大學資訊科技系

26 中序表示法轉換成前序表示法 堆疊處理法 p4-24 由右而左掃描資料，依據資料是運算元或運算子作不同的處理；運算子還要考慮其優先次序
步驟1. 由右至左依序取得資料di(data item)。 步驟2. 如果di是運算元，則直接輸出。 步驟3. 如果di是運算子（含左右括號），則： (1)如果di=")"，放入堆疊。 (2)如果di="("，依次輸出堆疊中的運算子，直到取出")"為止。 (3)如果di不是“)”或“(”，則與堆疊頂點的運算子ds(data of stack)作優先順 序比較： 當di較ds優先時， 則di放入堆疊，迴圈輸出堆疊資料，直到優先次序相等 當di不較ds優先或相等時，則ds輸出，di放入堆疊。 步驟4. 如果運算式已讀取完成，而堆疊中尚有運算子時，依序由頂端輸出。 步驟5. 反轉輸出的字串 德明科技大學資訊科技系

27 中序轉換成前序 範例：A+B*(C-D) 、由右而左讀取 (1)讀取：‘)’ push放入stack頂端
(4)讀取：‘C’ 輸出：C 目前輸出的字串：DC 德明科技大學資訊科技系 註：中序轉成前序時，右括號在堆疊中的優先順序最小

28 範例：A+B*(C-D) 、由右而左讀取 (6)讀取：‘*’ push放入stack頂端
(5)讀取：‘(’ 依序輸出(POP)堆疊中的運算子，直到取出‘)為止 輸出：－ 目前輸出的字串：DC－ (註：左右括號不會輸出顯示) (6)讀取：‘*’ push放入stack頂端 (7)讀取：’B’ 輸出：B 目前輸出的字串：DC－B 德明科技大學資訊科技系

29 範例：A+B*(C-D) 、由右而左讀取 (8)讀取：‘+’ Stack頂端的運算子優先權高，則先’*’輸出，’+’放入堆疊
輸出：* 目前輸出的字串：DC－B* (9)讀取：’A’ 輸出：A 目前輸出的字串：DC－B*A (10)輸出剩餘的Stack中的資料(運算式已經讀取完成, 而堆疊中尚有運算子時, 依序由頂端輸出) 輸出：+ 目前輸出的字串：DC－B*A+ (11)反轉輸出的字串 +A*B－CD 德明科技大學資訊科技系

30 中序表示法轉換成後序表示法 堆疊處理法 p4-29 由左而右掃描資料，依據資料是運算元或運算子作不同的處理，運算子還要考慮其優先次序
步驟1. 由左至右依序取得資料di(data item)。 步驟2. 如果di是運算元, 則直接輸出。 步驟3. 如果di是運算子(包含左右括號), 則： (1)如果di= "(", 放入堆疊。 (2)如果di= ")" ,依序輸出堆疊中的運算子, 直到取出 "(" 為止。 (3)如果di不是 “(” 或 “)” , 則與堆疊頂點的運算子ds(data of stack)作優先 順序比較： 當di較ds優先時, 則di放入堆疊。 當di不較ds優先或相等時, 則ds輸出，di放入堆疊。 步驟4.如果運算式已經讀取完成, 而堆疊中尚有運算子時, 依序由頂端輸出 德明科技大學資訊科技系

31 中序轉換成後序 範例：A+B*(C-D) 、由左而右讀取 (3) 讀取：’B’ 輸出：B 目前輸出的字串：AB
p4-30 範例：A+B*(C-D) 、由左而右讀取 (1) 讀取：’A’ 輸出：A 目前輸出的字串：A (3) 讀取：’B’ 輸出：B 目前輸出的字串：AB (2) 讀取：‘+’ push放入stack頂端 (2) 讀取：‘*’ push放入stack頂端 德明科技大學資訊科技系

32 範例：A+B*(C-D) 、由左而右讀取 (5) 讀取：‘(’ push放入stack頂端 (7) 讀取：‘-’ push放入stack頂端
(6) 讀取：’C’ 輸出：C 目前輸出的字串：ABC (8) 讀取：’D’ 輸出：D 目前輸出的字串：ABCD 註：中序轉成後序時，左括號在堆疊中的優先順序最小 德明科技大學資訊科技系

33 範例：A+B*(C-D) 、由左而右讀取 (9) 讀取：‘ ) ’ 依序輸出(POP)堆疊中的運算子, 直到取出 “ ( ”為止 輸出：－
(註：左右括號不會輸出顯示) (10)輸出剩餘的Stack中的資料(運算式已經讀取完成, 而堆疊中尚有運算子時, 依序由頂端輸出) 輸出：* 最後輸出的字串：ABCD－*+ 德明科技大學資訊科技系

34 前序表示法轉換成中序表示法 堆疊處理法 p4-36 1.由右至左依序取得資料di 2.如果di是運算元，則放入堆疊中。
(<運算元2><運算子><運算元1>)後，再將結果放入堆疊中 德明科技大學資訊科技系

35 前序轉換成中序 前序式+A*B－CD ，轉換成中序式 德明科技大學資訊科技系

36 後序表示法轉換成中序表示法 堆疊處理法 p4-39 1.由左至右依序取得資料di。 2.如果di是運算元，則放入堆疊中。
德明科技大學資訊科技系

37 後序轉換成中序 後序式ABCD-*+ ，轉換成中序式 德明科技大學資訊科技系