數(shù)據(jù)結(jié)構(gòu)英文版課件：chapter 3 Queues

Chapter3QueuesAqueueisadatastructuremodeledafteralineofpeoplewaitingtobeserved.Alongwithstacks,queuesareoneofthesimplestkindsofdatastructures.Thischapterdevelopspropertiesofqueues,studieshowtheyareapplied,andexaminesdifferentimplementations.TheimplementationsillustratetheuseofderivedclassesinC++andtheimportantobject-orientedtechniqueofclassinheritance.隊列是一個模擬日常生活中人們排隊等候服務(wù)的數(shù)據(jù)結(jié)構(gòu)。與棧一樣，隊列是最簡單的數(shù)據(jù)結(jié)構(gòu)。本章描述了隊列的性質(zhì)、應(yīng)用及不同的實現(xiàn)方法。描述了C++中派生類的使用和類的繼承中重要的面向?qū)ο蠹夹g(shù)。ContentPointsDefinitionsImplementationsofQueuesCircularImplementationofQueuesinC++

DemonstrationandTestingApplicationofQueues:Simulation

DefinitionsQueue：wesimilarlydefineaqueuetobealistinwhichalladditionstothelistaremadeatoneend,andalldeletionsfromthelistaremadeattheotherend.Queuesarealsocalledfirst-in,first-outlists,orFIFO（先進先出表）

forshort.Applications:acomputersystem,queuesoftaskswaitingforprinter,diskstorage,withmultitasking，useoftheCPU.Front:thefirst

entryinthequeuerear:thelastentryinthequeue23411122front(head)rear(tail)QueueOperations

（隊列的基本操作）Asinourtreatmentofstacks,weshallimplementqueueswhoseentrieshaveagenerictype,whichwecallQueue_entry.Queue::Queue();postcondition:TheQueuehasbeencreatedandisinitializedtobeempty.Error_codeQueue::append(constQueue_entry&x);postcondition:Ifthereisspace,xisaddedtotheQueueasitsrear.OtherwiseanError_codeofoverflowisreturned.Error_codeQueue::serve();postcondition:IftheQueueisnotempty,thefrontoftheQueuehasbeenremoved.OtherwiseanError_codeofunderflowisreturned.QueueOperations

（隊列的基本操作）Error_codeQueue::retrieve(Queue_entry&x)const;postcondition:IftheQueueisnotempty,thefrontoftheQueuehasbeenrecordedasx.OtherwiseanError_codeofunderflowisreturned.（取隊頭元素）boolQueue::empty()const;postcondition:ReturntrueiftheQueueisempty,otherwisereturnfalse.QueueOperations

