数据结构与算法分析lecture5(队列)

queue(队列)队列也是一种受限的线性表，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出“FIFO”表。入队（enqueue）：队列元素从队尾插入出队（dequeue）：队列元素从队首删除a1,a2,a3,a4,…………an-1,an队列示意图队头队尾Queue(队列)TaoLiangCollegeofsoftwareSiChuanUniversity队列的存储结构线性队列顺序存储结构循环队列2051217frontrear(a)12173304frontrear(b)(a)Thequeueaftertheinitialfournumber20,5,12and17havebeeninserted(b)Thequeueafterelements20and5aredeleted,followingwhich3,30,and4areinserted?循环队列205121712173304frontrearfrontrear(a)(b)(a)Thequeueaftertheinitialfournumber20,5,12and17havebeeninserted(b)Thequeueafterelements20and5aredeleted,followingwhich3,30,and4areinserted队首存放在数组中编号较低的位置（沿顺时针方向），队尾存放在数组中编号较高的位置．因此，入队操作增加rear指针的值，出队操作增加front指针的值Array-basedqueueimplementationtemplateclassElemclassAQueue:publicQueueElem{private:intsize;intfront;intrear;Elem*listArray;public:AQueue(intsz=DefaultListSize){//Constructor//Makelistarrayonepositionlargerforemptyslotsize=sz+1;rear=0;front=1;listArray=newElem[size];}~AQueue(){delete[]listArray;}//Destructorvoidclear(){front=rear;}boolenqueue(constElem&it){if(((rear+2)%size)==front)returnfalse;//fullrear=(rear+1)%size;//circularincrementlistArray[rear]=it;returntrue;}入队操作增加rear指针的值booldequeue(Elem&it){if(length()==0)returnfalse;//emptyit=listArray[front];front=(front+1)%size;//circularincrementreturntrue;}出队操作增加front指针的值boolfrontValue(Elem&it)const{if(length()==0)returnfalse;//emptyit=listArray[front];returntrue;}virtualintlength()const{return((rear+size)–front+1)%size;}};Linkedqueue(链式队列)队列也可以用来链接存储线性表来实现链表的第一个表元是队列首结点链表的末尾表元是队列的队尾结点，队尾结点的链接指针值为NULL与链式栈的实现相类似,不需要在头部附加头结点.LinkedqueueimplementationtemplateclassElemclassLQueue:publicQueueElem{private:LinkElem*front;//pointertofrontqueuenodeLinkElem*rear;//pointertorearqueuenodeintsize;//numberofelementsinqueuepublic:LQueue(intsz=DefaultListSize)//constructor{front=NULL;rear=NULL;size=0;}~LQueue(){clear();}//Destructorvoidclear(){//clearqueuewhile(front!=NULL){//deleteeachlinknoderear=front;front=front-next;deleterear;}rear=NULL;size=0;}boolenqueue(constElem&it){if(rear==NULL)//Emptyqueuefront=rear=newLinkElem(it,NULL)else{rear-next=newLinkElem(it,NULL);rear=rear-next;}size++;returntrue;}booldequeue(Elem&it){//removeElemfromfrontif(size==0)returnfalse;//emptyit=front-element;//storedequeuedvalueLinkElem*ltemp=front;//holddequeuedlinkfront=front-next;//advancefrontdeleteltemp;//deletelinkif(front==NULL)rear=NULL;//dequeuedlastelementsize--;returntrue;//returnelementvalue}boolfrontValue(Elem&it)const{if(size==0)returnfalse;it=front-elements;returntrue;}virtualintlength()const{returnsize;}};ComparisonofArray-BasedandLinkedQueues顺序队列和链式队列的实现方式与栈的实现基本相似顺序队列不同于顺序栈，不能在一个数组中存储两个队列，除非总有数据项从一个队列转入另一个队列在顺序队列中存储变长记录的方式与顺序栈中的方式相同