第 四 章 堆疊(Stack) 課程名稱：資料結構 授課老師：________ 2019/2/23

本章學習目標 1.讓讀者了解日常生活中有許多例子都是堆疊的應用。 2.說明堆疊的運作原理及在運算式上的應用。 2019/2/23

本章內容 4-1 堆疊(Stack) 4-2 以陣列來製作堆疊 4-3 堆疊在運算式上的應用 2019/2/23

4-1 堆疊(Stack) 堆疊(Stack)是一種後進先出(Last In First Out, LIFO)的有序串列，亦即資料處理的方式都是在同一邊進行，也就是由相同的一端來進行插入與刪除動作。而我們日常生活中，也有一些是堆疊的例子，例如堆盤子、書本裝箱…等，都是一層一層的堆上去，如果想要取出箱子中某一本書，也只能從最上面開始取出。 2019/2/23

【定義】 1.一群相同性質元素的組合，即有序串列(ordered List) 。 2.具有LIFO(Last In First Out) 後進先出的特性。 3.將一個項目放入堆疊的頂端，這個動作稱為Push(推入)。 4.從堆疊頂端拿走一個項目，這個動作稱為Pop(彈出)。 5.Push/Pop的動作皆發生在同一端，則稱此端為Top(頂端)。 6.要取出資料時，則只能從Top(頂端)取出，不能從中間取出資料。 2019/2/23

2019/2/23

【堆疊常用專有名詞】 1. Push ：加入新項目到堆疊的頂端。 2. Pop ：取出堆疊頂端一個項目。 3. TopItem ：查看堆疊頂端的項目內容。 4. IsEmpty ：判斷堆疊是否為空，若為空則傳回真(True)， 否則傳回假(False)。 5. IsFull ：判斷堆疊是否為滿，若為滿則傳回真(True)， 2019/2/23

【演算法】 2019/2/23

【舉例】假設有一個空的Stack，實施下列的動作： 實作之展示畫面在下一頁 2019/2/23

【老師上課動態展示】檔案在附書光碟中。 Push E Push A,B,C,D    2019/2/23

【堆疊的應用】 2019/2/23

【舉例】 在電腦中，我們可以利用堆疊具有後進先出的特性，來解決副程式的呼叫。 2019/2/23

【作法】呼叫副程式時，必須先將返回位址暫時儲存到「堆疊」中。 【過程】如下所示： 2019/2/23

4-2 以陣列來製作堆疊 製作堆疊最常用的方法就是利用一維陣列。 1.產生堆疊結構： 宣告一個陣列結構。 方法：Create(Stack) //指建立一個空的Stack 製作：利用VB語言 2019/2/23

將資料(item)插入到Stack中，並且成為Top頂端元素； 如果堆疊已滿，則無法進行。 方法：Push(item, Stack) 2019/2/23

製作：利用VB語言 2019/2/23

假設在空的Stack中連續加入4個資料項item，分別為A,B,C,D， 在加入之後Stack的狀態如下圖所示： 陣列的記憶體配置 假設在空的Stack中連續加入4個資料項item，分別為A,B,C,D， 在加入之後Stack的狀態如下圖所示： 2019/2/23

指刪除Stack的Top頂端元素，如果堆疊是空，則無法進行。。 方法：Pop(item,Stack) 2019/2/23

製作：利用VB語言 2019/2/23

假設在空的Stack中連續加入4個資料項item，分別為A,B,C,D，則在刪除D時，其Stack的變化如下圖所示： 陣列的記憶體配置 假設在空的Stack中連續加入4個資料項item，分別為A,B,C,D，則在刪除D時，其Stack的變化如下圖所示： 2019/2/23

指傳回Stack的Top頂端元素，如果堆疊是空，則無法進行。 方法：TopItem(Stack) 2019/2/23

若使用陣列時，判斷Stack是否已滿(亦即Top指標是否等於N-1)， 若是則傳回True，否則傳回False。 5.判斷堆疊是否已滿 若使用陣列時，判斷Stack是否已滿(亦即Top指標是否等於N-1)， 若是則傳回True，否則傳回False。 方法：IsFull(Stack) 2019/2/23

