Data Structure(C++) Slides-ENG 数据结构课件Chapter-3-Stack-and-Queue-English

2026DataStructures

Chapter3StackandQueueStackandItsApplications:Arestrictedlinearlist:LastIn,FirstOutApplicationsofstackContentsQueueandItsApplications:Arestrictedlinearlist:FirstIn,FirstOutStackandItsApplications3.13.1DefinitionofStackInsertionpositions:1ton+1Deletionpositions:1tonLinearlistInsertionposition:n+1Deletionposition:nStackBottomTopStack:alinearlistinwhichinsertionanddeletionarerestrictedtooneendonly.Stacktop(top):theendatwhichinsertionanddeletionareallowedStackbottom(bottom):theotherendofthestackDataStructuresandAlgorithmsDataStructuresChapter3

StackandQueue（a1,…,an-1,an）OperationalCharacteristicsofStackInsertion:push,pushintostackDeletion:pop,popoutofstackaInsertDeletebcOperationalcharacteristicofstack:(LastInFirstOut,LIFO)Emptystack:astackcontainingnodataelementsIfapopoperationisperformednow,whichelementwillbepopped?3.1TopDataStructuresandAlgorithmsDataStructuresChapter3

StackandQueueExamplesofStack3.1Whataresomereal-lifeexamplesofstacks?AjarAstackofbowlsInstallationofcertainpartsParenthesesDataStructuresandAlgorithmsDataStructuresChapter3

StackandQueueLogicalStructureofStack3.1Example:Threeelementsarepushedintoastackintheordera,b,c,andeachelementmaybepushedonlyonce.Whichofthefollowingarepossiblepopsequences?1)c,b,a;2)b,c,a3)c,a,b4)b,a,c5)a,b,c6)a,c,bBottomTopabTopcTopPopsequence:Case1:1)OKDataStructuresandAlgorithmsDataStructuresChapter3

StackandQueueLogicalStructureofStack3.1Example:Threeelementsarepushedintoastackintheordera,b,c,andeachelementmaybepushedonlyonce.Whichofthefollowingarepossiblepopsequences?

1)c,b,a;

2)b,c,a

3)c,a,b

4)b,a,c

5)a,b,c

6)a,c,babcPopsequence:Case2:2)OKWhatabout3),4),5),and6)?Forndistinctelementspushedintoastackinsequence,howmanypossiblepopsequencesarethere?P60DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueAbstractDataTypeDefinitionofStackADTStackDatamodelBasicoperationsendADTTheelementsinastackareofthesametypeandfollowtheLastIn,FirstOutproperty;adjacentelementshavepredecessorandsuccessorrelationships.InitStack:initializethestackDestroyStack:destroythestackPush:pushanelementontothestackPop:popanelementfromthestackGetTop:getthetopelementEmpty:determinewhetherthestackisemptyComparedwithotherdatastructures,thebasicoperationsofastackarefixed.3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueStorageStructureofStack3.1StoragestructureofstackStoragestructureoflinearlistSequentialstorageLinkedstorageAstackisaspecialtypeoflinearlist,soitsstoragestructurealsoincludessequentialstorageandlinkedstorage.SequentialstorageLinkedstorageBecausestackoperationsarerestrictedtothetopofthestack,theimplementationofstackstoragestructuresisasimplifiedversionofsequentiallistsandsinglylinkedlists.DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueSequentialStackSequentialstack:thesequentialstoragestructureofastack

012345678Howtorepresentthestacktop:usevariabletoptostorethesubscriptofthetopelement.Howtorepresentthestackbottom:useoneendofthearrayasthestackbottom.topabcHowcananarraybeadaptedtoimplementthesequentialstorageofastack?3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueImplementationofSequentialStackconstintStackSize=10;template<typenameElement>classSStack{public:SStack();~SStack();voidpush(Elementx);Elementpop();ElementgetTop();intisEmpty();private:Elementdata[StackSize];inttop;};

InitStack:initializethestackDestroyStack:destroythestackPush:pushanelementontothestackPop:popanelementfromthestackGetTop:getthetopelementEmpty:determinewhetherthestackisemptyClassimplementationofstack:3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueuetemplate<typenameElement>voidSStack<Element>::push(Elementx){if(top==StackSize-1)throw"overflow";data[++top]=x;}

012…

