数据结构英文版课件Chapter3.Stacks

DataStructuresUsingCNicklausWirth:DataStructuresUsingC2/432010-3-30DataStructuresUsingC3.Stacks◆Introduction◆Definition◆PrimitiveOperations◆AbstractDataType(ADT)◆Implementation◆ApplicationofStackStacks◆Astackisalistwiththerestrictionthatinsertionsanddeletionscanbeperformedinonlyoneposition,namely,theendofthelist,calledthetop.◆Pushoperationonastackisequivalenttoaninsertion,andPopoperationonastackisequivalenttoadeletionofthemostrecentlyinserteddataitem.◆StackareknownasLIFO(lastin,firstout)lists.3.1Introduction3.Stacks#Examples:stack4/43DataStructuresUsingC3.2Definition◆Astackisanorderedcollectionofdataelementswheretheinsertanddeletionoperationsoccuratoneendonly,calledthetopofthestack.Stackpushdownlist,LIFOlist(LastInFirstOut)……BottomTopRespresentationofastackItem1Item2Item3Item4pushpopTopBottomStack3.Stacks5/43DataStructuresUsingC3.2Definition(stackmodel)◆stackmodel:onlythetopelementisaccessible.Thegeneralstackmodelisthatthereissomeelementthatisatthetopofthestack,anditistheonlyelementthatisvisible.Fromthismodel,item4isthetopelement.WecanonlypopItem4,orpushanewitemafterItem4.Item1Item2Item3Item4pushpopTopBottomStack7/43DataStructuresUsingC3.3PrimitiveOperations(1)push(stack,item):insertanelement;(2)pop(stack):removinganelement;(3)peep(stack):determiningthetopitemwithoutremovingit;peep(stack)={i=pop(stack),push(stack,i)};(4)empty(stack);(5)full(stack);◆Beforeusingthestack:(1)Initialthesizeofstack;(2)initializethevariablewhichpointsthetopelement.3.Stacks#Examples:push,popoperationsTopTopToppoppushchangeTopthenpushdatapopdatathenchangeTop3.Stacks8/43DataStructuresUsingC44332255443322443322TopTopToppush:TopTopToppop:9/43DataStructuresUsingC3.Stacks443322443322554433225544332244332244332210/43DataStructuresUsingC3.4AbstractDataType(ADT)AbstractDataType(ADT)iskeywordusedinaprogramminglanguagetospecifytheamountofmemoryneededtostoredataandthetypeofdatathatwillbestoredinthememorylocation.◆ADTforstack(1)push()(or)put(or)insertsnewitemonthetopofstack;(2)pop()removesandreturntopitemofstack;(3)top()verifiesthetopitemofstack.3.Stacks3.4AbstractDataType(ADT)1.StackDeclarations--arrayimplementation#defineMAX50typedefstruct{ElemTypedata[MAX];inttop;}SqStack;topbottomPopPushana1a2…3.4AbstractDataType(ADT)2.StackDeclarations–linkedlistimplementationtypedefstructnode{ElemTypedata;structnode*link;}LinkedStack;3.4Implementation◆Usinganarray◆Usingalinkedlist◆alinkedlistismoreefficientthanarray◆Arrayimplementationofastack◆Advantages:simple◆Disadvantages:(a)possiblewastageofmemory;(b)Thereislimitationinstoringtheitems;(c)Insertanddeletionoperationsinvolvemoredatamovements.firstelementToplastelementMaximumlength3.Stacks13/43DataStructuresUsingC#Examples:insert(intitem){if(top=n){printf(“StackFull”);return;};top=top+1;data[top]=item;return;}delete(){if(top0){printf(“StackEmpty”);return;}item=data[top];printf(“Deleteditemis%d”,item);getch();top=top-1;return;}3.Stacks14/43DataStructuresUsingC◆Linkedlistimplementationofastack◆Advantages:(a)needn’tfixedsize;(b)insertanddeletionoperationsdoesn’tinvolvemoredatamovements;(c)nowastageofmemory.◆Disadvantages:pointerinvolvedforeachnode.firstelementpushedlastelementpushedTop15/43DataStructuresUsingCBottomAlinkerpointingtothefirstorthelastelementcanbedefined.3.StacksdatapointerdatapointerdataNULL#Examples:voidpush(intitem){structnode*temp;temp=(structnode*)malloc(sizeof(structnode));if(temp==NULL)printf(“\nStackisfull.”);temp-data=item;temp-link=top;top=temp;}structnode{intd;structnode*link;};structnode*top;//recordthetopnodeofstack3.Stacks16/43DataStructuresUsingC17/43DataStructuresUsingCintpop(){structnode*temp;intitem;if(top==NULL){printf(“\nStackisempty.”);returnNULL;}temp=top;item=temp-data;top=top-link;free(temp);returnitem;}#Examples:3.StacksExercise:Howtoreverseasequenceandoutputit?Forexample:Asequence:1,2,3,4,5,6,7,8;Wewanttooutputitinreversedorder.Pleaseusestackstructuretodoit.C.X.Deng理学院物理系19/432010-3-30DataStructuresUsingC3.5ApplicationofStack◆Infixtopostfixconversion◆Evaluationofarithmeticexpressions◆Decimaltobinaryconversion◆Functioncallsusingstack◆Computingthefactorial3.StacksC.X.Deng理学院物理系◆Infixtopostfixconversion#Examples:#:A+B*C/D-E^F*G#:((A+B)*((C/D)-(E^(F*G))))◆Notationrepresentinganarithmeticexpression:(1)infix:operandoperatoroperand(2)prefix:operatoroperandoperand(3)postfix:operandoperandoperatormoreadvantage(usingstackoperation)#Examples:3.StacksA+((B*C)/D)-((E^F)*G)20/432010-3-30DataStructuresUsingCinfix:A+B*G/Bprefix:+AB*EGpostfix:AB+CD-C.X.Deng理学院物理系◆RULE:infixpostfix(a)Fullyparenthesizetheinfixexpression;(b)MovealloperatorstotheircorrespondingRIGHTparenthesis;(c)Removealltheparenthesis.#Example:((A+((B^C)-D))*(E-(A/C)))((A+((B^C)–D))*(E-(A/C)))((A((BC^D-+(E(AC/-*ABC^D-+EAC/-*3.Stacks21/432010-3-30DataStructuresUsingCC.X.Deng理学院物理系(a)Fullyparenthesizetheinfixexpressionl;(b)MovealloperatorssothattheyreplacetheircorrespondingLEFTparenthesis;(c)Removealltheparenthesis.#Example:((A+((B^C)-D))*(E-(A/C)))((A+((B^C)–D))*(E-(A/C)))*+A-^BC)D))-E/AC)))*+A-^BC