数据结构英文版课件Chapter4.Queues

DataStructuresUsingCNicklausWirth:1/772/77DataStructuresUsingC4.Queues◆Introduction◆Definition◆OperationsonaQueue◆AbstractDataTypeforQueues◆RepresentationofaQueue◆VariousOtherQueueStructures◆ApplicationsC.X.Deng理学院物理系4.1IntroductionQueue:awaitingline4.QueuesAqueueisaFIFOstructure:FirstInFirstOutDeletion3/772010-4-21DataStructuresUsingCInsertion#ExampleC.X.Deng理学院物理系4.QueuesReadyAwaitingQueuesofprocessesincomputeroperatingsystemRunningQ2Q1#Example4/772010-4-21DataStructuresUsingCC.X.Deng理学院物理系Applicationprogram1WndProcMessagemappingDefWndowProcApp1messagequeuesSystemQueuesInputmessageSystemmessageApp2messagequeuesApp3messagequeuesPostmessageSendMessageWINDOWSmessagequeues5/772010-4-21DataStructuresUsingC#Example:4.QueuesMultiTaskingSystemC.X.Deng理学院物理系4.2Definition◆AQueueisanorderedcollectionofhomogeneousdataelementswheretheinsertingoperationtakesplaceatoneend(rear),anddeletionoperationtakesplaceattheotherend(front).FIFO(FirstInFirstOut)◆LengthofaQueue:Thenumberofelementsthataqueuecanaccommodate.◆FrontandRearofaQueue.4.QueuesFrontAsamplequeueRear6/772010-4-21DataStructuresUsingC13579……C.X.Deng理学院物理系7/772010-4-21DataStructuresUsingC4.3OperationsonaQueue(1)Insert(q,element):insertanelementattherearendofqueueq,ifthequeueisnotfull;(2)item=remove(q):removeanelementfromthefrontendofqueueq,ifthequeueisnotempty;(3)bv=Isempty(q):determinewherethequeueisemptyornot,bv=FALSEifqisnotempty,bv=TRUEifqisempty.(4)Fv=Isfull(q):determinewherethequeueisfullornot,bv=FALSEifqisnotfull,bv=TRUEifqisfull.4.QueuesC.X.Deng理学院物理系(3)Ifitisnotfull,insertanewelementinthisnewrearposition.#Example:4.Queues◆Insertionoperation(1)Increasetherearpositionby1;(2)Checkwhetheritisfull;FrontRearFrontRear(NotFull)FrontRear8/772010-4-21DataStructuresUsingC13579……13579……1357911……C.X.Deng理学院物理系(3)Increasethefrontpositionby1;#Example:4.Queues◆Deletionoperation(1)Checkwhetherthequeueisempty;(2)Ifitisnotempty,removetheelementatthefront;FrontRear×……FrontRear3579(NotEmpty)FrontRear9/772010-4-21DataStructuresUsingC13579……×3579……C.X.Deng理学院物理系10/772010-4-21DataStructuresUsingC4.4AbstractDataTypeforaQueue◆ADTforQueue(1)Enqueue():Addsanitemtotherearendofthequeue;(2)Dequeue():Removesandreturnsanitemfromthefrontendofthequeue;(3)Front():Verifiesasitemonthefrontendofthequeue.4.QueuesC.X.Deng理学院物理系4.5RepresentationofaQueue◆Usinganarray◆Usingalinkedlist(1)Representationofaqueueusinganarray……4.QueuesFrontDeletionOperationoccursatthisend.11/772010-4-21DataStructuresUsingCRearInsertionOperationoccursatthisend.◆Requirement:(1)1Darray;(2)Avariableindicatingthefrontposition;(3)Avariableindicatingtherearposition.◆Advantages:simple,easy;◆Disadvantages:(a)possiblewastageofmemory;(b)Insertionisdeniedevenifthereissomespaceatthefrontofthearray.Howtosolve?C.X.Deng理学院物理系◆Insertiononanarraya[0]a[1]a[2]a[3]a[4]4.Queues0front0rear1front1rear1front2rear1front3rear1front4rear12/772010-4-21DataStructuresUsingC①③②④⑤inta[5];eInitial:f=0;r=0;SSCSCUSCUTfrontandrearareintegervaria#b(leRse,fforemptyqueuefront=rear=0.C.X.Deng理学院物理系4.Queues①1front4rear2front4rear3front4rear4front4rear0front0rear13/772010-4-21DataStructuresUsingC③②④⑤◆Deletiononanarraya[0]a[1]a[2]a[3]a[4]inta[5];frontandrearareintegerInitial:f=0;r=0;SCUTCUTUTTvariables,foremptyqueuefront=rear=0.C.X.Deng理学院物理系4.Queues①1front3rear2front3rearfront3rear0front0rear314/772010-4-21DataStructuresUsingC③②④a[0]a[1]a[2]a[3]a[4]◆Insertion/DeletiononanarrayInitial:f=0;r=0;SCUCUUC.X.Deng理学院物理系4.Queues#Example:arrayimplementionofqueuedefineMAX100insert(intitem){if(r==n)/*nisthemaximumsize*/{printf(“queueisfull\n”);printf(“itemisnotinsertedintothequeue”);return;}else{if((r==0)&&(f==0)){f=1;};r=r+1;a[r]=item;printf(“Itemisinsertedintothequeue,”);}}inta[MAX];intf=0,r=0,n;/*f:front,r:rear,n:max;Initial:f=0;r=0;15/772010-4-21DataStructuresUsingCC.X.Deng理学院物理系4.Queues#Example:arrayimplementionofqueue#(Referencep105)intdelete(){intitem;if(f==0){printf(“queueisempty\n”);return;}else{item=a[f];if(f==r){r=0;f=0;}else{f=f+1;}}returnitem;}Initial:f=0;r=0;16/772010-4-21DataStructuresUsingCC.X.Deng理学院物理系◆Insertiononanarraya[0]a[1]a[2]a[3]a[4]4.Queuesinta[5];frontandrearareintegervariables,foremptyqueuefront=rear.front-1rear-1front0rear-1front1rear-1front2rear-1front3rear-117/772010-4-21DataStructuresUsingC①③②④⑤Initial:f=-1;r=-1;SSCSCUSCUTC.X.Deng理学院物理系◆Deletiononanarraya[0]a[1]a[2]a[3]a[4]4.Queues-1front3rear0front3rear1front3rear2front3rearfrontrear①③②④inta[5];Initial:f=-1,r=-1;⑤3frontandrearforempty3areintegervariables,queuefront=rear.DataStructuresUsingC18/772010-4-21SCUTCUTUTTC.X.Deng理学院物理系4.Queues◆Deletion/Insertiononanarray①③②④⑤⑥a[0]a[1]a[2]a[3]a[4]rearfront-1front2rear0front2rear1front222rearJ2wasdeleted2front3J3wasinsertedrearinta[5];front33rearJ3wasdeletedJ0wasdeletedJ1wasdeletedEMPTYQueueEMPTYQueueInitial:f=-1;r=-1;19/772010-4-21DataStructuresUsingCJ0J1J2J1J2J2J3C.X.Deng理学院物理系4.Queues◆Deletion/InsertiononanarrayJ4wasinsertedfront4rear3⑦frontrear44⑧4front4rear⑨a[0]a[1]20/772010-4-21DataStructuresUsingCa[2]a[3]a[4]J4wasdeletedEMPTYQueueInitial:f=-1;r=