若使用陣列時，判斷Stack是否是空(亦即Top值為-1)，若是則傳 回True，否則傳回False。 6.判斷堆疊是否是空的 若使用陣列時，判斷Stack是否是空(亦即Top值為-1)，若是則傳 回True，否則傳回False。 方法：IsEmpty(Stack) 2019/2/23

【老師上課動態展示】檔案在附書光碟中。 2019/2/23

4-3 堆疊在運算式上的應用 在日常生活中，我們所使用的四則運算都屬於中序(infix order)運算式，亦即運算子位於兩個運算元之間的表示法。但是，此種表示法電腦並無法直接的處理，因為中序式可能會含有括號，並且運算子可能有不同的優先順序權。因此，若要使用電腦來處理運算式時，則必須要先將「中序式」轉換成「後序式」(postfix order)。 2019/2/23

算術式表示的方式有三種： 一、中序(Infix)表示法 二、前序(prefix)表示法 三、後序(postfix)表示法 2019/2/23

一、中序(Infix)表示法 指數學上的表示方式，就是屬於中序式，把運算子放在兩個運算元的中間。 表示式：<運算元1 > <運算子> <運算元2 > 例如：A+B。 缺點：電腦無法一次依序讀取運算式，因運算式可能含有括號， 且未定義運算子優先順序。 2019/2/23

二、前序表(prefix)示法 指將中序表示法中的運算子和運算元重新調整順序，只是運算子的順序是在運算元前面。 表示式：<運算子> <運算元1 > <運算元2 > 例如：+AB。 2019/2/23

三、後序表(postfix)示法 後序表示法和前序表示法相類似，使得運算子放於運算元後面的表示法。 表示式：<運算元1 > <運算元2 > <運算子> 例如：AB+。 優點：不必使用括號，方便電腦使用。 2019/2/23

4-3.1 運算式的轉換 大部份的運算式(expression)都是由運算元(operand)與運算子(operator)所組成。 例如：A*B+(C/D)-E 其中A,B,C,D為運算元(operand) +,-,*,/為運算子(operator) 2019/2/23

【運算原則】 括號內先處理 優先權較高的運算子先執行 同優先權者，則由其結合性，來決定是由左而右，還是由右而左執行。 2019/2/23

【常見的運算子優先順序】 2019/2/23

一、中序式→前序式 假設有一個中序式為：A×B+C×D，欲轉換成前序式，其步驟如下： 1.先用括號將優先順序分出來 2.將運算子移到最接近且有括住此運算子的左括號右邊，則依優先順序為： ((×AB)＋(×CD)) (＋(×AB)(×CD)) 3.把括弧全部拿掉，即為所得。 ＋×AB×CD 2019/2/23

二、中序式→後序式 假設有一個中序式為：A×B+C×D，欲轉換成後序式，其步驟如下： 1.先用括號將優先順序分出來 2.將運算子移到最接近且有括住此運算子的右括號左邊，則依優先順序為： ((AB×)＋(CD×)) ((AB×)(CD×)＋) 3.把括弧全部拿掉，即為所得。 AB×CD×＋ 2019/2/23

4-3.2 中序運算式的表示法及計算 1.處理中序運算式的計算時，基本上，需要使用兩個堆疊來存運算元 和運算子。 2.當讀取之運算子優先權低於「運算子堆疊」頂端運算子時，則從 「運算子堆疊」與「運算元堆疊」取出運算子與兩個運算元來運算。 2019/2/23

【處理步驟】 步驟1. 建立運算元和運算子堆疊，初始為空。 步驟2. 當運算式尚未讀完時(由左至右) ，則依序讀取運算式的一個 符號(運算元或運算子)。 步驟3. 若讀取的是運算元，則存入運算元堆疊中。 2019/2/23