（隊列的基本操作）classQueue{public:Queue();boolempty()const;Error_codeappend(constQueue_entry&x);Error_codeserve();Error_coderetrieve(Queue_entry&x)const;//Additionalmemberswillrepresentqueuedata.};QueueOperations

（隊列的基本操作）RemovefrontorunderflowRecordfrontasxorunderflowpushpopfrontAddxtorearoroverflowExtendedQueueOperations

ExtendedQueueOperations:fullclearsizeserve_and_retrieveclassQueuemethods:Queue(constructor)appendserveretrieveemptydatamembersclassQueueclassExtended_Queuemethods:Extended_queue(constructor)appendserveretrieveemptyfullclearsizeserve_and_retrievedatamembersadditionaldatamembersinheritanceBaseclassDerivedclassExtendedQueueOperations

classExtended_queue:publicQueue{public:boolfull()

const;intsize()

const;voidclear();Error_codeserve_and_retrieve(Queue_entry&item);};ExtendedQueueOperations

ThenewoperationsforourclassExtended_queuehavethefollowingspecifications.boolExtended_queue::full()const;postcondition:ReturntrueiftheExtended_queueisfull;returnfalseotherwise.voidExtended_queue::clear();postcondition:AllentriesintheExtended_queuehavebeenremoved;itisnowempty.ExtendedQueueOperations

intExtended_queue::size()const;postcondition:ReturnthenumberofentriesintheExtended_queue.Error_codeExtended_queue::serve_and_retrieve(Queue_entry&item);postcondition:ReturnunderflowiftheExtended_queueisempty.OtherwiseremoveandcopytheitematthefrontoftheExtended_queuetoitemandreturnsuccess.ExtendedQueueOperations

EveryA“isa”BclassAisderivedfromclassBEveryA“hasa”BclassAhasadatamemberoftypeBTherelationshipbetweentheclassExtended_queueandtheclass

Queueisoftencalledanis-a

relationship.ThisisbecauseeveryExtended_queueobject“isa”Queueobjectwithotherfeatures—namely,themethodsserve_and_retrieve,full,size,andclear.CconsiderC++classesthatmightbeusedinaprogramtomanageauniversitybudget.SomeoftheseclassesareUniversity,Student,University_president,andPerson.Everystudentisaperson,andthereforewemightcreatetheclassStudentasderivedfromtheclassPersontoreflecttheis-arelationshipbetweenthecorrespondingconcepts.TheclassUniversity_presidentcouldalsobeimplementedasaderivedclassofPersontoreflectanotherobviousis-arelationship.TheclassesUniversityandUniversity_presidentdonotreflectanis-arelationship,howevertheclassesarerelated,becauseeveryuniversitydoeshaveapresident.Weshallsaythattheseclassesreflectahas-arelationship,andinanimplementationwewouldmakethisrelationshipclearbylayeringtheclasses,thatis,byincludingadatamemberof

typeUniversity_presidentinthedefinitionoftheclassUniversity.OutlineQueueConceptPropertyBasicoperationsClassqueueClassextended_queueIMPLEMENTATIONSOFQUEUES

ContiguousimplementationThephysicalmodelimplementationLinearimplementationCirculararrayimplementationLinkedimplementation(Wewilldiscussinthenextchapter)ContiguousimplementationThebasicwayisthesame.Wecreateaqueueinmemorybysettingupanarraytoholdtheentries.Tofacilitatetheoperations,wemustkeeptrackofthefrontandtherearofthequeue.(基本方法是相同的，我們使用一個數(shù)組來存放隊列中的元素，為了方便操作，我們還保存了隊列中的隊頭和隊尾位置。)1.ThePhysicalModel（物理模型）

Thestrategy（策略）istokeepthefrontofthequeuealwaysinthefirstlocationofthearray.Contiguousimplementation423111front2344rearrearToremoveanentryfromthequeue,however,wouldbeveryexpensiveindeed.(出隊時，隊列中所有元素都向前移動一個位置)NotapracticalwayAnentrycanbeappendedtothequeuesimplybyincreasingtherearbyoneandputtingtheentryinthatlocation.(入隊時元素添加到最后，隊尾指示器增1)2.LinearImplementation（隊列的順序?qū)崿F(xiàn)）

Toappend

anentrytothequeue,wesimplyincreasetherearbyoneandputtheentryinthatposition.Toserveanentry,wetakeitfromthepositionatthefrontandthenincreasethefrontbyone.Job1Job2Job3Job4Job5Job61012345appendJob1appendJob2appendJob3serveJob1appendJob4appendJob5appendJob6serveJob2appendJob7

