【精品数据结构】stack

《【精品数据结构】stack》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter5Stack5.1definitionofstackDefinition:Astackisalinearlistinwhichinsertionsanddeletionstakeplaceatthesameend.Thisendiscalledthetop.Theotherendofthelistiscalledthebottom.ItisalsocalledaLIFO(last-in-first-out)list.5.1definitionofstackFigure5.1stackconfigurationsEtopDtopDCCBBBtopAb

2、ottomAbottomAbottom5.2ADTstackAbstractDataTypeStack{instanceslinearlistofelements;oneendiscalledthebottom;theotheristhetop;operationsCreate():Createanemptystack;IsEmpty():Returntrueifstackisempty,returnfalseotherwise5.2ADTstackIsFull():Returntrueifstackiffull,returnfalseotherwise;Top()

3、:returntopelementofthestack;Add(x):addelementxtothestack;Delete(x):Deletetopelementfromstackandputitinx;}5.3Formula-basedRepresentationWemayusetheFormula-basedrepresentationwhenTop=-1isemptystackstack012topmaxtop-15.3Formula-basedRepresentationFormula-basedclassStacktemplateclass

4、Stack{//LIFOobjectspublic:Stack(intMaxStackSize=10);~Stack(){delete[]stack;}boolIsEmpty()const{returntop==-1;}boolIsFull()const{returntop==MaxTop;}5.3Formula-basedRepresentationTTop()const;Stack&Add(constT&x);Stack&Delete(T&x);Private:inttop;//currenttopofastackintMaxTop;//maxvalue

5、fortopT*stack;//elementarray};5.3Formula-basedRepresentation1)constructorStacktemplateStack::Stack(intMaxStackSize){//stackconstructorMaxTop=MaxStackSize-1;stack=newT[MaxStackSize];top=-1;}5.3Formula-basedRepresentation2)getthetopelementTemplateTStack::Top()const{//

6、returntopelementif(IsEmpty())throwOutOfBounds();elsereturnstack[top];}5.3Formula-basedRepresentation3)pushanelementTemplateStack&Stack::Add(constT&x){//Addxtostackif(IsFull())throwNoMem();stack[++top]=x;return*this;}5.3Formula-basedRepresentation4)popanelementtemplate

7、T>Stack&Stack::Delete(T&x){//deletetopelementandputitinxif(IsEmpty())throwOutOfBounds();x=stack[top--];return*this;}5.3Formula-basedRepresentationItiswastefulofspacewhenmultiplestacksaretocoexistWhenthere’sonlytwostacks,wecanmaintainspaceandtimeefficiencybypeggingth