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

1、1Chapter 4 Stacks and QueuesJames Chen2005/10/242OutlineslSome Different kinds of StructureslStackslReverse StringlDelimiter matchinglQueueslPriority QueueslParsing Arithmetic Expressionslinfix postfix expression3Different Structuresl先前章節討論過的資料結構和演算法與本章即將要討論的資料結構和演算法有著極為明顯的差異。l有三點主要差異有三點主要差異: :l真實世界

2、的資料 v.s. 程式設計師的工具lArray 對應到現實資料lStack/Queue 程式內部使用l限制存取的機制l無法使用 index 直接存取.必須借由Interfaces 存取.l一次只能存取一筆資料(最上面 or 最前面).l更抽象化的概念l使用這些資料結構的程式不需要知道實作細節.l實際的儲存機制也不須擔心! ( Array or Linked-List or Heap )4郵件之堆積處理方式:l由上而下(Top-to-Bottom)逐一處理 Stackl由最久的開始處理. Queuel重新攪亂,並依重要性重新排列. Priority Queue5Stacks (堆疊)l說明l推入

3、(Push), 拋出(Pop) 和取值(Peek) l只能存取最近推入(Push)的資料(最上面).l若要存取其他資料, 必須先移出最上面的資料.lLIFO Last In First Outl有頂端 (Top) 一個紀錄變數l應用l檢查原始程式中的成對的括號 l評估數學運算式(Arithmetic Expression)的值.l程式執行過程: 副程式之呼叫與返回6Stack Applet7Stack 原始程式l 架構關係StackX- int maxSize;- double stackArray;- int top;+ StackX(int s)+ push(double j) : voi

4、d+ pop() : double+ peek() : double+ isEmpty() : boolean+ isFull() : booleanStackAppmain( String )8Stack 程式碼 part 1 / constructormaxSize = s; / set array sizestackArray = new doublemaxSize; / create arraytop = -1; / no items yet9Stack 程式碼 part 2 / put item on top of stackstackArray+top = j; / increme

5、nt top, insert item / take item from top of stackreturn stackArraytop-; / access item, decrement top10Stack 程式碼 part 3 / peek at top of stackreturn stackArraytop; / true if stack is emptyreturn (top = -1); / true if stack is fullreturn (top = maxSize-1);11StackApp 程式碼class StackApppublic static void

6、 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.out.print(value); / display

7、 itSystem.out.print( ); / end whileSystem.out.println(); / end main() / end class StackApp12push(49)Stack 程式 圖示法pop(); pop()13Error Handlingl現有版本之問題l使用者必須負責檢查! lisEmpty() and isFull(): 將StackX/Queue錯誤例外的處理加入 StackX/Queue 之內, 讓使用者不須擔心此問題! 修改 push()/insert() , pop()/remove() and peek()/peekFront() met

8、hod.14Example of Stack : 倒轉字母StackX- int maxSize;- double stackArray;- int top;+ StackX(int s)+ push(double j) : void+ pop() : double+ peek() : double+ isEmpty() : boolean+ isFull() : booleanReverser- String input;- String output;+ Reverser(String in)+ doRev() : StringReverseAppmain ( String arg) 15

