《数据结构与算法》Chap3-stack

CollegeofElectronicandInformationEngineeringChongqingUniversityofScienceandTechnologyInstructor:XiongQian

Spring2013DataStructuresandAlgorithms

Chapter3:StacksChapter3Objectives

Uponcompletionyouwillbeableto

Explainthedesign,use,andoperationofastackImplementastackusingalinkedliststructureUnderstandtheoperationofthestackADTWriteapplicationprogramsusingthestackADTDiscussreversingdata,parsing,postponingandbacktrackingStackshighlights3.1BasicStackOperations3.2StackLinkedListImplementation3.3CLanguageImplementations3.4StackADT3.5StackApplicationsStackdefinitionStackofbooksThequestionsare:1.Howtoaddabooktothestack?2.Howtotakethethirdbookfromtop?UnderstandstackYoucanimaginestackasthisbarrelAstackisalastin-firstout

(LIFO)datastructureinwhichallinsertionanddeletionarerestricttooneend,calledtop.PushstackPopstackStacktop3-1

BasicStackOperationsPushstackDATAPUSHDATADATAPushoperationaddsanitematthetopofthestack.Beforeaddingtheitem,thestackspacemustbecheckedtoensurethatthereisenoughroomtoholdtheitem.POPStackPOPDATAPOPremovestheitematthetopofthestackandreturntheitemtotheuser(theapplicationthatcallsthisoperation).Becarefultheemptystateorunderflowstateofthestack,whenyouimplementpopoperation.StacktopStackTopDATAStackTopcopiestheitematthetopofthestackandreturntheitemtotheuser(theapplicationthatcallsthisoperation),butdoesnotremovetheitem.Becarefultheemptystateorunderflowstateofthestack,whenyouimplementstacktopoperation.ExampleofbasicstackoperationsBlueRedGreenPush“Green”BlueRedGreenPush“Blue”RedGreenBluePOPRedGreenBluePUSHRedGreenBlueRedSTACKTOPGreenRedRedPOPGreenRedPOPGreenSeveraldatastructureimplementstack.Linkedlisthassomeadvantagestoimplementstack.dynamicmemoryallocationtechnologytosavememoryspace.easilyidentifytheTopofthestack.theheadoflinkedlist3-2StackLinkedListImplementationConceptualandphysicalstackimplementationsTheStructureof

StackHeadandStacknodeMetadataTopStackDataNextStackHeadstructureStackDatastructurePointertonodestackcounttopendstacknodedatanextendnodeStackAlgorithmsandPseudocodeimplementationCreatestackPushstackPopstackStacktopEmptystackFullstackStackcountDestroystackCreatestackCreatestackjustinitializethemetadataforthestackstructure.?count?Top0count×TopalgorithmcreateStackInitializemetadataforastack.

PreStackisstructureformetadata.Postmetadatainitializedstack.count=0stack.top=nullReturnendcreateStackPushStack0count×TopPUSHGreen1countTopGreendata×nextPUSHGreenInsertsanelementintothestack1.Findmemoryforthenewnode2.Assignthedatatothestacknode3.Changethepointers4.Count+1Insertanodetostackneedstoknowthat:Intoanemptystack?Intoastackwithdata(logicalisthesame)Hasnomemory(overflow)PushStack(Continue)PUSHBlue1countTopGreendata×next2countTopbluedatanextGreendata×nextPUSHBluePushStack(Pseudocode)algorithmpushStack(stack,data)Insert(push)oneitemintothestack.Prestackismetadatastructuretoavalidstack,datacontainsdatatobepushedinstackPostdatahavebeenpushedinstack.Returntrueifsuccessful;falseifmemoryoverflow.1if(stackisfull)1success=falseelse1allocate(newPtr)2newPtr->data=data3newPtr->next=stack.top4stack.top=newPtr5stack.count=stack.count+16success=trueendifreturnsuccessendpushStackPopStack2countTopbluedatanextGreendata×next1countTopGreendata×nextPOPStackPOPStackPopStack(Continue)1countTopGreendata×nextPOPStack0count×TopPOPStackPopStack(pseudocode)AlgorithmpopStack(stack,dataOut)Thisalgorithmpopstheitemonthetopofthestackandreturnsittotheuser.PrestackismetadatastructuretoavalidstackdataOutisareferencevariabletoreceivethedata.PostDatahavebeenreturnedtocallingalgorithm.Returntrueifsuccessful;falseifunderflow.1If(stackempty)1success=false2Else1dltPtr=stack.top2dataOut=stack.top->data3stack.top=stack.top->next4stack.count=stack.count-15recycle(dltPtr)6success=true3endif4returnsuccessendpopstackStackTopThestacktopalgorithmsendsthedataatthetopofthestackbacktothecallingmodulewithoutdeletingthetopnode.Thelogicforthestacktopissimple,butonethingshouldbetakencare,thatisthestateofstackempty.Stacktop(pseudocode)algorithmstackTop(stack,dataOut)ThisalgorithmretrievesthedatafromthetopofthestackwithoutchangingthestackPrestackismetadatastructuretoavalidstackdataOutisareferencevariabletoreceivethedataPostdatahavebeenreturnedtocallingalgorithmReturndatahavebeenreturned,falseifunderflow.1if(stackempty)1success=false2else1DataOut=stack.top->data2Success=true3endif4returnsuccessendstackTopDestroystack(Originalstate)3countTopbluedatanextGreendata×nextReddatanextTempReddatanext3countTopbluedatanextGreendata×nextDestroystack(Deleteitem1)Destroystack(Deleteitem2)3countTopGreendata×nextTempbluedatanextDestroystack(Deleteitem3)0count×TopTempGreendatanextPseudocodeforDestroyStackalgorithmdestroystack(stack)Thisalgorithmreleasesallnodesbacktothedynamicmemory.

