《刊首寄语Titl》PPT课件

《《刊首寄语Titl》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、QueueCandDataStructuresBaojianHuabjhua@ustc.edu.cnLinearListRecallthatalinearlisthastheform:Thedeleteandinsertoperationsmayinsertordeleteanarbitraryelemente_iIfthedeleteisrestrictedatoneendandinsertattheotherend,wegetaqueueExample:QueueofChar‘a’insert

2、‘b’‘a’insertinsert‘b’‘a’‘c’delete‘b’‘c’AbstractDataTypesinC:Interface//infile“queue.h”#ifndefQUEUE_H#defineQUEUE_HtypedefstructQueue_t*Queue_t;Queue_tQueue_new();intQueue_size(Queue_tq);intQueue_isEmpty(Queue_tq);voidQueue_enQueue(Queue_tq,polyx);poly

3、Queue_deQueue(Queue_tq);polyQueue_getHead(Queue_tq);#endifImplementationUsingExtensibleArray//infile“arrayQueue.c”#include“queue.h”structQueue_t{Array_tl;};//Recalltheboxstrategy:lqOperations:“new”Queue_tQueue_new(){Queue_tq=malloc(sizeof(*q));q->l=Ar

4、ray_new();returnq;}0n-1arraymaxtaillqOperations:“size”intQueue_size(Queue_tq){returnArray_length(q->l);}0n-1arraymaxtaillqOperations:“isEmpty”intQueue_isEmpty(Queue_tq){returnArray_isEmpty(q->l);}0n-1arraymaxtaillqOperations:“enQueue”voidQueue_enQueue

5、(Queue_tq,polyx){Array_insertLast(stk->l,x);return;}0n-1arraymaxtaillqOperations:“deQueue”polyQueue_deQueue(Queue_tq){if(Array_isEmpty(q->l))error(“emptyqueue”);returnArray_deleteFirst(q->l);}Operations:“deQueue”0n-1arraymaxtaillqOperations:“deQueue”0

6、n-1arraymaxtaillqAnalysisWhat’sthecomplexity?enQueue:O(1)deQueue:O(n)datamovementCanwedobetter?LazyapproachbetteramortizedperformanceCircularqueueLazyApproachInsteadofmovingdatawhen“deQueue”,wemovedataonlywhen“enQueue”reachingthetailofthequeueO(n)onno

7、perationswhichhasO(1)amortizedcostLazyApproachWhat’snecessarymodification?Leavethisasaprogrammingassignment0n-1arraymaxtaillqCircularQueueArefinementofthelazyapproachisthecircularqueuehead=tail=0;012345tailheadenQueue(q,‘a’);CircularQueueArefinementof

8、thelazyapproachisthecircularqueuehead=tail=0;012345tailheadenQueue(q,‘a’);enQueue(q,‘b’);‘a’CircularQueueArefinementofthelazyapproachisthecircularqueuehead=tail=0;012345tailheadenQueue(q,‘a’);enQueue(q,‘b’);enQueue(q,‘c’);‘a’‘b’CircularQueueAr