StackSize-1topabcxImplementationofSequentialStackPushpushInput:elementvaluexFunction:insertelementxatthetopofthestackOutput:ifinsertionsucceeds,oneelementisaddedtothetop;otherwise,returnfailureinformationWhencanapushoperationnotbeperformed?Timecomplexity?3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueImplementationofSequentialStacktemplate<typenameElement>ElementSStack<Element>::pop(){

if(top==-1)throw"underflow";x=data[top--];

returnx;}

012…

StackSize-1abctopPoppopInput:noneFunction:deletethetopelementofthestackOutput:ifdeletionsucceeds,returnthedeletedelement;otherwise,returnfailureinformationWhencanapopoperationnotbeperformed?Timecomplexity?Howcanwegetthetopelementofthestack?3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueImplementationofSequentialStackCheckwhetherthestackisemptyisEmpty

Input:noneFunction:determinewhetherthestackisemptyOutput:return1ifthestackisempty;otherwise,return0

012…

StackSize-1abctopEmptystack:top=-1template<typenameElement>intSStack<Element>::isEmpty(){if(top==-1)return1

else

return0;}3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueSequential

Stack3.1PositionofthestackbottomUsually,theendofthearraywithsubscript0isusedasthestackbottom;whenelementsareadded,thetoppointerincreasesfrom0.Theendwiththelargestarraysubscriptcanalsobeusedasthestackbottom;whenelementsareadded,thetoppointerdecreasesfromMAX.

012345678topCanthestackbottombeplacedelsewhere?topDataStructuresandAlgorithmsDataStructuresChapter3StackandQueue3.1TwoStacksSharingSpaceIfaprogramneedstousetwostackswiththesamedatatypeatthesametime,howshouldtheybestoredsequentially?Solution1:Directsolution:allocateaseparatearrayspaceforeachstack.Solution2:Sequentialstacksextendinonedirection:useonearraytostoretwostacks.DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueTwoStacksSharingSpace3.1a1

a2…aitop1top2bj

……b2

b1Bottomofstack1Bottomofstack2Thebottomofstack1isfixedattheendwithsubscript0;Thebottomofstack2isfixedattheendwithsubscriptStackSize-1;top1andtop2arethetoppointersofstack1andstack2,respectively;Stack_Sizeisthesizeoftheentirearrayspace(representedbySinthefigure).DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueTwoStacksSharingSpacea1a2

…antop1Stack1empty:top1=-1Stack2empty:top2=MaxSizeTwostackssharingspace:fortwostackswiththesamedatatype,pre-allocatedstoragespacecanbeusedasfullyaspossible.Thisistheideaoftwostackssharingspace.bm…b2b1…top2

012…

MaxSize-1Stackfull:top1+1=top23.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueLinkedStack3.1Whichendismoreconvenientasthestackbottom,andwhichendasthestacktop?Linkedstack:thelinkedstoragestructureofastackImplementationmethod:linkedlistBasicidea:determinethepositionsofthestackbottomandstacktopheada1a2an∧aiDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueIftheheadofthelinkedlistisusedasthestacktopandthetailasthestackbottom3.1Asinglylinkedlistusuallyneedsaheadernodeandaworkingpointer.Whentheheadofthelinkedlistisusedasthestacktop,onlyonetoppointerisneeded;itreplacesboththeheadpointerandtheworkingpointerinthesinglylinkedlist.Thisapproachsimplifiesoperationsonthesinglylinkedlist.Iftheheadofthelinkedlistisusedasthestackbottomandthetailasthestacktop,theoperationisnotsosimple.Interestedstudentsmayanalyzeitthemselves.LinkedStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueImplementationofLinkedStacktemplate<typenameElement>classLStack{public:LStack();~LStack();voidpush(Elementx);Elementpop();ElementgetTop();intempty();private:Node<Element>*top;};

InitStack:initializethestackDestroyStack:destroythestackPush:pushanelementontothestackPop:popanelementfromthestackGetTop:getthetopelementEmpty:determinewhetherthestackisemptyClassimplementationofstack:3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueuetemplate<typenameElement>voidLStack<Element>::push(Elementx){s=newNode<Element>;s->data=x;s->next=top;top=s;}ImplementationofLinkedStackPushpush