【處理步驟】<續> 步驟4. 若讀取的是運算子 (1) 若運算子為 "(", 放入堆疊。 註：中序表示式，左括號在堆疊中的優先順序最小，亦即任何運算子 都大於它的優先權。 (2) 若運算子為 ")" ,依序輸出堆疊中的運算子, 直到取出 "(" 為止。 (3)若運算子堆疊為空，則存入運算子堆疊。 (4)若運算子堆疊非空，則與頂端之運算子比較優先權，若較堆疊中的高 則存入堆疊中。若較低或等於時，則從運算子堆疊取出一運算子並從 運算元堆疊取出所需運算元，運算後將結果存回運算元堆疊。然後將 剛剛讀取之運算子存入運算子堆疊。若運算式未讀完時，則回到步驟 (2)。 2019/2/23

【處理步驟】<續> 步驟5.中序運算式讀完之後，若運算子堆疊非空，則從運算子堆疊取出一 運算子並從運算元堆疊取出所需運算元，運算後將結果存回運算元 堆疊。重覆此步驟，直到運算子堆疊為空的。 步驟6.運算元堆疊的最後內容即為運算式之計算結果。 2019/2/23

【舉例】中序運算式為：A+B*C-D 假設：運算元堆疊設為Stack1，運算子堆疊設為Stack2。 步驟1: 建立運算元和運算子堆疊，並設初始為空的 2019/2/23

步驟2: 從左到右讀取運算式，讀到運算元則置入運算元堆疊(Stack1)； 若讀到運算子則置入運算子堆疊(Stack2)。 2019/2/23

步驟3: 讀取“*”時，由於“*”的優先權高於Stack2的top頂端運算子“+” ， 故將“*”存入運算子堆疊 2019/2/23

步驟4: 讀取 ’C’ 2019/2/23

步驟5: 讀取“-”時，因為“-”優先權低於Stack2的top頂端運算子“*”， 故取出“*”與兩個運算元進行計算，並將結果存回運算元堆疊 2019/2/23

步驟6: 因為”-”時，優先權等於Stack2的頂端運算子”+”，故取出”+”與 將剛才未存入堆疊的”-”存入運算子堆疊。 2019/2/23

步驟7:讀取”D” 2019/2/23

步驟8: 取出運算子“-”及運算元“A+B*C”及”D”進行計算， 結果存回運算元堆疊 2019/2/23

4-3.3 中序表示法轉換成前序表示法 由中序表示法轉換成前序表示法的方法有兩種： 1. 加括號去除法：這種方法是人類使用的方法，主要是應付於考試， 想快速得到前序表示法時使用。 2. 堆疊處理法：「由右而左」掃描資料，依據資料是運算元或運算子 作不同的處理，運算子還要考慮其優先次序。 2019/2/23

一、加括號去除法 例如：A+B*(C-D) 1.先用括號將優先順序分出來 (A+(B*(C-D))) 2.將運算子移到最接近且有括住此運算子的左括號右邊，則依優先順序為： (A+(*B(-CD))) (+A(*B(-CD))) 3.把括弧全部拿掉，即為所得。 +A*B-CD 2019/2/23

二、堆疊處理法 步驟1. 由右至左依序取得資料di(data item)。 步驟2. 如果di是運算元，則直接輸出。 (3)如果di不是“)”或“(”，則與堆疊頂點的運算子ds(data of stack)作優先順 序比較： 當di較ds優先時， 則di放入堆疊，迴圈輸出堆疊資料，直到優先次序相等。 當di不較ds優先或相等時，則ds輸出，di放入堆疊。 步驟4. 如果運算式已讀取完成，而堆疊中尚有運算子時，依序由頂端輸出。 步驟5. 反轉輸出的字串 2019/2/23

【實例】A+B*(C-D) (1)讀取：‘)’ > Stack頂端的運算子優先權 (2)讀取：’D’ 輸出：D 目前輸出的字串：D 2019/2/23

【實例】A+B*(C-D) (3)讀取：‘－’ > Stack頂端的運算子優先權 註：中序轉成前序時，右括號在堆疊中的優先順序最小， 亦即任何運算子都大於它的優先權。 2019/2/23