Problem:nottrueoverflow(假溢出）happensfault:discardedspaceThismethodhasamajordefect（缺點）:Boththefrontandrearindicesareincreasedbutneverdecreased.Asthequeuemovesdownthearray,thestoragespaceatthebeginningofthearrayisdiscarded（丟棄）

andneverusedagain.Advantage:forapplicationswherethequeueisregularlyemptied,thenatatimewhenthequeueisempty,thefrontandrearcanbothberesettothebeginningofthearray,andthesimpleschemeofusingtwoindicesandstraight-linestoragebecomesaveryefficientimplementation.inefficientuseofspaceAlimitedway3.CircularArray（循環(huán)隊列）Inconcept,wecanovercometheinefficientuseofspacesimplybythinkingofthearrayasacircleratherthanastraightline.(可以克服假溢出的問題),nowweneednotworryaboutrunningoutofspaceunlessthearrayisfullyoccupied,inwhichcasewetrulyhaveoverflow.(除非數(shù)組空間真正耗盡真溢出，否則不需擔(dān)心假溢出。)Job1Job2Job3Job4Job5Job61012345Job7appendJob7[5][4][3][2][1][0]Job3Job4Job5Job6Job7

ImplementationofCircularArrays（循環(huán)隊列的實現(xiàn)）Anarrayholdalltheentriesandthefirstlocationissupposedthenextofthelast;一個被認為是首尾相連的數(shù)組frontandrear;front和rear分別指示著隊頭和隊尾元素的位置Howtoappendanentrytothequeue?Howtoserveanentryfromthequeue?Howtoinitthefrontandrear?Job1Job2Job31012appendJob2appendJob3front=0rear=0rear=2345HowtoappendanentryWhenanentryisappendedtothequeue,rear++;隊尾指示器rear增1，front沒有變化rear=1Job1Job2Job3Job4Job5Job61012345appendJob7Job7front=2rear=5rear=0HowtoappendanentryUsuallywhenanentryisappendedtothequeue,rear++;Butwhentherearisthelastposition:maxqueue-1;rear=0;rear=((rear+1)==maxqueue)?0:(rear+1);orrear=(rear+1)%maxqueue;HowtoseveranentryButwhenthefrontisthelastposition:maxqueue-1;front=0;front=((front+1)==maxqueue)?0:(front+1);orfront=(front+1)%maxqueue;serveJob3serveJob4serveJob5serveJob6Job1Job2Job3Job4Job5Job6Job7front=2rear=0front=31012345front=4front=5front=0Usuallywhenanentryisservedfromthequeue,front++;AttentionWhenanentryisappendedtothequeue,wemustjudgeifthequeueisfull.(overflow)

入隊需判別隊滿；Whenanentryisseveredfromthequeuewemustjudgeifthequeueisempty.(underflow)出隊需判別隊空。Job11012front=0rear=0345Howtoinitthefrontandtherearforanemptyqueue?front=0;rear=-1;orfront=0;rear=maxqueue-1;經(jīng)過一次入隊后，可以得到這個狀態(tài)。Job1012front=0rear=0345severJob1front=0[5][4][3][2][1][0]rear=0Job1front=1appendJob2隊空時，rear和front相差1個位置。在這個例子中，front=1，rear=0；Job2rear=1appendJob3，4，5，6Job3Job4Job5Job6rear=5appendJob7rear=0Job7隊滿時，rear和front也相差1個位置。在這個例子中，front=1，rear=0；EmptyandFullBoundaryConditions存在問題:如何區(qū)別隊空和隊滿!IMPLEMENTATIONSOFQUEUES

PossibleSolutions（解決方法）emptyposition（少用一個空間）

Oneistoinsistonleavingoneemptypositioninthearray,sothatthequeueisconsideredfullwhentherearindexhasmovedwithintwopositionsofthefront.anewvariable

（引入一個變量）

Asecondmethodistointroduceanewvariable.ThiscanbeaBooleanflagthatissetastruewhentherearcomesjustbeforethefronttoindicatethatthequeueisfulloranintegervariablethatcountsthenumberofentriesinthequeue.specialvalues（采用特殊值）

Thethirdmethodistosetoneorbothoftheindicestosomevalue(s)thatwouldotherwiseneveroccurinordertoindicateanempty(orfull)queue.Forexample,anemptyqueuecouldbeindicatedbysettingtherearindexto-1.IMPLEMENTATIONSOFQUEUES

SummaryofImplementationsTosummarizethediscussionofqueues,letuslistallthemethodswehavediscussedforimplementingqueues.

Thephysicalmodel:

alineararraywiththefrontalwaysinthefirstpositionandallentriesmovedupthearraywheneverthefrontisremoved.Thisisgenerallyapoormethodforuseincomputers.

Alineararray

withtwoindicesalwaysincreasing.Thisisagoodmethodifthequeuecanbeemptiedallatonce.

Acirculararray

withfrontandrearindicesandonepositionleftvacant.IMPLEMENTATIONSOFQUEUES

SummaryofImplementationsAcirculararray

withfrontandrearindicesandaflagtoindicatefullness(oremptiness).

Acirculararray

withfrontandrearindicesandanintegervariablecountingentries.

Acirculararray

withfrontandrearindicestakingspecialvalues

toindicateemptiness.CIRCULARIMPLEMENTATIONOFQUEUESINC++（循環(huán)隊列實現(xiàn)）Theimplementationinacirculararraywhichusesacountertokeeptrackofthenumberofentriesinthequeuebothillustratestechniquesforhandlingcirculararraysandsimplifiestheprogrammingofsomeoftheextended-queueoperations.Weshalltakethequeueasstoredinanarrayindexedwiththerange0to(maxqueue-1)CIRCULARIMPLEMENTATIONOFQUEUESINC++constintmaxqueue=10;//smallvaluefortestingclassQueue{public: Queue(); boolempty()const; Error_codeserve(); Error_codeappend(constQueue_entry&item); Error_coderetrieve(Queue_entry&item)const;protected: intcount; intfront,rear; Queue_entryentry[maxqueue];};CIRCULARIMPLEMENTATIONOFQUEUESINC++Queue::Queue()/*Post:TheQueueisinitializedtobeempty.*/{ count=0; rear=maxqueue-1; front=0;}boolQueue::empty()const/*Post:ReturntrueiftheQueueisempty,otherwisereturnfalse.*/{ returncount==0;}CIRCULARIMPLEMENTATIONOFQUEUESINC++Error_codeQueue::append(constQueue_entry&item)/*Post:itemisaddedtotherearoftheQueue.IftheQueueisfullreturnanError_codeofoverflowandleavetheQueueunchanged.*/{ if(count>=maxqueue)returnoverflow; count++; rear=((rear+

1)==maxqueue)?0:(rear+

1); entry[rear]=item; returnsuccess;}CIRCULARIMPLEMENTATIONOFQUEUESINC++.Error_codeQueue::serve()/*Post:ThefrontoftheQueueisremoved.IftheQueueisemptyreturnanError_codeofunderflow.*/{ if(count<=0)returnunderflow; count--; front=((front+1)==maxqueue)?0:(front+

1); returnsuccess;}CIRCULARIMPLEMENTATIONOFQUEUESINC++Error_codeQueue::retrieve(Queue_entry&item)const/*Post:ThefrontoftheQueueretrievedtotheoutputparameteritem.IftheQueueisemptyreturnanError_codeofunderflow.*/{ if(count<=0)returnunderflow; item=entry[front]; returnsuccess;}intExtended_queue::size()const/*Post:ReturnthenumberofentriesintheExtended_queue.*/{ returncount;}1、Acircularqueuehastheprobleminwhichitisnoteasytodistinguishbetweenfullandemptyqueues.