Input:elementvaluexFunction:insertelementxatthetopofthestackOutput:ifinsertionsucceeds,oneelementisaddedtothetop;otherwise,returnfailureinformationIsthisheadinsertionortailinsertion?Timecomplexity?topanan-1a1∧xstop3.1Whyisitunnecessarytocheckwhetherthestackisfull?DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueImplementationofLinkedStacktemplate<typenameElement>ElementLStack<Element>::pop(){

if(top==nullptr)throw"underflow";

x=top->data;p=top;

top=top->next;

deletep;

returnx;}Poppop

Input:noneFunction:deletethetopelementofthestackOutput:ifdeletionsucceeds,returnthedeletedelement;otherwise,returnfailureinformationWhencanapopoperationnotbeperformed?Timecomplexity?Howcanwegetthetopelementofthestack?topanan-1a1∧topptop=nullptrEmptystack3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueComparisonBetweenSequentialStackandLinkedStack3.1Timeperformance:Same;bothhaveconstanttimecomplexityO(1).Spaceperformance:Sequentialstack:hasalimitonthenumberofelementsandmaywastespace.Linkedstack:nostack-fullproblemunlessnomemoryisavailable.However,eachelementrequiresapointerfield,whichintroducesstructuraloverhead.Insummary,whenthenumberofelementschangesgreatlyduringstackuse,alinkedstackisappropriate;otherwise,asequentialstackshouldbeused.DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueApplicationsofStackSStack<int>stack;

while(n) {stack.push(n%8); n=n/8;}while(!stack.isEmpty()){cout<<stack.pop(); }

NNdiv8Nmod8289236143614514555505Output3.1NumberSystemConversionDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample：(2892)10=(5514)8ApplicationsofStack

Whenmultiplefunctionsarecalledinanestedmanner,theexecutionruleisthatthefunctioncalledlaterreturnsfirst.Therefore,thestorageusedbyeachfunctionshouldbemanagedinastack-likemanner.Example:intmain(){

intm,n;A(m,n);1:...return0;}//mainDataareaofmainmnDataareaoffunctionA1mni...DataareaoffunctionB2i

xy...……Run-timestack3.1FunctionCallsandRecursionvoid

A(ints,intt){inti;B(i);2:…}//Avoid

b(intr){intx,y;…}//BDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueApplicationsofStack3.1FunctionCallsandRecursionRecursionRecursion:asubprogram(orfunction)callsitselfdirectly,orindirectlythroughaseriesofcallingstatements.Itisafundamentalmethodfordescribingandsolvingproblems.Basicideaofrecursion:problemdecomposition.Transformacomplexproblemthatisdifficulttosolveintooneormoresubproblems,andthenfurtherdecomposethesesubproblemsintosmallersubproblemsuntileachcanbesolveddirectly.Keypointsofrecursion:Recursiveboundarycondition:determineswhenrecursionstops,alsocalledtherecursiveexit.Recursivepattern:howthelargerproblemisdecomposedintosmallerproblems,alsocalledtherecursivebody.DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueInternalexecutionprocessofarecursivefunctionWhenexecutionbegins,aworkingstackisfirstcreatedforrecursivecalls.Itsstructureincludesvalueparameters,localvariables,andreturnaddresses.Beforeeachrecursivecall,thecurrentvaluesoftherecursivefunction'svalueparametersandlocalvariables,aswellasthereturnaddressafterthecall,arepushedontothestack.Aftereachrecursivecallfinishes,thetopelementispoppedfromthestack,restoringthecorrespondingvalueparametersandlocalvariablestotheirpreviousvalues,andexecutioncontinuesatthespecifiedreturnaddress.ApplicationsofStack3.1FunctionCallsandRecursionDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueTowerofHanoiThreetowersA,B,andCTowerAhas64goldendisksarrangedbysize.Goal:movealldiskstotowerCwiththehelpoftowerB.Onlyonediskcanbemovedatatime.Atalltimes,largerdisksmustbebelowsmallerdisks.ApplicationsofStack3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueRecursiveprocessofthe2-diskHanoitowerTowerofHanoiApplicationsofStack3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueRecursiveprocessofthe3-diskHanoitowerTowerofHanoiApplicationsofStack3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueRecursiveprocessofthe4-diskHanoitowerTowerofHanoiApplicationsofStack3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueRecursivesolutiontotheTowerofHanoiproblemImplementationsteps:1.Whenn=1,movethediskdirectlytothetargetpeg.2.Whenn>1,completetheprocessinthreesteps:2.1Move(n-1)diskstotheauxiliarypegbyrecursivelysolvingthe(n-1)-diskHanoiproblem.2.2Movethelastdisktothetargetpeg.2.3Movethe(n-1)diskstothetargetpegbyrecursivelysolvingthe(n-1)-diskHanoiproblem.C++description:ApplicationsofStack3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueuevoidHanoi(intn,charA,charB,charC){

