資料結構 (Data Structures) Course 5: Stack and Queue 授課教師 : 陳士杰 國立聯合大學資訊管理學系
Outlines 本章重點 Stack 的定義 應用 製作與 ADT Queue 的定義 應用 製作與 ADT 如何利用 Array 與 Linked list 製作 Stack 與 Queue Infix( 中序 ) 運算式與 Postfix ( 後序 ), Prefix ( 前序 ) 運算式間之相互 轉換 Postfix 與 Prefix 的計算 (Evaluation) Stack Permutation 2
Stack ( 堆疊 ) Def: 具有 LIFO (last in-first out) 或 FILO (first in-last out) 性質的有序串列 插入元素的動作稱為 Push, 刪除元素的動作稱為 Pop. Push/Pop 的動作皆發生在同一端, 此端稱為 Top. 3
Stack 之 ADT Data Object Spec. A set of data item Top: 指出目前頂端元素所在 Size: 表 Stack 的大小 Operation Spec. Create(S) S 建立一個空的 Stack S, 傳回値為一個新的 Stack S, 傳回給 User 使用 Push(S, item) S 將資料 item 插入到 Stack S 中, 並成為 Top 端元素 If Stack full, 則無法執行 Pop(S) item, S 刪除 Stack S 的 Top 端元素 If Stack empty, 則無法執行 4
Top(S) item 傳回 Stack S 之 Top 端元素値, 但不刪除 If Stack empty, 則無法執行 IsFull(S) Boolean 判斷 S 是否為 full 若是, 則傳回 True; 否則傳回 False IsEmpty(S) Boolean 判斷 S 是否為 empty 若是, 則傳回 True; 否則傳回 False 5
練習範例 1 Pop(Push(S, item)) = S Top(Push(S, item)) = item IsEmpty(Create(S)) = True Pop(Create(s)) = Error ( 無法執行, 是空的 Stack) IsEmpty(Push(S, i)) = False 6
練習範例 2 有一空的 Stack, 實施下列動作後,Stack 的內容為何? Push (S, a), Push(S, b), Pop(S), Push(S,c), Push(S, d), Pop(S) Ans: 7
Stack 的排列組合問題 (Stack Permutation) 三個資料 a, b, c 依序 push 入 stack, 而過程中可插入 pop 動作, 則合法的排列組合有哪些? Sol: abc push a, pop, push b, pop, push c, pop acb push a, pop, push b, push c, pop, pop bac push a, push b, pop, pop, push c, pop bca push a, push b, pop, push c, pop, pop ( ) cab push a, push b, push c, pop,?? cba push a, push b, push c, pop, pop, pop 共有 5 種合法的排列組合!! 8
n 個資料執行 stack permutation, 其合法的排列組合個數 為多少? Sol: 1 2n n + 1 n Catalmnn Number Catalmnn Number 可用於表示 : n 個 nodes 所形成的不同二元樹個數 n 個 ( 與 ) 所形成的合法配對個數 n 個矩陣之所有可能相乘方式 ( 同 括號配對 的觀念 ) 9
Stack 之製作 有兩個方式 : 用 Linked List 用 Array Application Program 應用於 ADT Stack Queue Tree Graph 較基礎的 D.S. ( 層次較低 ) Array Linked List 怎麼實作? 當然, 我們也可以用 Stack 實作出 Queue, 或用 Queue 實作出 Stack, 但這是另一層次的問題了!! 10
用 Linked List 製作 Stack 要利用 linked list 實作 stack, 需要撰寫兩個不同的結構 (Structure): Head: 用以當作堆疊中的 Top, 以指出堆疊中頂端元素之所在 此 Head 結構內不一定要有存放資料之資料變數, 但一定要有一個指標一定要有一個指標以指 向堆疊的頂端元素 往後各節若無特別説明, 此 Head 結構皆僅有一個指標, 名為 Top Data Node: 用以存放欲置於堆疊中的資料 此節點的結構內至少要有至少要有一個指標一個指標與一個資料變數一個資料變數 指標用以指向下一個元 素, 資料變數用以存放堆疊的資料 11
Create(S) 主要作法 : 宣告 top 指標為 null 即可 : top = null ( 初値 ); top null S 12
Push(S,, item) 推入非空堆疊 pnew 推入空堆疊 pnew top 2 item top 2 item 1 1 top top null null 13
主要作法 : begin end New(t); // 跟系統要求記憶體空間以產生並置放一個新節點 pnew pnew data = item; // 把資料 item 塞到這個新節點 pnew 的 Data 欄位中 pnew link = top; 1 top = pnew; 2 特點 : 只要 Memory 有空間,O.S. 就允許 Linked Stack 去 Push 新資料!! 不用 像 Array 一樣, 要先檢查 Array 是否滿了 14
Pop(S) item top 2 讀出資料 top dltptr 1 item 4Ret(dltPtr) null 15
主要作法 : begin end if (top = null) Stack empty; else begin end; 1 dltptr= top; 2 item = top data; 3 top = dltptr link; 4 Ret(dltPtr); 16
Top(S) 主要作法 : begin if (top= null) success = false; else begin print(top data); success = true; end; return success; end 17
IsFull(S) 主要作法 : begin end if (memory available) else result = false; result = true; return result; 18
IsEmpty(S) 主要作法 : begin end if (top=null) else result = false; result = true; return result; 19
用 Array 製作 Stack 我們專注於以下的 Operation Spec. Create(S) S Push(S, item) S Pop(S) item, S Top(S) item IsFull(S) Boolean IsEmpty(S) Boolean 20
Create(S) 建立空的 Stack 只需做宣告即可 : S: Array[1 n] item // 宣告一個 Array int top = 0 // 設定一整數變數 top 且初値為 0 為了説明方便, 以下談論用 Array 製作 Stack 時, 均假設一維陣列的 起始位址是從 1 開始!! 這與實際撰寫 C++ 有所出入, 請特別注意 21
Push(S,, item) begin if top = n stack Full; else begin top = top + 1; //top 要先加 1 end end; S[top] = item; // 再將 item 置入 S item y x top top 22
Pop(S) begin if top = 0 stack empty; else begin item = S[top]; // 先將 item 叫出 end end; top = top - 1; // 再將 top 減 1 S item y x top top 23
Top(S) begin if top = 0 stack empty; else return S[top]; // 將 item 叫出 end 24
IsEmpty(S) begin if top = 0 return True; else return False; end 25
IsFull(S) begin if top = n return True; else return False; end 26
Stack Application Procedure Call/Recursive Call 之處理 Parsing ( 剖析 ) Reversing Data ( 反轉資料 ) 中序式 (Infix) 與前序式 (Prefix)/ 後序式 (Postfix) 間互轉 後序式的計算 27
Procedure Call/Recursive Call ( 副程式 / 遞迴呼叫 ) 28
Parsing ( 剖析 ) 編譯器 (Compiler) 將程式剖析成單獨的個體, 如 : 關鍵 字 名字 標誌 等, 以進行程式語法檢査 一般常見的程式問題是不對稱的括號 (Unmatched Parentheses ), 即是編譯器在剖析過程中, 藉由堆疊來做判斷 29
Reversing Data ( 反轉資料 ) 30
Infix 與 Prefix/Postfix 間互轉 數學運算的表示式可有下列三種 : Prefix ( 前序式 ): +ab Infix ( 中序式 ): a+b Postfix ( 後序式 ): ab+ 31
Infix ( 中序式 ): Def: 一般所使用的 Expression Format 格式 : Operand 1 ( 運算元 1) Operator ( 運算子 ) Operand 2 ( 運算元 2) 運算子的種類 : Binary: +, -,,, and, or, Unary: not 缺點 : 不利於 Compiler 對式子運算的處理 需要考慮運算子之間的優先權優先權 結合性 Compiler 可能需要來回多次 scan 才可以求算出結果 Ex: a + b * c (d - e) 32
結合性對, -, 有影響!! 左結合 : (5-3)-2 = 0 右結合 : 5-(3-2) = 4 33
Postfix ( 後序式 ): 格式 : Operand 1( 運算元 1) Operand 2( 運算元 2) Operator( 運算子 ) 優點 : Compiler 易於處理,scan 一次即可求得計算結果 在後序式的表示式當中, 已免除掉括號, 優先權與結合性結合性的考量 中序式轉後序式, 需要用到一個 Stack 的支援 34
Prefix ( 前序式 ): 格式 : Operator( 運算子 ) Operand 1( 運算元 1) Operand 2( 運算元 2) 優點 : Compiler 處理 Prefix 的計算,scan 一次即可求得結果 在前序式的表示式當中, 已免除掉括號, 優先權與結合性結合性的考量 但是在中序式轉前序式比較麻煩, 需要用到二個 Stack 的支援 還是傾向 使用 Postfix 35
中序式轉後序式 前序式之相關議題 : 中序式與後序式 / 前序式互轉的計算 (Evaluation) 中序式轉後序式 前序式 後序式 前序式轉中序式 中序式與後序式 / 前序式互轉的演算法 (Algorithm) 中序式轉後序式的演算法 後序式計算的演算法 36
中序式與後序式 / 前序式互轉的計算 中序式轉後序式 前序式 後序式 前序式轉中序式 37
中序式轉後序式 前序式 使用 括號法 : 中 後的歩驟 : 對於中序式, 先加上完整的括號配對 將運算子取代最近的右括號 刪除左括號, 予以輸出即可 中 前的歩驟 : 對於中序式, 先加上完整的括號配對 將運算子取代最近的左括號 刪除右括號, 予以輸出即可 38
一般常見的運算子之優先權與結合性 : 39
Ex: A+B C, 寫出其 postfix 及 prefix 中 後 : 加上完整的括號配對 ( 優先於 +): (A+(B C)) 將運算子取代最近的右括號 : (A+(B C)) (A (BC + 刪除左括號 : (A (BC + ABC + 中 前 : 加上完整的括號配對 ( 優先於 +): (A+(B C)) 將運算子取代最近的左括號 : (A+(B C)) +A BC)) 刪除右括號 : +A BC)) +A BC 40
Ex: A+B+C, 寫出其 postfix 及 prefix 中 後 : 加上完整的括號配對 ( 左結合 ): ((A+B)+C) 將運算子取代最近的右括號 : ((A+B)+C) ((AB+C+ 刪除左括號 : ((AB+C+ AB+C+ 中 前 : 加上完整的括號配對 ( 左結合 ): ((A+B)+C) 將運算子取代最近的左括號 : ((A+B)+C) ++ABC)) 刪除右括號 : ++ABC)) ++ABC 41
Ex: A B C, 寫出其 postfix 及 prefix 中 後 : 加上完整的括號配對 ( 右結合 ): (A (B C)) 將運算子取代最近的右括號 : (A (B C)) (A(BC 刪除左括號 : (A(BC ABC 中 前 : 加上完整的括號配對 ( 右結合 ): (A (B C)) 將運算子取代最近的左括號 : (A (B C)) A BC)) 刪除右括號 : A BC)) A BC 42
範例練習 Infix 轉 Postfix (A+B C)-C (D E) (Ans: A B C + C D E -) ~A and B or (C > E) and ~F ( ~ 表 not) (Ans: A ~ B and C E > or F ~ and) Infix 轉 Prefix A -B + C (D - E) (Ans: + A - B C - D E) -B + A 2-4 B - D E F (Ans: --+-B A2 4B D EF) 43
後序式 前序式轉中序式 Prefix Infix 運算子 運算元 1 運算元 2 運算元 1 運算子 運算元 2 Postfix Infix 運算元 1 運算元 2 運算子 運算元 1 運算子 運算元 2 44
Sol: Postfix: AB+D EFAD + +C+, 則其 infix 為何? A B + D E F A D + + C + (( ((A+B) D) + (E (F+ (A D)))) +C) ( A + B ) D + E ( F + A D ) + C Hint: 哪個括號能拿掉, 哪個不能拿掉, 自已要會判斷!!! 45
Sol: Prefix: +-AB CD-EF, 則其 infix 為何? + - A B C D E F ( (A-B) - ((C D) (E-F) )) A - B + C D (E - F) Hint: 哪個括號能拿掉, 哪個不能拿掉, 自已要會判斷!!! 46
Sol: Postfix: AB- CD +, 則其 infix 為何? A B - C D + A B - C D + (( A (-B) ) + (C D)) Hint: 哪個括號能拿掉, 哪個不能拿掉, 自已要會判斷!!! 47
範例練習 Postfix: 6 2 3 4 5 + 之値為何? Ans: 9 Postfix: 2 5 3 2 5 - + 5 3 - 之値為何? Ans: -13 Postfix: 1 2 3 4 5 6 7 8 + 之値為何? Ans: -14.75 Postfix: a b c d e + a c -, 則其 Prefix 為何? Ans: - + - a b c d e a c Prefix: + + + a b c + d e f + g h, 則其 Postfix 為何? Ans: a b + c d e + + f + g h + 48
中序式與後序式 / 前序式互轉的演算法 需要堆疊 (Stack) 支援 討論次序 : Infix 轉 Postfix 的演算法 ( 利用 1 個 Stack) Postfix 之計算的演算法 Infix 轉 Prefix 的演算法 ( 利用 2 個 Stack) Prefix 之計算的演算法 49
演算法意義匯整 : Infix 轉 Postfix 的演算法 ( 利用 1 個 Stack) 1. 中序運算式由左往右由左往右掃描, 當遇到 : 1-1. 1. 運算元 : 直接輸出 ( 或 Print) 到後序式 1-2. 運算子 : 1-2-1. 1. ) : pop 堆疊內的運算子直到遇到 ( 1-2-2. 2. 其它運算子 x: 比大小 1. 若運算子 x 的優先權 > 堆疊內最 Top 的運算子時, 則將運算子 x push 至堆疊中 2. 若運算子 x 的優先權 堆疊內最 Top 的運算子時, 則 pop 堆疊內的運算子直到 x > 堆疊內最 Top 的運算子為止 2. 掃描完中序運算式, 則將堆疊內的殘餘資料 pop 完 Note: Stack 為空時, 其優先權最低 ( Stack 沒有任何運算子可與待輸入的運算子 做比較!!) ( 在 Stack 外優先權最高, 但在 Stack 內優先權最低 50
寫出 Infix: A+B (C (C-D E)+F 轉 Postfix 的過程 1) Print A 2) + > 空的 Stack push + 3) Print B 4) > + ( 堆疊的 top 元素 ) push 5) ( > push ( 6) Print C 7) - > ( (on stack) push - 8) Print D 9) > - push 10) Print E 11) ) pop stack until ( 1) Pop, print 2) Pop -, print 3) Pop (, 不用 print Ans: 12) + pop, print 13) + + pop +, print 14) + > 空的 Stack push + 15) Print F 16) Scan 完畢, 清空 Stack pop + A BC D E - + F + - ( + 51
在執行上述轉換過程中, 所需之 Stack Size 至少需要 5 個 儲存空間 52
while (Infix 尚未 Scan 完畢 ) do // 意義匯整 1. begin x = NextToken; //Token 是指運算的單元, 可能是運算元或是運算子 if (x 是 operand) // 意義匯整 1-1. 1. print(x); else begin // 意義匯整 1-2. if (x 是 ) ) // 意義匯整 1-2-1. 1. begin pop(s), 直到遇見 ( 為止 ; end; else begin // 意義匯整 1-2-2. 2. 比較 (x 與 stack top 之優先權 ) -case x > top : 則 push(x, S); -case x top : 則 pop(s), 直到 x > top 為止, 再 push(x, S); end; end; while (stack empty) do // 意義匯整 2. pop stack; 53
Postfix 之計算的演算法 43-15 +, 寫出 postfix 計算過程 ( 含 Stack 內容 ) Stack 容量需至少為多少? 3 1)Push 4 2)Push 3 3) - : 1)pop 3 與 4 2) 計算 4-3 = 1, 再 push 1 4)Push 1 5)Push 5 6) : 1)pop 5 與 1 2) 計算 1 5 = 5, 再 push 5 7) + : 1)pop 5 與 1 2) 計算 1 + 5 = 6, 再 push 6 8)Scan 完畢,pop stack 6 5 35 1 Ans: 6 64 1 54
while (Infix 尚未 Scan 完畢 ) do begin end; x = NextToken; //Token 是指運算的單元, 可能是運算元或是運算子 if (x 是 operand) else push(x); begin end; pop 適當數目的運算元 - 計算 pop stack; - 再將計算結果 push 回 stack // 即為結果 55
範例練習 Postfix: 526 +42 3 - 之求算過程 ( 含 Stack 內容 ), 且 Stack Size 最少需為多少? 結果 = 11,Stack Size 3 在求算 Postfix: AB C-DE +AC - 時,Stack Size 最少需 為多少? Stack Size 3 56
Queue ( 佇列 ) Def: 具有 FIFO (First-in, First-out) 性質的有序串列 插入與刪除元素的動作發生在佇列的不同端 插入動作發生在尾端 (Rear) 刪除動作發生在前端 (Front) 57
Queue Example 有一空的 queue, 實施下列動作後, 則 Queue 的內容為何? add(q, a), add(q, b), delete, add(q, c), delete, add(q, e) Ans: 58
Queue 的應用 日常生活的排隊行為 在作業系統中的 job scheduling, 在相同的 priority 下, 利用 queue 來完成先到先作的策略 有許多的 I/O 工作同時要處理 將所有的 I/O 要求, 利用 queue 來達成先到先作的策略 用於模擬 (Simulation) 方面, 如佇列理論 (Queuing Theory) The two factors that most affect the performance of queues are the arrival rate and the service time. 59
Queue 的 ADT Data Objects: Queue: a set of data items Front: 指示 Queue 之前端元素所在 Rear: 指示 Queue 之尾端元素所在 Operations: Create(Q): 建立空佇列 Q ADDQ(Q, item) Q: 將 item 插入到 Queue Q 中, 成為新的尾端元素 (if Queue is full, then 無法執行 ) DeleteQ(Q, item) item, Q: 刪除 Queue 中的前端元素 (if Queue is empty, then 無法執行 ) IsEmpty(Q) Boolean IsFull(Q) Boolean Front(Q) item: 傳回 Queue 之 Front 端元素 ( 但不刪除 ) 60
Queue 的製作 用 Link list 製作 Single link list 用 Array 製作 利用 Linear Array 利用 Circular Array with (n-1) space used 利用 Circular Array with n space used 61
用 Linked list 製作 Create(Q) 宣告 : rear: pointer = nil front: pointer = nil 62
ADDQ(Q, item) // 為說明方便起見, 下列的 F = front, R = rear Case 1: ( 當 Queue 為空佇列 ) nil F R Case 2: ( 當 Queue 不為空佇列 ) F newptr item F R R nil nil newptr item R nil 63
//F = front, R = rear begin New(newPtr); newptr data = item; newptr link = nil; if (rear = nil) then //Case 1 front = newptr; else // Case 2 rear link = newptr; rear = newptr; end 64
Delete(Q) deleteloc F item Ret begin if (front = nil) then Queue Empty; else begin deleteloc = front; item = front data data; front = front link link; Ret(deleteLoc); if (front = nil) then rear = nil; end end; F R deleteloc nil 假設 Queue 中只有一個 node,, 回收後把 Rear 指向 nil. 主要是耽心系統不會自動將 Rear 設成 nil,, 使得 Rear 指標無效!!??? R F item Ret F nil 65
用 Array 製作 利用 Linear Array 利用 Circular Array with (n-1) space used 利用 Circular Array with n space used 66
Create(Q) 宣告 : 利用 Linear Array Q: array[0 n-1] of items // 宣告 Q 是一個大小為 n 的一維 Array Front: integer = -1 // 初値 Rear: integer = -1 // 初値 AddQ(Q, item) Queue begin if (rear = n) then QueueFull; else begin end end. rear = rear +1 Q[rear] = item 67
DeleteQ(Q) item, Queue begin if (rear = front) then QueueEmpty; else begin end end. front = front +1 item = Q[front] 問題 : 當 rear = n 時,Queue 並不代表真正為滿的情況! 68
為解決上述問題, 我們或許可以設計一個副程式, 當資料 已成長到 Arrar 的最末端時, 作一次 是否真的為滿 的判 斷 ( 即 :Rear = n 且 Front = 0) 0 若不為真滿, 則需將 (Front+1) 到 Rear 端的所有元素往左移 Front 格, 並重設 Rear 與 Front 的指標値 然而, 此種作法會導致 Queue 之 Add 動作時間為 O(n) 是用廻圈廻圈來實作資料的搬移, 花費時間太大 同時, 此搬移工作 是額外的處理項目, 與 Add 動作本身是無關的 當 Add 的工作很頻繁時, 整體執行效益差 69
利用 Circular Array with (n-1) space used Create(Q) 宣告 : Q: Array[0 n-1] front = rear = 0 // 初値 R 0 1 2 n-1 R = (R+1) mod n AddQ(item, Q) Queue begin end; rear = (rear+1) mod n; n //rear 指標先前進 if rear = front else QueueFull; // 表示 Queue 滿了 rear = rear-1 mod n; // 將 rear 重設回前一格 Q[rear]=item; 70
DeleteQ(Q) item begin if front=rear // 先檢查 X X QueueEmpty; X X else begin X X front = (front+1) mod n; item = Q[front]; X X end; X X end; R X X F 特點 : 最多只利用到 n-1 格空間若硬要使用到 n 格空間, 則 rear = front 條件成立時, 無法真正區分出 Queue 為 Full 或 Empty 判斷 Full 與 Empty 的條件式相同 ( 皆為 rear = Full) Add 與 Delete 之動作時間皆為 O(1) 沒有資料挪移的動作!! 71
利用 Circular Array with n space used 引進一個 Tag 變數, 用以協助判斷 Queue 為 Empty 或 Full: 該變數為 Boolean 型態 若 Tag = True: 則可協助判斷是否為 Full 若 Tag = False: 則可協助判斷是否為 Null 不是光靠 Tag 就能做正確判斷!! 72
Create(Q) 宣告 : Q: Array[0 n-1] front = rear: int = 0 // 初値 Tag: Boolean = 0 // 初値 AddQ(item, Q) Queue begin if (rear = front and Tag = 1) QueueFull; else begin rear = (rear+1) mod n; //rear 指標前進 Q[rear]=item; if (rear=front) Tag=1; end; end; 73
DeleteQ(Q) item begin if (Front=Rear and Tag=0) QueueEmpty; else begin Front = (Front+1) mod n; item = Q[Front]; if (Front=Rear) Tag=0; end; end; 特點 : 最多可利用到 n 格空間 Add 與 Delete 之運作時間稍長 多了一條 if 測試, 來測試 Tag 値設定, 且此兩個運作使用上極頻繁 整體時間效益稍嫌 Poor!! X X R F X X X X X X X X X X 74
Queue 的種類 FIFO Queue ( 先進先出佇列 ) Priority Queue ( 優先權佇列 ) Double Ended Queue ( 雙邊佇列 ) Double Ended Priority Queue ( 雙邊優先佇列 ) 75
FIFO Queue ( 先進先出佇列 ) 即一般的佇列, 具有 FIFO 特性, 前端刪除元素, 尾端加入元素 Priority Queue ( 優先權佇列 ) Double Ended Queue ( 雙邊佇列 ) Double Ended Priority Queue ( 雙邊優先佇列 ) 76
FIFO Queue ( 先進先出佇列 ) Priority Queue ( 優先權佇列 ) 不一定遵守 FIFO 特性 運作 : 插入任意優先權値之元素 刪除時, 是刪除具最大 / 最小優先權値之元素 可利用 Heap ( 堆積 ) 來製作 Double Ended Queue ( 雙邊佇列 ) Double Ended Priority Queue ( 雙邊優先佇列 ) 77
FIFO Queue ( 先進先出佇列 ) Priority Queue ( 優先權佇列 ) Double Ended Queue ( 雙邊佇列 ) 可於任何一端執行插入 / 刪除元素的動作 亦可實作成 : Input-restricted: 插入動作在固定端, 刪除動作在任意端 Output-restricted: 插入動作在任意端, 刪除動作在固定端 Double Ended Priority Queue ( 雙邊優先佇列 ) 78
FIFO Queue ( 先進先出佇列 ) Priority Queue ( 優先權佇列 ) Double Ended Queue ( 雙邊佇列 ) Double Ended Priority Queue ( 雙邊優先佇列 ) 可於任何一端執行插入元素的動作 但刪除時, 有一端是做 Delete Max 元素的動作, 另一端則作 Delete Min 元素的動作 可利用 Min-Max Heap ( 堆積 ) 來製作 79
補充 80
Prefix 之計算 觀念同 Postfix 的計算過程, 都是利用一個 Stack 差別 : 由右往左 Scan Operand 在 pop 之後的計算位置相反 81
計算 - +123 84 1) Push 4 2) Push 8 3) : 1) pop 8 與 4 2) 計算 8 4 = 2, 再 push 2 4) Push 3 5) Push 2 6) Push 1 7) + : 1) pop 1 與 2 2) 計算 1 + 2 = 3, 再 push 3 8) : 9) - : 1) pop 3 與 3 2) 計算 3 3 = 9, 再 push 9 1) pop 9 與 2 2) 計算 9-2 = 7, 再 push 7 10) Scan 完畢,pop stack 7 1 23 83 9 Ans: 7 42 7 82
Infix 轉 Prefix 之演算法 大原則 : Infix 由右往左 Scan 需要 2 個 Stacks 支援 83
1) push C 至 Temp Stack 2) > 空的 Stack S push 寫出 Infix: A+B C 轉 Prefix 的過程 3) push B 至 Temp Stack + 4) + ( 堆疊的 top 元素 ) 1) pop push into Temp Stack 2) Push + into stack S 5) push A 至 Temp Stack + S A B C Temp 6) Scan 完畢, 清空 Stack S pop + and push into Temp Stack Ans: + A B C 7) Pop Temp Stack 內所有資料 84
上述過程若沒有 Temp Stack 會發生何事? 1) print C 2) > 空的 Stack S push 3) print B 4) + ( 堆疊的 top 元素 ) 1) pop print 2) Push + into stack S 5) print A + S 6) Scan 完畢, 清空 Stack S pop + and print it 由此可知,Temp Stack 扮演 反 Ans: C B A + 向輸出 的角色 85