Prestackismetadatastructuretoavalidstack

Poststackemptyandallnodesrecycledloop(stack.topnotnull)1temp=stack.top2stack.top=temp.next3recycle(temp)endloopstack.count=0returnenddestroyStackOtherstackalgorithmsFundamentalstackoperationsincludecreatestack,pushstack,popstack,stacktop,anddestroystack.Inordertototallyencapsulatethedataandthedatastructureofthestack.Threesimpleoperationsareintroduced.Theyareemptystack,stackcount,andfullstack.Emptystackoperationisverysimple.Basedonlinkedlistimplementation.Wecanjustchecktheheadnodeofthelisttodeterminewhetherthestackisemptyornot.Thereforethepseudocodeisverysimple.algorithmemptyStack(stack)DetermineswhetherstackisemptyandreturnsaBoolean.PrestackismetadatastructuretoavalidstackPostreturnsstackstatusReturnBoolean,true:stackempty,false:stackcontainsdataif(stack.topnotnull)1result=falseelse1result=trueendifreturnresultEndemptyStackEmptystackOtherconditionstatement(s)thatcanbeusedheretoreplacethisstatement.FullstackalgorithmfullStack(stack)DetermineswhetherstackisfullornotandreturnsaBoolean.

Prestackismetadatastructuretoavalidstack.

Postreturnsstackstatus.

ReturnBoolean,true:stackfull,false:memoryavailableIf(memoryavailable)1result=falseelse1result=trueendifreturnfalseendfullStackStackCountalgorithmstackCount(stack)Returnsthenumberofelementscurrentlyinstack

PrestackismetadatastructuretoavalidstackPostreturnsstackcount