【實例】A+B*(C-D) (4)讀取：‘C’ 輸出：C 目前輸出的字串：DC (5)讀取：‘(’ 後，依序輸出(POP)堆疊中的運算子, 直到取出 “ ) ”為止 輸出：－ 目前輸出的字串：DC－ (註：左右括號不會輸出顯示) 2019/2/23

【實例】A+B*(C-D) (6)讀取：‘*’ > Stack頂端的運算子優先權 (7)讀取：’B’ 輸出：B 目前輸出的字串：DC－B 2019/2/23

【實例】A+B*(C-D) (8)讀取：‘+’< Stack頂端的運算子優先權，則先’*’輸出，’+’放入堆疊 輸出：* 目前輸出的字串：DC－B* (9)讀取：’A’ 輸出：A 目前輸出的字串：DC－B*A 2019/2/23

【實例】A+B*(C-D) (10)輸出剩餘的Stack中的資料(運算式已經讀取完成, 而堆疊中尚有運算子 時, 依序由頂端輸出) 輸出：+ 目前輸出的字串：DC－B*A+ (11)反轉輸出的字串：+A*B－CD 2019/2/23

【老師上課動態展示】檔案在附書光碟中。 2019/2/23

4-3.4 中序表示法轉換成後序表示法 由中序表示法轉換成後序表示法的方法有兩種： 4-3.4 中序表示法轉換成後序表示法 由中序表示法轉換成後序表示法的方法有兩種： 加括號去除法：這種方法是人類使用的方法，主要是應付於考試， 想快速得到後序表示法時使用。 2. 堆疊處理法：「由左而右」掃描資料，依據資料是運算元或運算子 作不同的處理，運算子還要考慮其優先次序。 2019/2/23

一、加括號去除法 例如：A+B*(C-D) 1.先用括號將優先順序分出來 (A+(B*(C-D))) 2.將運算子移到最接近且有括住此運算子的右括號左邊，則依優先順序為： (A+(B(CD-)*)) (A(B(CD-)*)+) 3.把括弧全部拿掉，即為所得。 ABCD-*+ 2019/2/23

二、堆疊處理法 步驟1. 由左至右依序取得資料di(data item)。 步驟2. 如果di是運算元, 則直接輸出。 (3)如果di不是 “(” 或 “)” , 則與堆疊頂點的運算子ds(data of stack)作優先 順序比較： 當di較ds優先時, 則di放入堆疊。 當di不較ds優先或相等時, 則ds輸出，di放入堆疊。 步驟4.如果運算式已經讀取完成, 而堆疊中尚有運算子時, 依序由頂端輸出。 2019/2/23

【實例】A+B*(C-D) (1) 讀取：’A’ 輸出：A 目前輸出的字串：A (2) 讀取：‘+’ > Stack頂端的運算子優先權 2019/2/23

【實例】A+B*(C-D) (3) 讀取：’B’ 輸出：B 目前輸出的字串：AB (4) 讀取：‘*’ > Stack頂端的運算子優先權 2019/2/23

