《数据结构与算法》Chap3 stack.ppt

《《数据结构与算法》Chap3 stack.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、CollegeofElectronicandInformationEngineeringChongqingUniversityofScienceandTechnologyInstructor:XiongQianSpring2013DataStructuresandAlgorithmsChapter3:StacksChapter3ObjectivesUponcompletionyouwillbeabletoExplainthedesign,use,andoperationofastackImplementastackusingalinkedliststru

2、ctureUnderstandtheoperationofthestackADTWriteapplicationprogramsusingthestackADTDiscussreversingdata,parsing,postponingandbacktrackingStackshighlights3.1BasicStackOperations3.2StackLinkedListImplementation3.3CLanguageImplementations3.4StackADT3.5StackApplicationsStackdefinitionSta

3、ckofbooksThequestionsare:1.Howtoaddabooktothestack?2.Howtotakethethirdbookfromtop?UnderstandstackYoucanimaginestackasthisbarrelAstackisalastin-firstout(LIFO)datastructureinwhichallinsertionanddeletionarerestricttooneend,calledtop.PushstackPopstackStacktop3-1BasicStackOperationsPus

4、hstackDATAPUSHDATADATAPushoperationaddsanitematthetopofthestack.Beforeaddingtheitem,thestackspacemustbecheckedtoensurethatthereisenoughroomtoholdtheitem.POPStackPOPDATAPOPremovestheitematthetopofthestackandreturntheitemtotheuser(theapplicationthatcallsthisoperation).Becarefultheem

5、ptystateorunderflowstateofthestack,whenyouimplementpopoperation.StacktopStackTopDATAStackTopcopiestheitematthetopofthestackandreturntheitemtotheuser(theapplicationthatcallsthisoperation),butdoesnotremovetheitem.Becarefultheemptystateorunderflowstateofthestack,whenyouimplementstack

6、topoperation.ExampleofbasicstackoperationsBlueRedGreenPush“Green”BlueRedGreenPush“Blue”RedGreenBluePOPRedGreenBluePUSHRedGreenBlueRedSTACKTOPGreenRedRedPOPGreenRedPOPGreenSeveraldatastructureimplementstack.Linkedlisthassomeadvantagestoimplementstack.dynamicmemoryallocationtechnolo

7、gytosavememoryspace.easilyidentifytheTopofthestack.theheadoflinkedlist3-2StackLinkedListImplementationConceptualandphysicalstackimplementationsTheStructureofStackHeadandStacknodeMetadataTopStackDataNextStackHeadstructureStackDatastructurePointertonodestackcounttopendstacknodedata

8、nextendnodeStackAlgorithmsandPseu