Drawtwosituationstoillustratethispoint.

Thefrontandrearpointersshouldbeinthesamepositionineachsituation.2、Evaluatethefollowingsentenceifitistrueorfalseandsimplyexplainwhy?AqueueisaFILOdatastructure.

Anarraybasedqueueimplementationisusuallyimplementedasacircularqueue.

Anarraybasedqueueisbetterthanalinkedlistimplementationofaqueue.

IMPLEMENTATIONSOFQUEUES

（隊列的實現(xiàn)）.ThePhysicalModel（物理模型）

Onestrategy（策略）wouldbetokeepthefrontofthequeuealwaysinthefirstlocationofthearray.Thenanentrycouldbeappendedtothequeuesimplybyincreasingthecountershowingtherear,inexactlythesamewayasweaddedanentrytoastack.Toremoveanentryfromthequeue,however,wouldbeveryexpensiveindeed.rearfrontIMPLEMENTATIONSOFQUEUES

（隊列的實現(xiàn)）.

LinearImplementation（隊列的順序?qū)崿F(xiàn)）

Toappend

anentrytothequeue,wesimplyincreasetherearbyoneandputtheentryinthatposition.Toserveanentry,wetakeitfromthepositionatthefrontandthenincreasethefrontbyone.Job1Job2Job3Job4Job5Job6Job710123456appendJob1appendJob2appendJob3serveJob1appendJob4appendJob5appendJob6serveJob2appendJob7appendJob8rearfault:discardedspaceThismethodhasamajordefect（缺點）:Boththefrontandrearindicesareincreasedbutneverdecreased.asthequeuemovesdownthearray,thestoragespaceatthebeginningofthearrayisdiscarded（丟棄）

andneverusedagain.Advantage:forapplicationswherethequeueisregularlyemptied(suchaswhenaseriesofrequestsisallowedtobuilduptoacertainpoint,andthenataskisinitiatedthatclearsalltherequestsbeforereturning),thenatatimewhenthequeueisempty,thefrontandrearcanbothberesettothebeginningofthearray,andthesimpleschemeofusingtwoindicesandstraight-linestoragebecomesaveryefficientimplementation.IMPLEMENTATIONSOFQUEUES

