第三章 堆疊與佇列 Stacks & Queues A farmer learns more from a bad harvest than a good one.

練功前的沉思 Q1:What is stack? Q2:What is queue? Q3:What is circular queue? Q3:How to implement stack using C? Q4:How to implement Queue using C? Q5:When do we apply stack and queue to solve problems? 李麗華--資料結構講義

WHAT IS STACK? Def: A stack, S, is a finite ordered list in which the operation of inserting and deleting of an item is done in only one side of the list. Characteristics: 1. Last In First Out(LIFO) 2. Last Come First Serve(LCFS) 3. In and out in only one end 4. Push and Pop operation Top S I S I H T Bottom 例: 要加入6個字元 T, H, I, S, I, S 到Stack S 李麗華--資料結構講義

Inserting and deleting items into a stack B A D C E top Bottom Initial List Insert A then B Insert C Insert D Insert E Delete E 動動手:設有一長度為4的stack,請試著依下面順序模擬: (1) PUSH A,B,C (2) POP, POP (3) PUSH D,E,F (4) PUSH G, (6) POP, POP, POP, POP, POP 李麗華--資料結構講義

Push & Pop Stack using C void push(int S[], int MAX, int top) { if (top >= MAX-1) printf(“\n Stack is FULL !! \n”) ; else { top++; printf(“\n Enter a number to be inserted:“); scanf(“%d”, &S[top]); } void pop(int S[], int top) { if (top < 0) printf(“\n Stack is Empty !! \n”) ; else printf(“\n Item %d is deleted“, S[top]); top-- ; } 李麗華--資料結構講義

WHAT IS QUEUE? Def: A Queue, Q, is a finite ordered list in which the operation of inserting and deleting of an item is done in different side of the list. Characteristics: 1. First In First Out(FIFO) 2. First Come First Serve(FCFS) 3. Two ends are used rare S I H T front 例: 要加入4個字元 T, H, I, S 到Queue Q 李麗華--資料結構講義

Inserting and deleting items into a Queue Let f = front pointer & r = rare pointer r B A D C E f Initial List Insert A then B Insert C Insert D Delete A Delete B Insert E 動動手:設有一長度為5的Queue,請試著依下面順序模擬: (1) Insert A,B,C (2) Delete, Delete (3) Insert D,E (4) Delete, Delete, (6) Insert F, (7) Delete, Delete 李麗華--資料結構講義

Insert & Delete in Queue using C void in_q(int Q[], int MAX, int r) { if (r >= MAX-1) printf(“\n Queue is FULL !! \n”) ; else { r++; printf(“\n Enter a number to be inserted:“); scanf(“%d”, &Q[r]); } void de_q(int Q[], int f, int r) { if ( f > r ) printf(“\n Queue is Empty!! \n”) ; else printf(“\n Item %d is deleted“, Q[f]); f++ ; } What is the problem for queue structure? 李麗華--資料結構講義

Circular Queue (CQ) front: one position clockwise from the first element rear : current end [2] [1] [2] [1] B A [3] [0] [3] C [0] ... [n-2] [n-1] [4] [5] Empty Circular Queue The initial value f=0, r=0 After insert A, B, C then f= 0, r = 3 李麗華--資料結構講義

Insert & Delete in CQ using C void in_cq(int CQ[], int MAX, int r) { r = (r+1) % MAX; if ( f == r ) { printf(“\n Queue is FULL !! \n”) ; if ( r == 0 ) r = MAX - 1; else r = r - 1; } else { printf(“\n Enter a number to be inserted:“); scanf(“%d”, &CQ[r]); void de_cq(int CQ[], int f, int r) { if ( f == r ) printf(“\n Queue is Empty!! \n”) ; else { f = (f+1) % MAX; printf(“\n Item %d is deleted“, CQ[f]); } 動動手: 設一個長度為5的CQ,請依 下列順序模擬(1)Insert A,B,C,D (2)Del, Del (3)Insert E,F,G (4)Del,Del (5)Insert H,I 李麗華--資料結構講義

Application--Prefix, Infix, Postfix 堆疊有許多可應用的地方,在程式編譯時就常會利用堆疊將中序運算式轉成後序運算式,編譯後電腦(CPU)可迅速的將運算元(Operand)與運算子(Operator)取出並運算. 中序式(Infix):即一般我們熟知的運算式表示法, 如: A + B * C (運算子即 +, *, 而運算元即A,B,C) 後序式(Postfix):主要是將運算子放在欲運 算的運算元之後, 如: A B C * + 前序式(Prefix) : 主要是將運算子放在欲運 算的運算元之前, 如: +A *B C 李麗華--資料結構講義

From Infix to Postfix The process steps are: (ex: A*B/C-D ) 1. Properly add parenthesis,i.e., (), into the expression with correct priority.  (((A*B)/C)-D) 2. Move all the operator to the right  ((AB)*C)/D)- 3. Delete all the ()  AB*C/D- 李麗華--資料結構講義

The Priority of Operator 動動腦 & 動動手 將下列infix轉postfix A+B*C/D*F A-B/C+D*E-F%G C/(A*B)+(B+C)*D A+(-B)-C*(-D) Operator Priority ---------------- --------- +, -, ! 6 *, /, % 5 +, - 4 <, <=, >, >= 3 && 2 || 1 高 低 李麗華--資料結構講義

Using Stack: From Infix to Postfix example: A*B/C-D (將運算子push到stack中) Get / Pop * Push / Get - Pop / Push - Initial Stack Get A Get B Get C Get D Pop all Get * push * * / / - - 輸出 結果 A A AB AB* AB*C AB*C/ AB*C/D AB*C/D- 李麗華--資料結構講義

The process from infix to postfix (1) 依序讀入中序式的一個字元 (2) 若此字元為空(表中序式己讀完), --> 則pop所有運算子在stack內,並輸出 --> stop 否則若此字元為運算元(即變數像A,B,C,D...) -->則直接輸出 否則若此字元為運算子(即+,-,*,/,%,|...) -->則若stack內的運算子priority較大則 pop並輸出 -->否則push此運算子到stack (3) Go To 步驟 (1) 特例: 遇見左括號“(”, 無論如何定要push到stack內,直到遇見右括號“)”, 遇見右括號後則要pop運算子直到遇見左括號“(”止. 李麗華--資料結構講義

Another example: Infix to Pretfix 步驟 1 2 3 4 5 6 7 8 9 10 11 12 13 讀入字元 A - B * ( C + D ) / E 輸入過程 AB ABC ABCD ABCD+ ABCD +* ABCD+*E ABCD+*E/ ABCD+*E/- 堆疊內容 空 - * - *( - *( + - / 範例: A-B*(C+D)/E 動動手: -(A+B)*(C+D) A&&(B<C)||(D>B) 李麗華--資料結構講義

Application: CUP computes 電腦裡的運算式, 其實是CPU利用postfix式子, 加上運用暫存器來做堆疊,算出最後的值. 例: 用之前的postfix ABCD+*E/- 令: A=99, B=7, C=3, D=5, E=4 步驟 1 2 3 4 5 6 7 8 9 讀入字元 A B C D + * E / - 堆疊內容 A, B A, B, C A, B, C, D A, B, 8 A, 56 A, 56, E A, 14 85 李麗華--資料結構講義

大師—該動動腦囉!! 第三章習題請解答下列並以紙本繳交: 第1題的(1)~(9)小題, 其中第(5),(6)小題, 請畫出stack內的運算子被push與pop的經過. 請implement一個程式: (1)中序式轉成後序式: 你的程式應該要求user輸入中序式(不含空格), 程式應設最多可讀入3~20個字元的中序式(以“#”字元做結束)後, 將轉好的後序式輸出到螢幕, (2)本程式接著再詢問user各個變數(應為大寫字母)的值, 利用己做好的後序式, 將運算後的值求出, 並輸出到螢幕上. 請交執行檔與原始檔, 檔名為: 學號-2.exe, 例: 9054007-2.exe) 回家動動腦 上課來發表 你還知道Stack 與 Queue 可以用在哪些生活面或實務面的哪些應用領域上? 請舉例說明. 李麗華--資料結構講義

Failure is the only opportunity to begin more intelligently. 唯有經歷失敗才能開啟智慧 --Henry Ford 李麗華--資料結構講義