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

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

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

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

4、uble+isEmpty():boolean+isFull():booleanStackAppmain(String )7Stack 程式碼 part 1/constructormaxSize=s;/set array sizestackArray=new doublemaxSize;/create arraytop=-1;/no items yet8Stack 程式碼 part 2/put item on top of stackstackArray+top=j;/increment top,insert item/take item from top of stackreturn stac

5、kArraytop-;/access item,decrement top9Stack 程式碼 part 3/peek at top of stackreturn stackArraytop;/true if stack is emptyreturn(top=-1);/true if stack is fullreturn(top=maxSize-1);10StackApp 程式碼class StackApppublic static void main(String args)StackX theStack=new StackX(10);/make new stacktheStack.pus

6、h(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 itSystem.out.print();/end whileSystem.out.println();/end main()/end class StackApp11push(49)

7、Stack 程式 圖示法pop();pop()12Error Handlingl現有版本之問題l使用者必須負責檢查!lisEmpty()and isFull():將StackX/Queue錯誤例外的處理加入 StackX/Queue 之內,讓使用者不須擔心此問題!修改 push()/insert(),pop()/remove()and peek()/peekFront()method.13Example of Stack:倒轉字母StackX-int maxSize;-double stackArray;-int top;+StackX(int s)+push(double j):void+p

8、op():double+peek():double+isEmpty():boolean+isFull():booleanReverser-String input;-String output;+Reverser(String in)+doRev():StringReverseAppmain(String arg)14Example of Stack:doRev()/reverse the stringint stackSize=input.length();/get max stack sizeStackX theStack=new StackX(stackSize);/make stack

9、for(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:分隔符號之配對-Delimiter Matchingl堆疊之應用之一:Parse(解析)特定字串之內

10、容是否符合語法規範cd/correctabcde/correctab(cde/not correct;doesnt match(abcde/not correct;nothing matches final ab(c)/not correct;Nothing matches opening 16Delimiter Matching 之觀念之觀念nExample:a b (c d e )f a b (c d )e f 17Delimiter Matching 之相關作法之相關作法lDelimiterlOpening Delimiter ,(lClosing Delimiter ,)l作法:l逐一

11、讀取字元l遇到Opening Delimiter就放進 stackl遇到 Closing Delimiter 就從 stack pop 出來一個opening delimiter;若 stack 沒有 Opening Delimiter 可供讀取,則表示有誤!l並比較是否是同一類 delimiter,若不同類就是有誤!l若無資料可供輸入而 Stack 是 empty,就表示原式是正確無誤,否則就有誤!18Delimiter Matching 程式架構程式架構-bracket.javaStackX-int maxSize;-double stackArray;-int top;+StackX(i

12、nt s)+push(double j):void+pop():double+peek():double+isEmpty():boolean+isFull():booleanBracketChecker-String input;+BracketChecker(String in)+check():voidBracketApp+main(String)19Delimiter Matching 程式架構程式架構-check()method part 12.3.int stackSize=input.length();/get max stack size4.StackX theStack=new

13、 StackX(stackSize);/make stack5.for(int j=0;j=front)return rear-front+1;else return(maxSize-front)+(rear+1);34Efficiency of Queueslinsert():O(1)lremove():O(1)lpeek():O(1)35Deques:double-ended queue-同時擁有 stack 與 queue 的特性!l可以從 front 或 rear 進行插入或刪除資料的動作.linsertLeft()and insertRight(),and lremoveLeft()

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

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

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

17、碼 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 upward else/if smaller,break;/done shifting/end forqueArrayj+1=

18、item;/insert itnItems+;/end else(nItems 0)/end insert()44Priority Queue 程式碼 part 3public double remove()/remove minimum item return queArray-nItems;public double peekMin()/peek at minimum item return queArraynItems-1;public boolean isEmpty()/true if queue is empty return(nItems=0);public boolean isF

19、ull()/true if queue is full return(nItems=maxSize);45PriorityQApp 程式碼class PriorityQApppublic static void main(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.

20、remove();System.out.print(item+);/10,20,30,40,50/end whileSystem.out.println();/end main()/-/end class PriorityQApp46Efficiency of Priority Queuesl現有效能linsert():O(N)lremove():O(1)l改進方案l改以 heap 實作!47Parsing Arithmetic Expressions統一更正英中譯名統一更正英中譯名(pp.137 161):linfix:插入 中序中序lpostfix:字尾 後序後序lprefix:字首 前序

21、前序lexpression:表達(法)運算式運算式lpostfix notation:字尾(的)界限 後序表示式後序表示式 linfix notation:插入界限 中序表示式中序表示式lprefix notation:字首(的)界限 前序表示式前序表示式 lpostfix expression:字尾表達法 後序運算式後序運算式loperator:運算元 運算子運算子loperand:運算子 運算元運算元48Expression(運算式)lExpression(運算式)l由運算子(Operator)與運算元(Operand)構成的式子l運算子:+-*/%l運算元:1 2 6 7 i j sum

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

23、ostfixl主要原因lInfix：給人看的，一般程式內的寫法。lPostfix：給電腦看的，方便評估運算式之值!52中序表示式的評估規則l中序表示式的評估值，一般都是由左而右由左而右的進行評估與替換，但是遇到不同等級的運算子，就要特別注意評估之先後次序。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 =2753評估中序表示式之分解動作 利用電腦撰寫演算法以進行評估是很難

24、的利用電腦撰寫演算法以進行評估是很難的!l簡單評估之範例:3+4 5 =7 5=2 3+4 先算出後(7)，再將值和 5 作減法(-)運算!l不簡單評估之範例:3+4*5 =3+20=23 不能先算 3+4 的值，因為規則必須先算乘法(*)!123456789101112131454Infix 與 Postfix 的對照範例一55Infix 與 Postfix 的對照範例二56Infix 到 Postfix 的轉換方式l類似infix 的評估方式來進行1.由左而右逐一讀入字元(token)2.若是 operand(運算元)，立刻copy到postfix的輸出字串尾端3.若是 operator(

25、運算子)l若是(左括號：將(推入堆疊中l若是)右括號：將堆疊中所有運算子(到左括號為止，左括號捨棄)逐一移出並複製到postfix的輸出字串l一般運算子：l到堆疊中比較(peek)優先權，若現有運算子(opThis)和堆疊頂端堆疊頂端(opTop)的運算子的優先權比較結果是相同或比較高相同或比較高(左括號除外)，就重複移出堆疊中比現有運算子優先權還高的運算子(直到左括號為止，左括號仍留在堆疊中)到postfix的輸出字串。l將現有運算子推入堆疊中。4.若已達運算式尾端，將堆疊中所有運算子逐一移出並複製到postfix的輸出字串57Infix 到 Postfix 的轉換規則58Infix 到 P

26、ostfix 的轉換範例一-利用 stack 存放 operators l運算子之優先次序:(,)*,/,%+,-3+4 5 3 4+5-59課堂練習 infix postfixl利用前述規則，畫出stack中之變化l3+4*5 l3*(4+5)l8*6+(4+2*7)-9/3lA+B*(C D)60infix 轉換至 postfix 之Java程式架構StackX-int maxSize;-char stackArray;-int top;+StackX(int s)+push(char j):void+pop():char+peek():char+peekN():char+isEmpty(

27、):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():String61InfixApp 執行結果Enter infix:Input=A*(B+C)-D/(E+F)For A Stack(bottom-top):For*Stac

28、k(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):-/For E Stack(bottom-top):-/(For+Stack(bottom-top):-/(For F Stack(bo

29、ttom-top):-/(+For)Stack(bottom-top):-/(+While Stack(bottom-top):-/While Stack(bottom-top):-End Stack(bottom-top):Postfix is ABC+*DEF+/-62InfixApp 主程式class InfixApp public static void main(String args)throws IOException String input,output;while(true)System.out.print(Enter infix:);System.out.flush();

30、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 translation System.out.println(Postfix is +output+n);/end while/end main()/end of InfixApp63InToPost Java程式-part 1-doTrans()主要程式碼主

31、要程式碼switch(ch)case+:/its+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 an operand

32、output=output+ch;/write it to outputbreak;/end switch64InToPost 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(opTop);/restore(break;else /its an operator int prec2;/precedence of ne

33、w 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=output+opTop;/than prec of old/end else(its an operator)/end whiletheStack.push(opThis);/push new o

34、perator/end gotOp()opTop=opThis65InToPost Java程式-part 3public 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()66評估後序運算式後序運算式(Postfix Expres

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

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

37、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 主程式public static void main(String args)throws IOExceptionString input;int output;while(true)System.out.print(Enter postfix:)

38、;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()71ParsePost 主要程式 part 1public int doParse()

39、theStack=new StackX(20);/make new stackchar ch;int j,num1,num2,interAns;for(j=0;j=0&ch=9)/if its a numbertheStack.push(int)(ch-0);/push it else /its an operatornum2=theStack.pop();/pop operandsnum1=theStack.pop();switch(ch)/do arithmetic case+:interAns=num1+num2;break;case-:interAns=num1-num2;break;

40、case*:interAns=num1*num2;break;case/:interAns=num1/num2;break;default:interAns=0;/end switchtheStack.push(interAns);/push result /end else/end forinterAns=theStack.pop();/get answerreturn interAns;/end doParse()72Review of Chapter 4 are data structures usually used to simplify certain programming op

41、erations.lThe important are pushing(inserting)an item onto the top of the stack and popping(removing)the item thats on the top.lThe important are inserting an item at the rear of the queue and removing the item from the front of the queue.lA queue can be implemented as a circular queue,which is base

42、d on an array in which the indices wrap around from the end of the array to the beginning.lA priority queue allows access to the smallest(or sometimes the largest)item.lThese data structures can be implemented with or with other mechanisms such as.lArithmetic expressions are typically evaluated by translating them to postfix notation and then evaluating the postfix expression.lA stack is a useful tool both for translating an infix to a postfix expression and for evaluating a postfix expressi on.73