（隊列的實現(xiàn)）.

CircularArrays（順序循環(huán)隊列）Inconcept,wecanovercometheinefficientuseofspacesimplybythinkingofthearrayasacircleratherthanastraightline.Atdifferenttimes,thequeuewilloccupydifferentpartsofthearray,butweneverneedworryaboutrunningoutofspaceunlessthearrayisfullyoccupied,inwhichcasewetrulyhaveoverflow.IMPLEMENTATIONSOFQUEUES

.[5][4][3][2][1][0][5][4][3][2][1][0][5][4][3][2][1][0]IMPLEMENTATIONSOFQUEUES

.

ImplementationofCircularArrays（循環(huán)隊列的實現(xiàn)）

Ournextproblemistoimplementacirculararrayasanordinarylinear(thatis,straight-line)array.Todoso,wethinkofthepositionsaroundthecircleasnumberedfrom0tomax-1,wheremaxisthetotalnumberofentriesinthecirculararray,andtoimplementthecirculararray,weusethesamenumberedentriesofalineararray.ThenmovingtheindicesisjustthesameasdoingmodulararithmeticWhenweincreaseanindexpastmax-1,westartoveragainat0.Thisislikedoingarithmeticonacircularclockface;thehoursarenumberedfrom1to12,andifweaddfourhourstoteno’clock,weobtaintwoo’clock.IMPLEMENTATIONSOFQUEUES

.CircularArraysinC++InC++,wecanincreaseanindexiofacirculararraybyusingtheternaryoperator?:

andwritingi=((i+1)==max)?0:(i+

1);Orwecanusethemodulusoperatorandwritei=(i+

1)%maxYoushouldchecktoverifythattheresultofthelatterexpressionisalwaysbetween0andmax-1.IMPLEMENTATIONSOFQUEUES

.BoundaryConditions（邊界條件）存在問題:如何區(qū)別隊空和隊滿？IMPLEMENTATIONSOFQUEUES

.PossibleSolutions（解決方法）emptyposition（少用一個空間）

Oneistoinsistonleavingoneemptypositioninthearray,sothatthequeueisconsideredfullwhentherearindexhasmovedwithintwopositionsofthefront.flag（設(shè)定標志位）

Asecondmethodistointroduceanewvariable.ThiscanbeaBooleanflagthatissetastruewhentherearcomesjustbeforethefronttoindicatethatthequeueisfulloranintegervariablethatcountsthenumberofentriesinthequeue.specialvalues（采用特殊值）

Thethirdmethodistosetoneorbothoftheindicestosomevalue(s)thatwouldotherwiseneveroccurinordertoindicateanempty(orfull)queue.Forexample,anemptyqueuecouldbeindicatedbysettingtherearindexto-1.IMPLEMENTATIONSOFQUEUES

.

SummaryofImplementationsTosummarizethediscussionofqueues,letuslistallthemethodswehavediscussedforimplementingqueues.

Thephysicalmodel:

alineararraywiththefrontalwaysinthefirstpositionandallentriesmovedupthearraywheneverthefrontisremoved.Thisisgenerallyapoormethodforuseincomputers.

Alineararray

withtwoindicesalwaysincreasing.Thisisagoodmethodifthequeuecanbeemptiedallatonce.

Acirculararray

withfrontandrearindicesandonepositionleftvacant.IMPLEMENTATIONSOFQUEUES

.SummaryofImplementationsAcirculararray

withfrontandrearindicesandaflagtoindicatefullness(oremptiness).

Acirculararray

withfrontandrearindicesandanintegervariablecountingentries.

Acirculararray

