【精品数据结构】queue

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

1、Chapter6Queue6.1DefinitionDefinition:Aqueueisalinearlistinwhichadditionsanddeletionstakeplaceatdifferentends.Itisalsocalledafirst-in-first-outlist.Theendatwhichnewelementsareaddediscalledtherear.Theendfromwhicholdelementsaredeletediscalledthefront.6.1DefinitionSamplequeuesfron

2、trearfrontrearfrontrearABCBCBCDDeleteAAddD6.2ADTAbstractDataTypeQueue{instancesorderedlistofelements;oneendiscalledthefront;theotheristherear;operationsCreate():Createanemptyqueue;IsEmpty():Returntrueifqueueisempty,returnfalseotherwise;IsFull():returntrueifqueueisfull,returnfa

3、lseotherwise;6.2ADTFirst():returnfirstelementofthequeue;Last():returnlastelementofthequeue;Add(x):addelementxtothequeue;Delete(x):deletefrontelementfromthequeueandputitinx;}6.3formula-basedrepresentationthequeuesize=rear+1;anemptyqueuehasrear=-1ABC……Queue:frontrearMaxsize-1[0]

4、[1][2][n-1]6.3formula-basedrepresentationToaddanelement:rear=rear+1;queue[rear]=x;Todeleteanelement:twomethods:1)front=front+1;O(1)2)shiftthequeueonepositionleft.O(n)6.3formula-basedrepresentationFigure6.3frontrearfrontrearfrontrearABC…BC…BCD…6.3formula-basedrepresentationFigu

5、re6.4…ABCDEFrontrearFreespace6.3formula-basedrepresentationAsthefigure6.4shows,eachdeletioncausesfronttomoverightby1So,therewillbetimeswhenrear=maxsize-1andfront>0Atthesetimesthequeueisnotfull,thereisspaceattheleftendofit6.3Formula-basedrepresentationAnotherwayistouseacircular

6、arraytorepresentaqueueCBAfrontrearDAddtionCBAfrontrear6.3Formula-basedrepresentationdeletiondeletionCBAfrontDrearCBfrontrearDA6.3Formula-basedrepresentationInacircularqueue:frontpointstoonepositionbeforethefirstelementinthequeueAqueueisemptyifffront==rearTheinitialconditionfro

7、nt=rear=0definesaninitiallyemptyqueue6.3Formula-basedrepresentationHowcanwedistinguishbetweenanemptyqueueandafullqueue?ThemaxnumberofelementsinaqueueactuallyismaxsizeAqueueisfulliff(rear+1)%maxsize==frontAqueueifemptyifffront==rear6.3Formula-basedrepresentationFormula-basedcla

8、ssqueue(program6.1)templateclassQueue{//FIFOobjectspu