Returnintegercountofnumberofelementsinstack.return(stack.count)endstackCountThereisonlyoneexecutivestatementinthisalgorithm.Ofcourse,itcanbeplacedintheupperfunctionsandeliminatethisalgorithm.ButdonotforgettheessenceofADT—hidingthedataandthestructureabsolutelytotheupperapplications.3-3CLanguageImplementationsThissectionpresentsasimplenon-ADTimplementationofastack.Wedevelopasimpleprogramthatinsertsrandomcharactersintothestackandthenprintsthem.3-4StackADTWebeginthediscussionofthestackADTwithadiscussionofthestackstructureanditsapplicationinterface.Wethendeveloptherequiredfunctions.DataStructureADTImplemenationTypicalstackapplicationscanbeclassifiedintofourbroadcategories:ReversingdataReverseaListConvertdecimaltobinaryParsingdataParseparenthesesPostponingdatausageInfixtopostfixtransformationEvaluatingPostfixexpressionsBacktrackingstepsgoalseekingEightQueensProblem3-5StackApplicationsReverseaListalgorithmreverseNumberThisprogramreversesalistofintegersreadfromthekeyboardbypushingthemintoastackandretrievingthemonebyone.1createStack(stack)2prompt(Enteranumber)3read(number)Fillstack4loop(notendofdataANDnotfullStack(stack))1pushStack(stack,number)2prompt(Enternextnumber:<EOF>tostop)3read(number)5endloopNowprintnumbersinreverse6Loop(notemptyStack(stack))1popStack(stackdataOut)2print(dataOut)7endloopendreverseNumberTheidealiesinreversingdataisveryeasytounderstand.First,pusheachitemonebyoneintostack(statements4-5),thenpopthemoutsuccessively(statements6-7).BecausestackisaLIFOdatastructure,theorderoftheitemhasbeenreversed.(continued)Convertdecimaltobinarydividedecimalnumberby2continuouslyrecordtheremaindersuntilthequotientbecomes0printtheremaindersinbackwardorder.Stackisanidealstructuretoimplementthisprocess.100250225212262321000100112AlgorithmdecimalToBinaryThisalgorithmreadsanintegerfromkeyboardandprintitsbinaryequivalent.Ituseastacktoreversetheorderof0’sand1’sproduce.1createStack(stack)2prompt(Enteradecimalnumbertoconverttobinary)3read(number)4loop(number>0)1digit=numbermodulo22pushOK=push(stack,digit)3if(pushOKfalse)1print(Stackoverflowalert)2quitalgorithm4endif5number=number/25endloopBinarynumbercreatedinstack,nowprintit.6loop(notemptyStack(stack))1popStack(stack,digit)2printdigit7endloop8returnenddecimalToBinaryAlgorithmDecimaltoBinaryThequotientTheremainder:0or1ParsingParsingisanylogicthatbreaksdataintoindependentpiecesforfurtherprocessing.Forexample:totranslateasourceprogramtomachinelanguageUnmatchedParenthesesExampleParenthesesmustbematchedinanalgebraicexpression.

Stackcanholdtheleftpartsofthesesegmentswhilescanninganexpressionorastatementforthelatercomparing.ParseparenthesesAlgorithmparseParensThisalgorithmreadsasourceprogramandparsesittomakesureallopening-closingparenthesesarepaired.1loop(moredata)1read(character)2if(characterisanopeningparenthesis)1pushStack(stack,character)3else1if(characterisclosingparenthesis)1if(emptyStack(stack))1print(Closingparenthesisnotmatchedalert)2else1popStack(stack,token)3endif2endif4endif2endloop3if(notemptyStack(stack))1print(Openingparenthesisnotmatchedalert)4endifendparseParensPostponementdatausagePostponementmeansdeferringdatausageuntilsomelaterpoint(orsomethinghappens).InfixtopostfixtransformationInfix:a+bPrefix:+abPostfix:ab+High-levellanguageusetheinfixconvertittopostfixManualtransformationFullyparenthesizetheexpressionusinganyexplicitparenthesesChangingallinfixnotationsineachparenthesistopostfixnotation,startingfromtheinnermostexpressionsRemoveallparentheses.ExamplesofmanualtransformationA+B*C(A+(B*C))(A+(BC*))(A(BC*)+)ABC*+(A+B)*C+D+E*F-G(((((A+B)*C)+D)+(E*F))-G)(((((AB+)C*)D+)(EF*)+)G-)AB+C*D+EF*+G-TransformexpressionwithstackA*BAB*1.ReadandcopythefirstoperandAtotheresult,weget“A”.2.Readtheoperator“*”andpushitintoastackforlateruse.3.ReadandcopythesecondoperandBtotheresult,wecanget“AB”.4.Finishscanningthesourceexpression,popuptheoperatorandconcatenateittotheresult,weget“AB*”Precedencerulethepriorityofanoperatorpushedintothestackishigherthantheoperatoratthetopofthestack-------pushitintothestack.theoperatoratthetopofthestackhasahigherprioritythanorequaltothecurrentoperator-------itispoppedandplacedintheoutputexpression.A+B*C

ABC*+CopyoperandAtooutputexpression.Pushoperator+intostack.CopyoperandBtooutputexpression.Pushoperator*intostack.(Priorityof*ishigherthan+)CopyoperandCtooutputexpression.Popoperator*andcopytooutputexpression.Popoperator+andcopytooutputexpression.Transformexpressionwithstack

(consideringpriority)A+B*C-D/EABC*+DE/-A+B*C-D/EInfixstackpostfix+B*C-D/EA

B*C-D/E+A*C-D/E+AB

C-D/E*+AB

-D/E*+ABC

D/E-ABC*+/E-ABC*+D

E/-ABC*+D

/-ABC*+DE

ABC*+DE/-Transformexpressionwithstack

