先前章节讨论过的结构和演算法与本章即将要讨论的课件

1、Chapter 4 Stacks and QueuesJames Chen2005/10/241Chapter 4 Stacks and QueuesJamOutlinesSome Different kinds of StructuresStacksReverse StringDelimiter matchingQueuesPriority QueuesParsing Arithmetic Expressionsinfix postfix expression2OutlinesSome Different kinds oDifferent Structures先前章節討論過的資料結構和演算法

2、與本章即將要討論的資料結構和演算法有著極為明顯的差異。有三點主要差異:真實世界的資料 v.s. 程式設計師的工具Array 對應到現實資料Stack/Queue 程式內部使用限制存取的機制無法使用 index 直接存取.必須借由Interfaces 存取.一次只能存取一筆資料(最上面 or 最前面).更抽象化的概念使用這些資料結構的程式不需要知道實作細節.實際的儲存機制也不須擔心! ( Array or Linked-List or Heap )3Different Structures先前章節討論過的資料郵件之堆積處理方式:由上而下(Top-to-Bottom)逐一處理 Stack由最久的開

3、始處理. Queue重新攪亂,並依重要性重新排列. Priority Queue4郵件之堆積處理方式:4Stacks (堆疊)說明推入(Push), 拋出(Pop) 和取值(Peek) 只能存取最近推入(Push)的資料(最上面).若要存取其他資料, 必須先移出最上面的資料.LIFO Last In First Out有頂端 (Top) 一個紀錄變數應用檢查原始程式中的成對的括號 評估數學運算式(Arithmetic Expression)的值.程式執行過程: 副程式之呼叫與返回5Stacks (堆疊)說明5Stack Applet6Stack Applet6Stack 原始程式 架構關係St

4、ackX int maxSize; double stackArray; int top;+ StackX(int s)+ push(double j) : void+ pop() : double+ peek() : double+ isEmpty() : boolean+ isFull() : booleanStackAppmain( String )7Stack 原始程式 架構關係StackX int maxSStack 程式碼 part 1public StackX(int s) / constructormaxSize = s; / set array sizestackArray

5、= new doublemaxSize; / create arraytop = -1; / no items yet8Stack 程式碼 part 1public StackStack 程式碼 part 2public void push(double j) / put item on top of stackstackArray+top = j; / increment top, insert itempublic double pop() / take item from top of stackreturn stackArraytop-; / access item, decremen

6、t top9Stack 程式碼 part 2public void Stack 程式碼 part 3public double peek() / peek at top of stackreturn stackArraytop;public boolean isEmpty() / true if stack is emptyreturn (top = -1);public boolean isFull() / true if stack is fullreturn (top = maxSize-1);10Stack 程式碼 part 3public doublStackApp 程式碼class

7、 StackApppublic static void main(String args)StackX theStack = new StackX(10); / make new stacktheStack.push(20); / push items onto stacktheStack.push(40);theStack.push(60);theStack.push(80);while( !theStack.isEmpty() ) / until its empty, / delete item from stackdouble value = theStack.pop();System.

8、out.print(value); / display itSystem.out.print( ); / end whileSystem.out.println(); / end main() / end class StackApp11StackApp 程式碼class StackApp11push(49)Stack 程式 圖示法pop(); pop()12push(49)Stack 程式 圖示法pop(); pError Handling現有版本之問題使用者必須負責檢查! isEmpty() and isFull()Homework2 : 將StackX/Queue錯誤例外的處理加入 St

9、ackX/Queue 之內, 讓使用者不須擔心此問題! 修改 push()/insert() , pop()/remove() and peek()/peekFront() method.13Error Handling現有版本之問題13Example of Stack : 倒轉字母StackX int maxSize; double stackArray; int top;+ StackX(int s)+ push(double j) : void+ pop() : double+ peek() : double+ isEmpty() : boolean+ isFull() : boolea

