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

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

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

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

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

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失敗 德明科技大學資訊科技系

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

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

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

德明科技大學資訊科技系

函數呼叫 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.{ 3. printf(“f2 no more calling \n”); 4. k++ ; 5.} main f1 f2 5 6 6 7 德明科技大學資訊科技系

函數呼叫 遞迴呼叫呢?? 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.{ 3. printf(“f2 no more calling \n”); 4. k++ ; 5.} push pop push pop f1: m, n; (7) Top main: i, j; (6) main: i, j; (6) Top 遞迴呼叫呢?? 德明科技大學資訊科技系

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

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

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

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

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

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

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

運算式的表示法 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 為甚麼需要後序或前序?? 德明科技大學資訊科技系

中序式→前序式 中序式為 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 德明科技大學資訊科技系

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

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

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

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

中序表示法轉換成前序表示法 堆疊處理法 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. 反轉輸出的字串 德明科技大學資訊科技系

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

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

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

中序表示法轉換成後序表示法 堆疊處理法 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.如果運算式已經讀取完成, 而堆疊中尚有運算子時, 依序由頂端輸出 德明科技大學資訊科技系

中序轉換成後序 範例：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頂端 德明科技大學資訊科技系

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

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

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

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

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

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