(consideringparenthesis)A*(B+C/D)-EABCD/+*E-InfixStackPostfixA*(B+C/D)-E*(B+C/D)-EA(B+C/D)-E*A

B+C/D)-E(*A+C/D)-E(*AB

C/D)-E+(*AB/D)-E+(*ABC

D)-E/+(*ABC)-E/+(*ABCD-E*ABCD/+

E-ABCD/+*

-ABCD/+*E

ABCD/+*E-SummaryoftransforminganinfixtoapostfixexpressionReadeachiteminaninfixexpressionfromlefttorightuntiltotheendoftheinfixexpression1.Iftheitemisanopenparenthesis.2.Iftheitemisacloseparenthesis3.Iftheitemisanoperator4.Iftheitemisanoperand.5.AfterfinishingscanninginfixexpressionTransformingAlgorithmalgorithminToPostFix(formula)convertinfixformulatopostfix.PreFormulaisinfixnotationthathasbeeneditedtoensurethattherearenosyntacticalerrors.Postpostfixformulahasbeenformattedasastringaspostfix.Returnpostfixformula.1createStack(stack)2setpostfixtonullstring3looper=04loop(looper<sizeofformula)1token=formula[looper]//getatoken2if(tokenisopenparenthesis)1pushStack(stacktoken)3elseif(tokeniscloseparenthesis)1popStack(stack,token)2loop(tokenisnotopenparenthesis)1concatenatetokentopostfix2popStack(stack,token)3endloop

4elseif(tokenisoperator)1stackTop(stack,topToken)2loop(notemptyStack(stack)ANDpriority(token)<=priority(topToken))1popStack(stack,tokenOut)2concatenatetokenOuttopostfix3stackTop(stack,topToken)3endloop4pushStack(stack,token)5else1concatenatetokentopostfix6endif7looper=looper+15endloop6loop(notemptyStack(stack))1popStack(stack,token)2concatenatetokentopostfix7endloop8returnpostFixendinToPostFixTransformingAlgorithm(cont.)EvaluatingPostfixexpressionspostfixexpressioneasytoevaluatewithhelpofstack.Whilescanningapostfixexpressionpushalloperandsintoastackforlaterusewhenwemeetanoperator,wecanpopuptwooperandsandevaluatethemwiththeoperatorpushtheresultintothesamestackthefinalresultwillbethelastiteminthestack.2*(4+6)246+*20PosfixStack246+*46+*26+*42642+**1026+4=10

20ExampleofpostfixexpressionevaluationEvaluatingAlgorithmalgorithmpostFixEvaluate(expr)Thisalgorithmevaluatesapostfixexpressionandreturnsitvalue.Preavalidexpression.PostPostfixvaluecomputed.Returnvalueofexpression1exprsize=sizeofexpressionstring2createStack(stack)3index=04loop(index<exprsize)1if(expr[index]isoperand)1pushStack(stack,expr[index])2else1popStack(stack,operand2)2popStack(stack,operand1)3operator=expr[index]4value=calculate(operand1,operator,operand1)5pushStack(stack,value)3endif4index=index+15endloop6popStack(stack,result)7return(result)endpostFixEvaluateBacktrackingBacktrackingiswidelyusedinapplicationsrecordthe“footsteps”choicesat“crossway”tryrepeatedlyuntilyougetyourdestinationorgetthedestinationisunreachable.Stackisanidealstructuretoimplementrecordingandbacktracking“footsteps”and“branchways”asitsLIFOfeature.Thequestionnowiswhattoputintothestack.howtodistinguish“footstep”and“branchway”SimpleExampleofBacktracking(goalseeking)123412567891011131415161718StartnodeB12321B8B954B12321End76B8B954B12321End8B954B12321End1110954B12321Goal161514B171312321(a)(b)(c)(d)(e)(f)SeekgoalalgorithmalgorithmseekGoal(map)Thisalgorithmdeterminesthepathtoadesiredgoal.Preagraphcontainingthepathinitialized.PostPathtothegoalprinted1createStack(stack)2pMap=map.startFindpathandsavepathinstack3loop(pMapnotnullANDgoalNotFound)1if(pMapisgoal)1setgoalNotFoundtofalse2else1pushStack(stack,pMap)2if(pMapisabranchpoint)1loop(morebranchpoints)1createbranchPointnode2pushStack(stack,branchPoint)2endloop3endif4advancetonextnode3endif4endloopPrinttheresult5if(emptyStack(stack))1print(thereisnopathtoyourgoal)6else1print(Thepathtoyourgoalis:)2