先前章節(jié)討論過的結(jié)構(gòu)和演算法與本章即將要討論的課件

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先前章節(jié)討論過的資料結(jié)構(gòu)和演算法

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

3、始處理. Queue重新攪亂,並依重要性重新排列. Priority Queue4郵件之堆積處理方式:4Stacks (堆疊)說明推入(Push), 拋出(Pop) 和取值(Peek) 只能存取最近推入(Push)的資料(最上面).若要存取其他資料, 必須先移出最上面的資料.LIFO Last In First Out有頂端 (Top) 一個(gè)紀(jì)錄變數(shù)應(yīng)用檢查原始程式中的成對(duì)的括號(hào) 評(píng)估數(shù)學(xué)運(yùn)算式(Arithmetic Expression)的值.程式執(zhí)行過程: 副程式之呼叫與返回5Stacks (堆疊)說明5Stack Applet6Stack Applet6Stack 原始程式 架構(gòu)關(guān)係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 原始程式 架構(gòu)關(guān)係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現(xiàn)有版本之問題使用者必須負(fù)責(zé)檢查! isEmpty() and isFull()Homework2 : 將StackX/Queue錯(cuò)誤例外的處理加入 St

9、ackX/Queue 之內(nèi), 讓使用者不須擔(dān)心此問題! 修改 push()/insert() , pop()/remove() and peek()/peekFront() method.13Error Handling現(xiàn)有版本之問題13Example of Stack : 倒轉(zhuǎn)字母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 : 倒轉(zhuǎn)字母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 : 分隔符號(hào)之配對(duì)- Delimiter Matching堆疊之應(yīng)用之一: Parse (解析) 特定字串之內(nèi)容是否符合語法規(guī)範(fàn)cd / correctabcde / correctab(cde / not correct; doesnt match (abcde / not correct; nothing matches final ab(c) / not correct; Nothing matches opening 16Example of Stack : 分隔符號(hào)之配對(duì)- DDelimiter Matching 之觀念Example : a

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

14、就是有誤!若無資料可供輸入而 Stack 是 empty, 就表示原式是正確無誤, 否則就有誤!18Delimiter Matching 之相關(guān)作法DelimiDelimiter Matching 程式架構(gòu)- 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 程式架構(gòu)- bracDelimiter Matching 程式架構(gòu)- 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- 同時(shí)擁有 stack 與 queue 的特性 !可以從 front 或 rear 進(jìn)行插入或刪除資料

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

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

19、 Front/Rear Some Approach for Implementation 使用有排序的方式利用 Array 實(shí)作 (常用)讀取(移除)的速度很快! (Why)插入的速度很慢 ! (Why)使用隨意的方式利用 Array 實(shí)作讀取(移除)的速度很慢! (Why)插入的速度很快! (Why)40Some Approach for ImplementatiPriorityQ 示意圖insert(6)remove() ; remove()41PriorityQ 示意圖insert(6)remove()Priority Queue 程式架構(gòu)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 程式架構(gòu)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現(xiàn)有效能insert() : O(N)remove() : O(1)改進(jìn)方案改以 heap 實(shí)作!47Efficiency of Priority Queues現(xiàn)Parsing Arithmetic Expressions統(tǒng)一更正英中譯名 (pp. 137 161) : infix : 插入 中序postfix : 字尾 後序prefix : 字首 前序expression :表達(dá)(法) 運(yùn)算式postfix

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

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

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

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

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

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

32、 ) * , / , % + , - 3 + 4 5 3 4 + 5 -59Infix 到 Postfix 的轉(zhuǎn)換範(fàn)例一- 利用 st課堂練習(xí) infix postfix利用前述規(guī)則，畫出stack中之變化3 + 4 * 5 3 * ( 4 + 5 )8 * 6 + ( 4 + 2 * 7 ) - 9 / 3A + B * ( C D )60課堂練習(xí) infix postfix利用前述規(guī)則，畫出sinfix 轉(zhuǎn)換至 postfix 之Java程式架構(gòu)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 轉(zhuǎn)換至 postfix 之Java程式架構(gòu)StaInfixApp 執(zhí)行結(jié)果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 執(zhí)行結(jié)果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 評(píng)估後序運(yùn)算式(Postfix Expressions) 我們?cè)觞N去 Evaluate Postfix Expression ? 3 4 5 + * 6 1 2 + / -927322567評(píng)估後序運(yùn)算式(Postfix Expressions) 我評(píng)估

43、後序運(yùn)算式(Postfix Expressions)電腦程式如何幫我們進(jìn)行評(píng)估 ?Rules for Postfix Evaluation68評(píng)估後序運(yùn)算式(Postfix Expressions)電腦評(píng)估後序運(yùn)算式的Java程式架構(gòu)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評(píng)估後序運(yùn)算式的Java程式架構(gòu)StackX int maxPostfixApp 執(zhí)行結(jié)果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 執(zhí)行結(jié)果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