10、nReverser String input;- String output;+ Reverser(String in)+ doRev() : StringReverseAppmain ( String arg) 14Example of Stack : 倒轉字母StackX Example of Stack : doRev()public String doRev() / reverse the stringint stackSize = input.length(); / get max stack sizeStackX theStack = new StackX(stackSize);

11、/ make stackfor(int j=0; jinput.length(); j+) char ch = input.charAt(j); / get a char from inputtheStack.push(ch); / push itoutput = ;while( ! theStack.isEmpty() ) char ch = theStack.pop(); / pop a char,output = output + ch; / append to outputreturn output; / end doRev()15Example of Stack : doRev()p

12、ublExample of Stack : 分隔符號之配對- Delimiter Matching堆疊之應用之一: Parse (解析) 特定字串之內容是否符合語法規範cd / correctabcde / correctab(cde / not correct; doesnt match (abcde / not correct; nothing matches final ab(c) / not correct; Nothing matches opening 16Example of Stack : 分隔符號之配對- DDelimiter Matching 之觀念Example : a

13、b ( c d e ) f a b ( c d ) e f 17Delimiter Matching 之觀念Example Delimiter Matching 之相關作法DelimiterOpening Delimiter , , (Closing Delimiter , , )作法:逐一讀取字元遇到Opening Delimiter就放進 stack遇到 Closing Delimiter 就從 stack pop 出來一個opening delimiter;若 stack 沒有 Opening Delimiter 可供讀取, 則表示有誤!並比較是否是同一類 delimiter, 若不同類

14、就是有誤!若無資料可供輸入而 Stack 是 empty, 就表示原式是正確無誤, 否則就有誤!18Delimiter Matching 之相關作法DelimiDelimiter Matching 程式架構- bracket.javaStackX int maxSize; double stackArray; int top;+ StackX(int s)+ push(double j) : void+ pop() : double+ peek() : double+ isEmpty() : boolean+ isFull() : booleanBracketChecker String in

15、put;+ BracketChecker(String in)+ check() : voidBracketApp+ main ( String )19Delimiter Matching 程式架構- bracDelimiter Matching 程式架構- check() method part 1public void check()int stackSize = input.length(); / get max stack sizeStackX theStack = new StackX(stackSize); / make stackfor (int j=0; j= front) /

16、 contiguous sequencereturn rear-front+1;else / broken sequencereturn (maxSize-front) + (rear+1);34New Queue 程式碼 part 3public bEfficiency of Queuesinsert() : O(1)remove() : O(1)peek() : O(1)35Efficiency of Queuesinsert() :Deques : double-ended queue- 同時擁有 stack 與 queue 的特性 !可以從 front 或 rear 進行插入或刪除資料

17、的動作.insertLeft() and insertRight(), and removeLeft() and removeRight()應用insertLeft() + removeLeft() StackinsertLeft() + removeRight() Queue36Deques : double-ended queue- Priority Queues (優先佇列)佇列中的資料是依照優先等級來排列:具有最高優先權者排在front， 以便即時被處理!具有相同優先權的依照FIFO排列!優先佇列也是程式設計的工具之一。OS 的作業排程37Priority Queues (優先佇列)佇

18、列中的資料是依Priority Queue 之實作一般仍和Queue相同, 會有 front 和 rear但是通常我們需要仍夠較快速的取得最高優先(鍵值最小or最大)的資料進行處理. 也希望能夠快速的插入新的資料.使用 heap (MaxHeap, MinHeap) 的資料結構來實作儲存空間本章使用 Array 實作, 但是效率就差很多 !讀取(移除)的速度很快! (Why)插入的速度很慢 ! (Why)38Priority Queue 之實作一般仍和Queue相同,PriorityQ Applet- Front/Rear 作法和原有 Queue 不同 !39PriorityQ Applet-

19、 Front/Rear Some Approach for Implementation 使用有排序的方式利用 Array 實作 (常用)讀取(移除)的速度很快! (Why)插入的速度很慢 ! (Why)使用隨意的方式利用 Array 實作讀取(移除)的速度很慢! (Why)插入的速度很快! (Why)40Some Approach for ImplementatiPriorityQ 示意圖insert(6)remove() ; remove()41PriorityQ 示意圖insert(6)remove()Priority Queue 程式架構PriorityQ int maxSize; d

20、ouble queArray; int nItems;+ Queue(int s)+ insert(double j) : void+ remove() : double+ peekMin() : double+ size() : int+ isEmpty() : boolean+ isFull() : booleanPriorityQAppmain( String )42Priority Queue 程式架構PriorityQ iPriority Queue 程式碼 part 1public PriorityQ(int s) / constructormaxSize = s;queArray

21、 = new doublemaxSize;nItems = 0;43Priority Queue 程式碼 part 1pubPriority Queue 程式碼 part 2public void insert(double item) / insert itemint j;if (nItems=0) / if no items,queArraynItems+ = item; / insert at 0else / if any items,for (j=nItems-1; j=0; j-) / start at end, if ( item queArrayj ) / if new item

22、 larger, queArrayj+1 = queArrayj; / shift upward else / if smaller, break; / done shifting / end forqueArrayj+1 = item; / insert itnItems+; / end else (nItems 0) / end insert()44Priority Queue 程式碼 part 2pubPriority Queue 程式碼 part 3public double remove() / remove minimum item return queArray-nItems;

23、public double peekMin() / peek at minimum item return queArraynItems-1; public boolean isEmpty() / true if queue is empty return (nItems=0); public boolean isFull() / true if queue is full return (nItems = maxSize); 45Priority Queue 程式碼 part 3pubPriorityQApp 程式碼class PriorityQApppublic static void m

24、ain(String args) throws IOException PriorityQ thePQ = new PriorityQ(5);thePQ.insert(30);thePQ.insert(50);thePQ.insert(10);thePQ.insert(40);thePQ.insert(20);while( !thePQ.isEmpty() ) double item = thePQ.remove(); System.out.print(item + ); / 10, 20, 30, 40, 50 / end whileSystem.out.println(); / end m

25、ain()/- / end class PriorityQApp46PriorityQApp 程式碼class PriorityEfficiency of Priority Queues現有效能insert() : O(N)remove() : O(1)改進方案改以 heap 實作!47Efficiency of Priority Queues現Parsing Arithmetic Expressions統一更正英中譯名 (pp. 137 161) : infix : 插入 中序postfix : 字尾 後序prefix : 字首 前序expression :表達(法) 運算式postfix

26、notation : 字尾(的)界限 後序表示式 infix notation : 插入界限 中序表示式prefix notation : 字首(的)界限 前序表示式 postfix expression : 字尾表達法 後序運算式operator : 運算元 運算子operand : 運算子 運算元48Parsing Arithmetic ExpressionsExpression (運算式)Expression (運算式)由運算子(Operator)與運算元(Operand)構成的式子運算子: + - * / % 運算元: 1 2 6 7 i j sum salaryEx: i *2 +

27、j*salary ( i + j ) * 5 + 749Expression (運算式)Expression (運算Parsing Arithmetic ExpressionsExamples: 3 + 5 7 1 3 + 5 * 7 38 3 * ( 5+7) 36 對人而言，很容易就算出其值 !但利用電腦，要直接利用演算法去寫出解析程式是有點挑戰!利用電腦評估值的作法: two-phases先將來的數學運算式轉成後序表示法 ( postfix notation )評估後序表示式的值PS: 兩個步驟都要用到 stack !50Parsing Arithmetic ExpressionsInf

28、ix 與 Postfix Notation (中序與後序表示式)51Infix 與 Postfix Notation (中序與後為何要將 Infix 轉成 Postfix主要原因Infix ：給人看的，一般程式內的寫法。Postfix ：給電腦看的，方便評估運算式之值!52為何要將 Infix 轉成 Postfix主要原因52中序表示式的評估規則中序表示式的評估值，一般都是由左而右的進行評估與替換，但是遇到不同等級的運算子，就要特別注意評估之先後次序。運算子搭配適當數量的運算元即可評估其值Ex: 3 + 5 8Ex: 3 * 5 15規則一：同等級的由左由右3 + 4 5 = 7 5 = 2

29、規則二：先乘除後加減3 + 4 * 5 = 3 + 20 = 23 規則三：有括號，則先評估括號內之運算式之值3 * ( 4 + 5 ) = 3 * 9 = 2753中序表示式的評估規則中序表示式的評估值，一般都是由左而右的進評估中序表示式之分解動作 利用電腦撰寫演算法以進行評估是很難的!簡單評估之範例: 3 + 4 5 = 7 5 = 2 3 + 4 先算出後(7)，再將值和 5 作減法(-)運算 !不簡單評估之範例: 3 + 4 * 5 = 3 + 20 = 23 不能先算 3 + 4 的值，因為規則必須先算乘法(*) !123456789101112131454評估中序表示式之分解動作

30、利用電腦撰寫演算法以進行評估是Infix 與 Postfix 的對照範例一55Infix 與 Postfix 的對照範例一55Infix 與 Postfix 的對照範例二56Infix 與 Postfix 的對照範例二56Infix 到 Postfix 的轉換方式類似infix 的評估方式來進行由左而右逐一讀入字元(token)若是 operand(運算元)，立刻copy到postfix的輸出字串尾端若是 operator(運算子)若是(左括號：將(推入堆疊中若是)右括號：將堆疊中所有運算子(到左括號為止，左括號捨棄)逐一移出並複製到postfix的輸出字串一般運算子：到堆疊中比較(peek)

31、優先權，若現有運算子(opThis)和堆疊頂端(opTop)的運算子的優先權比較結果是相同或比較高(左括號除外)，就重複移出堆疊中比現有運算子優先權還高的運算子(直到左括號為止，左括號仍留在堆疊中)到postfix的輸出字串。將現有運算子推入堆疊中。若已達運算式尾端，將堆疊中所有運算子逐一移出並複製到postfix的輸出字串57Infix 到 Postfix 的轉換方式類似infix 的Infix 到 Postfix 的轉換規則58Infix 到 Postfix 的轉換規則58Infix 到 Postfix 的轉換範例一- 利用 stack 存放 operators 運算子之優先次序: ( ,

32、 ) * , / , % + , - 3 + 4 5 3 4 + 5 -59Infix 到 Postfix 的轉換範例一- 利用 st課堂練習 infix postfix利用前述規則，畫出stack中之變化3 + 4 * 5 3 * ( 4 + 5 )8 * 6 + ( 4 + 2 * 7 ) - 9 / 3A + B * ( C D )60課堂練習 infix postfix利用前述規則，畫出sinfix 轉換至 postfix 之Java程式架構StackX int maxSize; char stackArray; int top;+ StackX(int s)+ push(char j

33、) : void+ pop() : char+ peek() : char+ peekN() : char+ isEmpty() : boolean+ isFull() : boolean+ displayStack(String s)InToPost String input; String output; StackX theStack;+ InToPost (String in)+ doTrans() : String+ gotOper(opThis, prec1)+ gotParen(char ch)InfixApp+ main ( String )+ getString() : St

34、ring61infix 轉換至 postfix 之Java程式架構StaInfixApp 執行結果Enter infix: Input=A*(B+C)-D/(E+F)For A Stack (bottom-top):For * Stack (bottom-top):For ( Stack (bottom-top): *For B Stack (bottom-top): * (For + Stack (bottom-top): * (For C Stack (bottom-top): * ( +For ) Stack (bottom-top): * ( +For - Stack (bottom-

35、top): *For D Stack (bottom-top): -For / Stack (bottom-top): -For ( Stack (bottom-top): - /For E Stack (bottom-top): - / (For + Stack (bottom-top): - / (For F Stack (bottom-top): - / ( +For ) Stack (bottom-top): - / ( +While Stack (bottom-top): - /While Stack (bottom-top): -End Stack (bottom-top):Pos

36、tfix is ABC+*DEF+/-62InfixApp 執行結果Enter infix: InpuInfixApp 主程式class InfixApp public static void main(String args) throws IOException String input, output;while(true) System.out.print(Enter infix: ); System.out.flush(); input = getString(); / read a string from kbd if( input.equals() ) / quit if Ent

37、erbreak; / make a translator InToPost theTrans = new InToPost(input); output = theTrans.doTrans(); / do the translation System.out.println(Postfix is + output + n); / end while / end main()/ / end of InfixApp63InfixApp 主程式class InfixApp 63InToPost Java程式- part 1- doTrans() 主要程式碼switch(ch)case +: / i

38、ts + or -case -:gotOper(ch, 1); / go pop operatorsbreak; / (precedence 1)case *: / its * or /case /:gotOper(ch, 2); / go pop operatorsbreak; / (precedence 2)case (: / its a left parentheStack.push(ch); / push itbreak;case ): / its a right parengotParen(ch); / go pop operatorsbreak;default: / must be

39、 an operandoutput = output + ch; / write it to outputbreak; / end switch64InToPost Java程式- part 1- doTrInToPost Java程式- part 2public void gotOper(char opThis, int prec1) / got operator from inputwhile( !theStack.isEmpty() ) char opTop = theStack.pop();if ( opTop = ( ) / if its a ( theStack.push(opTo

40、p); / restore ( break;else / its an operator int prec2; / precedence of new op if (opTop=+ | opTop=-) / find new op prec prec2 = 1; else prec2 = 2; if(prec2 prec1) / if prec of new op less than prec of old theStack.push(opTop); / save newly-popped op break; else / prec of new not less output = outpu

41、t + opTop; / than prec of old / end else (its an operator) / end whiletheStack.push(opThis); / push new operator / end gotOp()opTop = opThis65InToPost Java程式- part 2public InToPost Java程式- part 3public void gotParen(char ch) / got right paren from inputwhile( !theStack.isEmpty() )char chx = theStack

42、.pop();if ( chx = ( ) / if popped ( break; / were doneelse / if popped operator output = output + chx; / output it / end while / end popOps()66InToPost Java程式- part 3public 評估後序運算式(Postfix Expressions) 我們怎麼去 Evaluate Postfix Expression ? 3 4 5 + * 6 1 2 + / -927322567評估後序運算式(Postfix Expressions) 我評估

43、後序運算式(Postfix Expressions)電腦程式如何幫我們進行評估 ?Rules for Postfix Evaluation68評估後序運算式(Postfix Expressions)電腦評估後序運算式的Java程式架構StackX int maxSize; int stackArray; int top;+ StackX(int s)+ push(int j) : void+ pop() : int+ peek() : int+ peekN() : int+ isEmpty() : boolean+ isFull() : boolean+ displayStack(String

44、 s)ParsePost String input;- StackX theStack;+ ParsePost (String in)+ doParse() : intPostfixApp+ main ( String )+ getString() : String69評估後序運算式的Java程式架構StackX int maxPostfixApp 執行結果Enter postfix: 345+*612+/-3 Stack (bottom-top):4 Stack (bottom-top): 35 Stack (bottom-top): 3 4+ Stack (bottom-top): 3 4

45、 5* Stack (bottom-top): 3 96 Stack (bottom-top): 271 Stack (bottom-top): 27 62 Stack (bottom-top): 27 6 1+ Stack (bottom-top): 27 6 1 2/ Stack (bottom-top): 27 6 3- Stack (bottom-top): 27 2Evaluates to 2570PostfixApp 執行結果Enter postfix: PostfixApp 主程式public static void main(String args) throws IOExce

46、ptionString input;int output;while(true) System.out.print(Enter postfix: );System.out.flush();input = getString(); / read a string from kbdif ( input.equals() ) / quit if Enter break;/ make a parserParsePost aParser = new ParsePost(input);output = aParser.doParse(); / do the evaluationSystem.out.println(Evaluates to + output); / end while / end main()71PostfixApp 主程式public static voParsePost 主要程式 part 1public int doParse() theStack = new StackX(20); / make new stackchar ch;int j, num1, num2, inte