Stacks

3STACKS3.1INTRODUCTIONAstackisalineardatastructure.Itisveryusefulinmanyapplicationsofcomputerscience.Itisalistinwhichallin-sertionsanddeletionsaremadeatoneend,calledthetopofthestack.Someoftheanalogiesusedtovisualizethisdatastructurearea)StackofTrays(or)PlatesPlacedonaTableHere,oneplateisplacedontopofanother,thuscreatingastackofplates.Suppose,apersontakesaplateoffthetopofthestackofplates.Theplatemostrecentlyplacedonthestackisthefirstonetobetakenoff.Thebottomplateisthefirstoneplacedonthestackandthelastonetoberemoved.b)AnotherFamiliarExampleofaStackisaRailwayStationforShuntingCarsInthisexample,thelastrailwaycarplacedonthestackisthefirsttoleave.c)ShipmentinaCargoFortheshipmentofgoods,theyhavetobeloadedintoacargo.Duringunloading,theyareunloadedexactlyintheoppositeorderastheyareloaded,thatis,thegoodswhichareloadedlastshouldbeunloadedfirst.3.2DEFINITIONAstackisanorderedcollectionofhomogeneousdataelementswheretheinsertionanddeletionoperationsoccuratoneendonly,calledthetopofthestack.Fig.3.3showstheschematicdiagramofastack.ThealternativerepresentationofastackisgiveninFigure.3.4.Othernamesforastackarepushdownlist,andLIFO(or)LastInFirstOutlist.Thestackallowsaccesstoonlyoneitem,i.e.,thelastiteminserted.Intheschematicdia-gramofastack,afterinsertingItem4intothestack,itactsasthetopmostelement.Itwillberemovedfirst.TheveryfirstitemthatwasinsertedintothestackisItem1.Itwillberemovedasthelastitem.Fig.3.1StackofplatesCargoStackFig.3.2Arailwayshuntingsystem—represenationofastack69Stacks3.3PRIMITIVEOPERATIONSTheprimitiveoperationsthatcanbeperformedonastackaregivenbelow:1.Insertinganelementintothestack(PUSHoperation)2.Removinganelementfromthestack(POPoperation)3.Determiningthetopitemofastackwithoutremovingitfromthestack(PEEPoperation)ThesyntaxusedforthePUSHoperationisPUSH(stack,item)wherestackisthenameofthestackintowhichtheitemspecifiedasthesecondargumentisplacedatthetoppositionofthestack.ThesyntaxusedforthePOPoperationisPOP(stack)wherestackisthenameofthestackfromwhichtheitemhastoberemoved,i.e.,theelementatthetopmostpositionofthestackisremoved.ConsiderastackstructureasgiveninFigure3.5(a).Afterinserting(PUSH)anelement(viz,55)intothisstack,thecontentsofthestackafterthePUSHoperationisgiveninFigure3.5(b).SupposeifthePOPoperationisspecifiedasPOP(st).ThenthecontentofthestackcanbevisualizedasinFigure3.5(c).PushPopTopItem4Item3Item2Item1BottomFig.3.3SchematicdiagramofastackBottomTopFig.3.4AlternativerepresentationofastackTop443322Fig.3.5(a)Fig.3.5(b)Fig.3.5(c)Top443322Thatis,theelementpointedoutbyTopwillberemovedandthenTopwillbedecrementedby1.Soitpointstheitemplacedbelowtheremoveditem.Itisalsopos-sibletoverifytheitemplacedatthetopofthestackwithoutremovingit.Thisopera-tioniscalledPEEP.ThesyntaxusedforthisoperationisTop4433225570DataStructuresUsingCPEEP(st)ThisoperationisthecombinationofPOPandPUSH.Itisequivalenttothefollow-ingstatements:i=POP(st)PUSH(st,i)POPremovestheitemfromthepositionpointedoutbyTop.Itisinvariablei.ThenusingthePUSHinstructionweareinsertingthesameitemiintothestack.Nowthevariableihasthevalueinthetopmostpositionofthestack.3.3.1OtherOperationsTheotheroperationsthatcanbeperformedonthestackarethefollowing:1)CheckingtheEmptinessoftheStackItisnotpossibletopopelementsfromtheemptystack.SoatthetimeofissuingthePOPoperation,thestackshouldbenon-empty.ThesyntaxusedtochecktheemptyconditionofthestackisEmpty(stack)ItreturnsTRUEifthestackisemptyandFALSEotherwise.2)CheckingtheFullConditionoftheStackIfthestackisfull,itisnotpossibletopushelementsintoit.SobeforeissuingthePUSHoperation,makesurethatthestackisnotfull.ThesyntaxusedtocheckthefullconditionofthestackisFull(stack)ItreturnsTRUEifthestackisFullandFALSEotherwise.3)BeforeUsingtheStack,theSizeoftheStackandtheVariablewhichPointstheTopElementoftheStackhavetobeInitialized3.4ANABSTRACTDATATYPE(ADT)AnAbstractDataType(ADT)isakeywordusedinaprogramminglanguagetospecifytheamountofmemoryneededtostoredataandthetypeofdatathatwillbestoredinthatmemorylocation.However,anADTdoesnotspecifyhowmanybytestoreserveforthedata,becausethenumberofbytesreservedforanADTvariesfromoneprogramminglanguagetoanother.ADTforStackThisisaLast-InFirst-Outstructure.Itemscanonlybeinsertedandremovedfromthetopofthestack.TheADTforstackarethefollowing:1)Push()(or)Put(or)insertnewitemontopofstack2)Pop()removeandreturntopitemofstack3)Top()Verifiesthetopitemofstack3.5IMPLEMENTATIONAstackcanbeimplementedinanyoneofthefollowingtwoways:1.Usinganarray2.Usingalinkedlist71Stacks3.5.1ArrayImplementationofStacksInthearrayimplementationofastack,astackcangroweithertowardsthehigh-indexedendofthearray(or)towardsthelow-indexedendofthearray.ThearrayimplementationofthestackwhichgrowstowardsthelowindexedendofthearrayisshowninFig.3.6.Thearrayimplementationrequiresthefollowing.1)Anarray2)AvariabletoptoholdthetopmostelementofthestackHere,thestackisoffixedsize.Thismeansthatsomemaximumlimitisspecifiedforstoringtheelementsintothestack.Oncethemaximumlimitisreached,itisnotpossibletostoretheelementsintoit.InFigure3.6,thelow-indexedendofthearrayholdsthelastelement