withfrontandrearindicestakingspecialvaluestoindicateemptiness.CIRCULARIMPLEMENTATIONOFQUEUESINC++（循環(huán)隊列實現(xiàn)）.Theimplementationinacirculararraywhichusesacountertokeeptrackofthenumberofentriesinthequeuebothillustratestechniquesforhandlingcirculararraysandsimplifiestheprogrammingofsomeoftheextended-queueoperations.Weshalltakethequeueasstoredinanarrayindexedwiththerange0to(maxqueue-1)CIRCULARIMPLEMENTATIONOFQUEUESINC++.constintmaxqueue=10;//smallvaluefortestingclassQueue{public: Queue(); boolempty()const; Error_codeserve(); Error_codeappend(constQueue_entry&item); Error_coderetrieve(Queue_entry&item)const;protected: intcount; intfront,rear; Queue_entryentry[maxqueue];};CIRCULARIMPLEMENTATIONOFQUEUESINC++.Queue::Queue()/*Post:TheQueueisinitializedtobeempty.*/{ count=0; rear=maxqueue-1; front=0;}boolQueue::empty()const/*Post:ReturntrueiftheQueueisempty,otherwisereturnfalse.*/{ returncount==0;}CIRCULARIMPLEMENTATIONOFQUEUESINC++Error_codeQueue::append(constQueue_entry&item)/*Post:itemisaddedtotherearoftheQueue.IftheQueueisfullreturnanError_codeofoverflowandleavetheQueueunchanged.*/{ if(count>=maxqueue)returnoverflow; count++; rear=((rear+

1)==maxqueue)?0:(rear+

1); entry[rear]=item; returnsuccess;}CIRCULARIMPLEMENTATIONOFQUEUESINC++.Error_codeQueue::serve()/*Post:ThefrontoftheQueueisremoved.IftheQueueisemptyreturnanError_codeofunderflow.*/{ if(count<=0)returnunderflow; count--; front=((front+1)==maxqueue)?0:(front+

1); returnsuccess;}CIRCULARIMPLEMENTATIONOFQUEUESINC++Error_codeQueue::retrieve(Queue_entry&item)const/*Post:ThefrontoftheQueueretrievedtotheoutputparameteritem.IftheQueueisemptyreturnanError_codeofunderflow.*/{ if(count<=0)returnunderflow; item=entry[front]; returnsuccess;}intExtended_queue::size()const/*Post:ReturnthenumberofentriesintheExtended_queue.*/{ returncount;}DEMONSTRATIONANDTESTING

Menu-drivendemonstrationprogramintmain()/*Post:Acceptscommandsfromuserasamenu-drivendemonstrationprogramfortheclassExtended_queue.Uses:TheclassExtended_queueandthefunctionsintroduction,get_command,anddo_command.*/{ Extended_queuetest_queue; introduction(); while(do_command(get_command(),test_queue));}DEMONSTRATIONANDTESTING

Menu-drivendemonstrationprogramDEMONSTRATIONANDTESTING

Menu-drivendemonstrationprogramDEMONSTRATIONANDTESTINGvoidhelp()/*Post:Ahelpscreenfortheprogramisprinted,givingthemeaningofeachcommandthattheusermayenter.*/{cout<<endl<<"Thisprogramallowstheusertoenteronecommand"<<endl<<"(butonlyone)oneachinputline."<<endl<<"Forexample,ifthecommandSisentered,then"<<endl<<"theprogramwillservethefrontofthequeue."<<endl<<endl<<"Thevalidcommandsare:"<<endl<<"A-Appendthenextinputcharactertotheextendedqueue"<<endlDEMONSTRATIONANDTESTING<<"S-Servethefrontoftheextendedqueue"<<endl<<"R-Retrieveandprintthefrontentry."<<endl<<"#-Thecurrentsizeoftheextendedqueue"<<endl<<"C-Cleartheextendedqueue(sameasdelete)"<<endl<<"P-Printtheextendedqueue"<<endl<<"H-Thishelpscreen"<<endl<<"Q-Quit"<<endl<<"Press<Enter>tocontinue."<<flush;charc;do{cin.get(c);}while(c!=‘\n’);}DEMONSTRATIONANDTESTINGbooldo_command(charc,Extended_queue&test_queue)/*Pre:crepresentsavalidcommand.Post:PerformsthegivencommandcontheExtended_queuetest_queue.Returnsfalseifc==‘q’,otherwisereturnstrue.Uses:TheclassExtended_queue.*/{boolcontinue_input=true;Queue_entryx;DEMONSTRATIONANDTESTINGswitch(c){case’

r’: if(test_queue.retrieve(x)==underflow) cout<<"Queueisempty."<<endl; else cout<<endl<<"Thefirstentryis:"<<x<<endl; break;case’q’: cout<<"Extendedqueuedemonstrationfinished."<<endl; continue_input=false; break;//Additionalcaseswillcoverothercommands.}returncontinue_input;}1、Acircularqueuehastheprobleminwhichitisnoteasytodistinguishbetweenfullandemptyqueu