【實例】A+B*(C-D) (5) 讀取：‘(’放到Stack中 (6) 讀取：’C’ 輸出：C 目前輸出的字串：ABC 2019/2/23

【實例】A+B*(C-D) (7) 讀取：‘－’> Stack頂端的運算子優先權 註：中序轉成後序時，左括號在堆疊中的優先順序最小， 亦即任何運算子都大於它的優先權。 2019/2/23

【實例】A+B*(C-D) (8) 讀取：’D’ 輸出：D 目前輸出的字串：ABCD (9) 讀取：‘ ) ’ 後，依序輸出(POP)堆疊中的運算子, 直到取出 “ ( ”為止 輸出：－ 目前輸出的字串：ABCD－ (註：左右括號不會輸出顯示) 2019/2/23

【實例】A+B*(C-D) (10)輸出剩餘的Stack中的資料(運算式已經讀取完成, 而堆疊中尚有運算子 時, 依序由頂端輸出) 輸出：*+ 最後輸出的字串：ABCD－*+ 2019/2/23

【老師上課動態展示】檔案在附書光碟中。 2019/2/23

4-3.5 前序表示法轉換成中序表示法 在上面介紹的方法是將「中序」轉換成「前序與後序」，但是如何將「前序」轉換成「中序」呢？我們一樣可以利用前面提到的「加括號去除法」與「堆疊法」來進行轉換。但是，轉換方式略有一點點不同，其說明如下。 2019/2/23

一、加括號去除法 以加括號去除法來求得前序式轉換成中序式的作法，若為前序時必須以「運算子+運算元」的方式括號。 【例如】請將前序式+A*B-CD，轉換成中序式。 【作法】 1. 依「運算子+運算元1+運算元2」的原則括號 ( + A ( * B ( - C D ) ) ) 2. 將左邊的運算子移到兩個運算元之中 ∴(A +( B *( C- D ) ) ) 3.拿掉未具優先權的括弧 A+B*(C-D) 2019/2/23

二、堆疊處理法 以堆疊法來處理前序轉換成中序時，必須要遵守以下的原則： 1.由右至左依序取得資料di 2.如果di是運算元，則放入堆疊中。 (<運算元2><運算子><運算元1>)後，再將結果放入堆疊中。如下圖所示： 2019/2/23

前序式+A*B－CD ，轉換成中序式 【作法】 1.由右而左依序取得資料di 2.如果di是運算元，則放入堆疊中。 2019/2/23

前序式+A*B－CD ，轉換成中序式 3.如果di是運算子，則從堆疊中取出兩個運算元，依照中序式的結合 方式(<運算元2><運算子><運算元1>)後，再將結果放入堆疊中。 2019/2/23

三、快速法(考試用) 前序式轉換成中序式時，必須要先找到「前序式的樣板(Prefix Pattern)」 規則： 前序式的樣板如下： 「前序式」的樣板：運算子 運算元1 運算元2 「中序式」的樣板：運算元1 運算子 運算元2 轉換 2019/2/23

【舉列】前序式為+A*B－CD ，請轉換為中序式。 2019/2/23

4-3.6 後序表示法轉換成中序表示法 在上面介紹的方法是將「中序」轉換成「前序與後序」，但是如何將「前序與後序」轉換成「中序」呢？我們一樣可以利用前面提到的「加括號去除法」與「堆疊法」來進行轉換。但是，轉換方式略有一點點不同，其說明如下。 2019/2/23

一、加括號去除法 以加括號去除法來求得前序式轉換成中序式的作法，若為後序時必須以「運算元+運算子」的方式括號。 【例如】請將後序式ABCD-*+，轉換成中序式。 【作法】 1. 依「運算元1+運算元2+運算子」的原則括號 ( A ( B ( C D - ) * ) + ) 2. 將右邊的運算子移到兩個運算元之中 ∴(A +( B *( C- D ) ) ) 3.拿掉未具優先權的括弧 A+B*(C-D) 2019/2/23

二、堆疊處理法 以堆疊法來處理後序轉換成中序時，必須要遵則以下的原則： 1.由左至右依序取得資料di。 2.如果di是運算元，則放入堆疊中。 2019/2/23

後序式ABCD-*+ ，轉換成中序式 【作法】 1.由左而右依序取得資料di 2.如果di是運算元，則放入堆疊中。 2019/2/23

後序式ABCD-*+ ，轉換成中序式 3.如果di是運算子，則從堆疊中取出兩個運算元，依照中序式的結合 方式(<運算元1><運算子><運算元2>)後，再將結果放入堆疊中。 2019/2/23

三、快速法(考試用) 後序式轉換成中序式時，必須要先找到「後序式的樣板(Postfix Pattern)」 規則： 後序式的樣板如下： 「後序式」的樣板：運算元1 運算元2 運算子 「中序式」的樣板：運算元1 運算子 運算元2 轉換 2019/2/23

【舉列】後序式為ABCD-*+，請轉換為中序式。 2019/2/23