9、Example of Stack : doRev() / reverse the stringint stackSize = input.length(); / get max stack sizeStackX theStack = new StackX(stackSize); / 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(

10、) ) char ch = theStack.pop(); / pop a char,output = output + ch; / append to outputreturn output; / end doRev()16Example of Stack : 分隔符號之配對- Delimiter Matchingl堆疊之應用之一: Parse (解析) 特定字串之內容是否符合語法規範cd / correctabcde / correctab(cde / not correct; doesnt match (abcde / not correct; nothing matches final

11、 ab(c) / not correct; Nothing matches opening 17Delimiter Matching 之觀念之觀念nExample : a b ( c d e ) f a b ( c d ) e f 18Delimiter Matching 之相關作法之相關作法lDelimiterlOpening Delimiter , , (lClosing Delimiter , , )l作法:l逐一讀取字元l遇到Opening Delimiter就放進 stackl遇到 Closing Delimiter 就從 stack pop 出來一個opening delimite

12、r;若 stack 沒有 Opening Delimiter 可供讀取, 則表示有誤!l並比較是否是同一類 delimiter, 若不同類就是有誤!l若無資料可供輸入而 Stack 是 empty, 就表示原式是正確無誤, 否則就有誤!19Delimiter Matching 程式架構程式架構- bracket.javaStackX- int maxSize;- double stackArray;- int top;+ StackX(int s)+ push(double j) : void+ pop() : double+ peek() : double+ isEmpty() : bool

13、ean+ isFull() : booleanBracketChecker- String input;+ BracketChecker(String in)+ check() : voidBracketApp+ main ( String )20Delimiter Matching 程式架構程式架構- check() method part 12.3.int stackSize = input.length(); / get max stack size4.StackX theStack = new StackX(stackSize); / make stack5.for (int j=0;

14、 j= front) return rear-front+1;else return (maxSize-front) + (rear+1);35Efficiency of Queueslinsert() : O(1)lremove() : O(1)lpeek() : O(1)36Deques : double-ended queue- 同時擁有 stack 與 queue 的特性 !l可以從 front 或 rear 進行插入或刪除資料的動作.linsertLeft() and insertRight(), and lremoveLeft() and removeRight()l應用linse

15、rtLeft() + removeLeft() StacklinsertLeft() + removeRight() Queue37Priority Queues (優先佇列優先佇列)l佇列中的資料是依照優先等級來排列:l具有最高優先權者排在front， 以便即時被處理!l具有相同優先權的依照FIFO排列!l優先佇列優先佇列也是程式設計的工具之一。lOS 的作業排程38Priority Queue 之實作l一般仍和Queue相同, 會有 front 和 rearl但是通常我們需要仍夠較最高優先(鍵值最小or最大)的資料進行處理. 也希望能夠新的資料.使用 heap (MaxHeap, MinH

16、eap) 的資料結構來實作儲存空間, 但是效率就差很多 !讀取(移除)的速度很快! (Why)插入的速度很慢 ! (Why)39PriorityQ Applet- Front/Rear 作法和原有作法和原有 Queue 不同不同 !40Some Approach for Implementationl l讀取(移除)的速度很快! (Why)l插入的速度很慢 ! (Why)l讀取(移除)的速度很慢! (Why)l插入的速度很快! (Why)41PriorityQ 示意圖insert(6)remove() ; remove()42Priority Queue 程式架構PriorityQ- int

17、maxSize;- double queArray;- int nItems;+ Queue(int s)+ insert(double j) : void+ remove() : double+ peekMin() : double+ size() : int+ isEmpty() : boolean+ isFull() : booleanPriorityQAppmain( String )43Priority Queue 程式碼 part 1public PriorityQ(int s) / constructormaxSize = s;queArray = new doublemaxSi

18、ze;nItems = 0;44Priority 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 larger, queArrayj+1 = queArrayj; / shift upwa

19、rd else / if smaller, break; / done shifting / end forqueArrayj+1 = item; / insert itnItems+; / end else (nItems 0) / end insert()45Priority Queue 程式碼 part 3public double remove() / remove minimum item return queArray-nItems; public double peekMin() / peek at minimum item return queArraynItems-1; pu

20、blic boolean isEmpty() / true if queue is empty return (nItems=0); public boolean isFull() / true if queue is full return (nItems = maxSize); 46PriorityQApp 程式碼class PriorityQApppublic static void main(String args) throws IOException PriorityQ thePQ = new PriorityQ(5);thePQ.insert(30);thePQ.insert(5

21、0);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 main()/- / end class PriorityQApp47Efficiency of Priority Queuesl現有效能linsert() : O(N)lremove() : O(1)l改

22、進方案l改以 heap 實作!48Parsing Arithmetic Expressions統一更正英中譯名統一更正英中譯名 (pp. 137 161) : linfix : 插入 中序中序lpostfix : 字尾 後序後序lprefix : 字首 前序前序lexpression :表達(法) 運算式運算式lpostfix notation : 字尾(的)界限 後序表示式後序表示式 linfix notation : 插入界限 中序表示式中序表示式lprefix notation : 字首(的)界限 前序表示式前序表示式 lpostfix expression : 字尾表達法 後序運算式後

23、序運算式loperator : 運算元 運算子運算子loperand : 運算子 運算元運算元49Expression (運算式)lExpression (運算式)l由運算子(Operator)與運算元(Operand)構成的式子l運算子: + - * / % l運算元: 1 2 6 7 i j sum salaryEx: i *2 + j*salary ( i + j ) * 5 + 750Parsing Arithmetic ExpressionslExamples: 3 + 5 7 1 3 + 5 * 7 38 3 * ( 5+7) 36 l對人而言，很容易就算出其值 !l但利用電腦，要

24、直接利用演算法去寫出解析程式是有點挑戰!l利用電腦評估值的作法: two-phasesl先將來的數學運算式轉成後序表示法 ( postfix notation )l評估後序表示式的值PS: PS: 兩個步驟都要用到兩個步驟都要用到 stack !stack !51Infix 與 Postfix Notation (中序與後序表示式)52為何要將 Infix 轉成 Postfixl主要原因lInfix ：給人看的，一般程式內的寫法。lPostfix ：給電腦看的，方便評估運算式之值!53中序表示式的評估規則l中序表示式的評估值，一般都是由左而右由左而右的進行評估與替換，但是遇到不同等級的運算子，

25、就要特別注意評估之先後次序。l運算子運算子搭配適當數量的運算元適當數量的運算元即可評估其值Ex: 3 + 5 8Ex: 3 * 5 15l規則一：同等級的由左由右l3 + 4 5 = 7 5 = 2l 規則二：先乘除後加減l3 + 4 * 5 = 3 + 20 = 23l 規則三：有括號，則先評估括號內之運算式之值l3 * ( 4 + 5 ) = 3 * 9 = 2754評估中序表示式之分解動作 利用電腦撰寫演算法以進行評估是很難的利用電腦撰寫演算法以進行評估是很難的!l簡單評估之範例: 3 + 4 5 = 7 5 = 2 3 + 4 先算出後(7)，再將值和 5 作減法(-)運算 !l不簡單

26、評估之範例: 3 + 4 * 5 = 3 + 20 = 23 不能先算 3 + 4 的值，因為規則必須先算乘法(*) !123456789101112131455Infix 與 Postfix 的對照範例一56Infix 與 Postfix 的對照範例二57Infix 到 Postfix 的轉換方式l類似infix 的評估方式來進行1.由左而右逐一讀入字元(token)2.若是 operand(運算元)，立刻copy到postfix的輸出字串尾端3.若是 operator(運算子)l若是(左括號：將(推入堆疊中l若是)右括號：將堆疊中所有運算子(到左括號為止，左括號捨棄)逐一移出並複製到pos

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

28、 % + , - 3 + 4 5 3 4 + 5 -60課堂練習 infix postfixl利用前述規則，畫出stack中之變化l3 + 4 * 5 l3 * ( 4 + 5 )l8 * 6 + ( 4 + 2 * 7 ) - 9 / 3lA + B * ( C D )61infix 轉換至 postfix 之Java程式架構StackX- int maxSize;- char stackArray;- int top;+ StackX(int s)+ push(char j) : void+ pop() : char+ peek() : char+ peekN() : char+ isEm

29、pty() : 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() : String62InfixApp 執行結果Enter infix: Input=A*(B+C)-D/(E+F)For

30、 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-top): *For D Stack (bottom-top): -For / Stack (bottom-top): -For ( Stack (bottom-top):

31、 - /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):Postfix is ABC+*DEF+/-63InfixApp 主程式class InfixApp public static void main(String args) t

32、hrows 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 Enterbreak; / make a translator InToPost theTrans = new InToPost(input); output = theTrans.doTrans(); / do the translat

33、ion System.out.println(Postfix is + output + n); / end while / end main()/ / end of InfixApp64InToPost Java程式- part 1- doTrans() 主要程式碼主要程式碼switch(ch)case +: / its + or -case -:gotOper(ch, 1); / go pop operatorsbreak; / (precedence 1)case *: / its * or /case /:gotOper(ch, 2); / go pop operatorsbreak;

34、 / (precedence 2)case (: / its a left parentheStack.push(ch); / push itbreak;case ): / its a right parengotParen(ch); / go pop operatorsbreak;default: / must be an operandoutput = output + ch; / write it to outputbreak; / end switch65InToPost Java程式- part 2public void gotOper(char opThis, int prec1)

35、 / got operator from inputwhile( !theStack.isEmpty() ) char opTop = theStack.pop();if ( opTop = ( ) / if its a ( theStack.push(opTop); / 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

36、prec of new op less than prec of old theStack.push(opTop); / save newly-popped op break; else / prec of new not less output = output + opTop; / than prec of old / end else (its an operator) / end whiletheStack.push(opThis); / push new operator / end gotOp()opTop = opThis66InToPost Java程式- part 3publ

37、ic void gotParen(char ch) / got right paren from inputwhile( !theStack.isEmpty() )char chx = theStack.pop();if ( chx = ( ) / if popped ( break; / were doneelse / if popped operator output = output + chx; / output it / end while / end popOps()67評估後序運算式後序運算式(Postfix Expressions) 我們怎麼去我們怎麼去 Evaluate Po

38、stfix Expression ? 3 4 5 + * 6 1 2 + / -927322568評估後序運算式後序運算式(Postfix Expressions)l電腦程式如何幫我們進行評估 ?lRules for Postfix Evaluation69評估後序運算式的Java程式架構StackX- int maxSize;- int stackArray;- int top;+ StackX(int s)+ push(int j) : void+ pop() : int+ peek() : int+ peekN() : int+ isEmpty() : boolean+ isFull()

39、 : boolean+ displayStack(String s)ParsePost- String input;- StackX theStack;+ ParsePost (String in)+ doParse() : intPostfixApp+ main ( String )+ getString() : String70PostfixApp 執行結果Enter postfix: 345+*612+/-3 Stack (bottom-top):4 Stack (bottom-top): 35 Stack (bottom-top): 3 4+ Stack (bottom-top): 3

40、 4 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 2571PostfixApp 主程式public static void main(String args) throws IOExceptionString input;int output

41、;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()72ParsePost 主要程式 part 1public int doParse() theStack = new StackX(20); / make new stackchar ch;int j, num1, num2, interAns;for (j=0; j= 0 & ch = 9