if(n==1)Move(A,C);

else{

Hanoi();

Move(A,C);

Hanoi();

}

}InfixexpressionTheoperatorisplacedbetweenoperands.a+b,c*dPostfixexpressionTheoperatorisplacedafteroperands.ab+,cd*PrefixexpressionTheoperatorisplacedbeforeoperands.+ab,*cdCalculationrules–Multiplicationanddivisionbeforeadditionandsubtraction;–Calculatefromlefttoright;–Calculateinsideparenthesesbeforeoutsideparentheses.•Example:4*(7-2*3)+26/(5+8)ReversePolishnotation/postfixexpression:containsnoparentheses,onlyoperandsandoperators;operatorsplacedearlierhavehigherpriority.4#7#2#3#*-*26#5#8#+/+ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueEvaluationofinfixexpressionsTwostacks:operandstackOPNDandoperatorstackOPTRScantheexpressionfromlefttorightuntilitends.Operand:pushontoOPND.CompareanoperatorwiththetopelementofOPTRbypriority:Higher:pushontoOPTR.Lower(nothigher):PopthetoptwoelementsfromOPND;popthetopelementfromOPTR;performtheoperationandpushtheresultontoOPND;continueprocessingthecurrentcharacter.Equal:popthetopelementfromOPTR.ThetopelementofOPNDisthefinalresult.ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExpressionEvaluation3.1Example:3*(4+2)/2-5Note:whenaleftparenthesisisinthestack,itisconsideredtohavethelowestpriority.ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5Note:whenaleftparenthesisisinthestack,itisconsideredtohavethelowestpriority.ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5Atthispoint,theloopends,andthetopelementofOPNDisthecalculationresult.ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueEvaluationofpostfixexpressionsOnestack:storesonlyoperands,notoperators.Scantheexpressionfromlefttorightuntilitends.Operand:pushontoS.Operator:PopthetoptwoelementsfromS;performtheoperationandpushtheresultback.ThetopelementofSisthecalculationresult.

Note:postfixexpressionevaluationisrelativelysimpleandveryimportantinpractice.ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5Convertedtopostfixexpression:342+*2/5-ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5Convertedtopostfixexpression:342+*2/5-ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5Convertedtopostfixexpression:342+*2/5-ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5Convertedtopostfixexpression:342+*2/5-Atthispoint,theloopends,andthetopelementofSisthecalculationresult.ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueConvertinganinfixexpressiontoapostfixexpressionOnestack:temporarilystoresoperators;operandsarenotstored.Scantheinfixexpressionfromlefttorightuntilitends.Operand:outputthecharacterdirectly.CompareanoperatorwiththetopelementofstackSbypriority:Higher:pushontoS.Lower(nothigher):popthetopelementofS,outputit,andcontinueprocessingthecurrentcharacter.Equal:popthetopelementofS(onlyforprocessingparentheses).Thefinaloutputisthepostfixexpression.ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5Convertedtopostfixexpression:Note:whenaleftparenthesisisinthestack,itisconsideredtohavethelowestpriority.ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5Convertedtopostfixexpression:Note:whenaleftparenthesisisinthestack,itisconsideredtohavethelowestpriority.ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5Convertedtopostfixexpression:Note:whenaleftparenthesisisinthestack,itisconsideredtohavethelowestpriority.ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5Convertedtopostfixexpression:Note:whenaleftparenthesisisinthestack,itisconsideredtohavethelowestpriority.ExpressionEvaluation3.1DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExample:3*(4+2)/2-5Convertedtopostfixexpression:Note:whenaleftparenthesisisinthestack,itisconsideredtohavethelowestpriority.ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueue2012postgraduateentranceexamquestion:Whenconvertingtheinfixexpressiona+b-a*((c+d)/e-f)+gintotheequivalentpostfixexpressionab+acd+e/f-*-g+,astackisusedtostoreoperatorswhoseoperationorderhasnotyetbeendetermined.Ifthestackisinitiallyempty,whatisthemaximumnumberofoperatorsstoredinthestackatthesametimeduringconversion?()2014postgraduateentranceexamquestion:Ifthestackisinitiallyempty,duringtheconversionofa/b+(c*d-e*f)/gintotheequivalentpostfixexpression,whataretheelementsinthestackinorderwhenfisscanned?()ExpressionEvaluation3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueExpressionevaluationThissectionintroducedthebasicmethodusedbycomputerstoevaluateexpressions.Evaluationusinginfixexpressionsisrelativelycomplex,whileevaluationusingpostfixexpressionsissimpler.Inpractice,computersoftenusepostfixexpressions.Theconversionfrominfixexpressionstopostfixexpressionscanalsobeimplementedwithastack.Inthechapterontrees,asimplermethodforconvertingamonginfix,prefix,andpostfixexpressionswillbeintroduced.3.1ApplicationsofStackDataStructuresandAlgorithmsDataStructuresChapter3StackandQueueQueueandItsApplications3.2Definition

