[工学]数据结构course05stackandqueue前序和后序表达式

《[工学]数据结构course05stackandqueue前序和后序表达式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、資料結構(DataStructures)Course5:StackandQueue▓Outlines本章重點Stack的定義、應用、製作與ADTQueue的定義、應用、製作與ADTInfix(中序)運算式與Postfix(後序),Prefix(前序)運算式間之相互轉換Postfix與Prefix的計算(Evaluation)StackPermutation2Astackisalinearlistinwhichalladditionsanddeletionsarerestrictedtooneend.Ifyouinsertedadataseriesintoastackandthenremoved

2、ittheorderofthedatawouldbereversed(反轉).Thisreversingattributeiswhystacksareknownasthelastin-firstout(LIFO)datastructure.3▓StackDef:具有LIFO(lastin-firstout)或FILO(firstin-lastout)性質的有序串列。插入元素的動作稱為Push,刪除元素的動作稱為Pop.Push/Pop的動作皆發生在同一端，此端稱為Top.4▓Stack之ADTDataObjectSpec.AsetofdataitemTop:指出目前頂端元素所在Size:表St

3、ack的大小OperationSpec.Create(S)S建立一個空的StackS,傳回值為一個新的StackSPush(S,item)S將資料item插入到StackS中，並成為Top端元素IfStackfull,則無法執行Pop(S)item,S刪除StackS的Top端元素IfStackempty,則無法執行5Top(S)item傳回StackS之Top端元素值，但不刪除IfStackempty,則無法執行此運作即為課本p.158所提到之“StackTop”IsFull(S)Boolean判斷S是否為full若是,則傳回True;否則傳回FalseIsEmpty(S)Boo

4、lean判斷S是否為empty若是,則傳回True;否則傳回False6※練習範例1※Pop(Push(S,item))=STop(Push(S,item))=itemIsEmpty(Create(S))=TruePop(Create(s))=Error(無法執行,∵是空的Stack)IsEmpty(Push(S,i))=False7※練習範例2※有一空的Stack，實施下列動作:PushgreenandbluePopbluePushredStacktopredPopredPopgreen則Stack的內容為何?89有兩個方式:用LinkedList用Array當然，我們也可以用Stack實作

5、出Queue，或用Queue實作出Stack，但這是另一層次的問題了!!▓Stack之製作ADTStackQueueTreeGraph怎麼實作?ArrayLinkedList較基礎的D.S.(層次較低)應用於ApplicationProgram10▓用LinkedList製作StackToimplementthelinkedliststack,weneedtwodifferentstructuresHeadDataNode11HeadAtoppointerAcountofthenumberofelementsinthestack.DataNodeInadditiontothedata,itc

6、ontainsanextpointertootherdatanodes.12Create(S)主要作法:宣告top指標為null即可:top=null(初值);課本作法:Initializesmetadataforastack.Pre:stackisstructureformetadataPost:metadatainitializedAlgorithmcreateStack(refstack)stack.count=0stack.top=nullreturnendcreateStack13Push(S,item)niltoppNewitemtopniltoppNew

7、itemtop推入非空堆疊推入空堆疊14主要作法:beginNew(t);//跟系統要求記憶體空間以產生並置放一個新節點pNewpNewdata=item;//把資料“item”塞到這個新節點pNew的Data欄位中pNewlink=top;top=pNew;end特點:只要Memory有空間，O.S.就允許LinkedStack去Push新資料!!不用像Array一樣，要先檢查Ar