ofQueueQueue:alinearlistinwhichinsertionisrestrictedtooneendanddeletiontotheotherend.Queuefront:theendwheredeletionisallowed;theelementatthefrontiscalledthefrontelement.Queuerear:theendwhereinsertionisallowed;theelementatthereariscalledtherearelement.3.2DataStructuresandAlgorithmsDataStructuresChapter3StackandQueue（a1,…,an-1,an）DefinitionofQueueInsertionpositions:1ton+1Deletionpositions:1tonLinearlistInsertionposition:n+1Deletionposition:1QueuefrontrearenQueuedeQueueQueuefront:theendwheredeletionisallowed;theelementatthefrontiscalledthefrontelement.Queuerear:theendwhereinsertionisallowed;theelementatthereariscalledtherearelement.Aqueuethatcontainsnoelementsandhaslength0iscalledanemptyqueue.Operationalcharacteristicofqueue:(FirstIn,FirstOut,

FIFO)a1

a2…anQueue3.2DataStructuresandAlgorithmsDataStructuresChapter3StackandQueue（a1,…,an-1,an）AbstractDataTypeDefinitionofQueueADTQueueDatamodelBasicoperations

endADTDataobject:D={ai|1≤i≤n，n≥0，aiisElementtypedata}Datarelationship:R=｛<ai，ai+1>|1≤i≤n-1｝InitQueue(&Q):initializethequeueandconstructanemptyqueueQ.DestroyQueue(&Q):whetherqueueQisempty;returntrueifitisempty,otherwisereturnfalse.enQueue(&Q,x):insertelementxintoQasthenewrearelement.deQueue(&Q,&x):deletethefrontelementfromQandreturnitsvaluethroughx.getQueue(Q,&x):getthefrontelementandreturnitthroughx.3.2DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueSequentialStorageStructureofQueueUseacontiguousstoragespacetostoretheelementsinthequeue.Sequentialqueue:aqueuestoredusingasequentialstoragestructure.01234a1a2a3a4rearExample:a1,a2,a3,anda4enterthequeueinorder.3.2DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueSequentialStorageStructureofQueue01234a1a2a3a4rear01234a2a3a4rearExample:a1leavesthequeue.Example:a2leavesthequeue.Timecomplexity?Howcanweimprovethetimeperformanceofthedequeueoperation?3.2DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueSequentialStorageStructureofQueueSettwopositionpointers:frontandrear.Convention:frontpointstothepositionbeforethefrontelement,andrearpointstotherearelement.01234a2a3a4rearfronta101234a2a3a4fronta5rearExample:a1leavesthequeue.Example:a2leavesthequeue,anda5entersthequeue.3.2DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueWhatproblemiscausedbytheone-waymobilityofthequeue?Falseoverflow:thearrayspaceoverflowseventhoughthereisstillfreespaceatthelowendofthearray.01234a4fronta5rearExample:a3leavesthequeue.Whatifa6wantstoenterthequeuenow?3.2Ifa6isinsertedatthistime,an"overflow"willoccur,althoughpositions0and1ofthearrayarestillfree.Thisiscalled"falseoverflow".Circularqueue:connecttheheadandtailofthearrayusedtostorethequeue.DataStructuresandAlgorithmsDataStructuresChapter3StackandQueueSequentialStorageStructureofQueue3.2Thereisnophysicalcircularstructure;itisimplementedinsoftware.Modulooperation:(4+1)%5=00123