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

《数据结构与算法分析lecture5(队列)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、queue(队列)队列也是一种受限的线性表，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出“FIFO”表。入队（enqueue）：队列元素从队尾插入出队（dequeue）：队列元素从队首删除a1,a2,a3,a4,…………an-1,an队列示意图队头队尾Queue(队列)TaoLiangCollegeofsoftwareSiChuanUniversity队列的存储结构线性队列顺序存储结构循环队列2051217frontrear(a)12173304frontrear(b)(a)Thequeueaftertheiniti

2、alfournumber20,5,12and17havebeeninserted(b)Thequeueafterelements20and5aredeleted,followingwhich3,30,and4areinserted?循环队列205121712173304frontrearfrontrear(a)(b)(a)Thequeueaftertheinitialfournumber20,5,12and17havebeeninserted(b)Thequeueafterelements20and5aredeleted,followingwhich3

3、,30,and4areinserted队首存放在数组中编号较低的位置（沿顺时针方向），队尾存放在数组中编号较高的位置．因此，入队操作增加rear指针的值，出队操作增加front指针的值Array-basedqueueimplementationtemplateclassAQueue:publicQueue{private:intsize;intfront;intrear;Elem*listArray;public:AQueue(intsz=DefaultListSize){//Constructor//Makelist

4、arrayonepositionlargerforemptyslotsize=sz+1;rear=0;front=1;listArray=newElem[size];}~AQueue(){delete[]listArray;}//Destructorvoidclear(){front=rear;}boolenqueue(constElem&it){if(((rear+2)%size)==front)returnfalse;//fullrear=(rear+1)%size;//circularincrementlistArray[rear]=it;ret

5、urntrue;}入队操作增加rear指针的值booldequeue(Elem&it){if(length()==0)returnfalse;//emptyit=listArray[front];front=(front+1)%size;//circularincrementreturntrue;}出队操作增加front指针的值boolfrontValue(Elem&it)const{if(length()==0)returnfalse;//emptyit=listArray[front];returntrue;}virtualintlength()c

6、onst{return((rear+size)–front+1)%size;}};Linkedqueue(链式队列)队列也可以用来链接存储线性表来实现链表的第一个表元是队列首结点链表的末尾表元是队列的队尾结点，队尾结点的链接指针值为NULL与链式栈的实现相类似,不需要在头部附加头结点.LinkedqueueimplementationtemplateclassLQueue:publicQueue{private:Link*front;//pointertofrontqueuenodeLink*r

7、ear;//pointertorearqueuenodeintsize;//numberofelementsinqueuepublic:LQueue(intsz=DefaultListSize)//constructor{front=NULL;rear=NULL;size=0;}~LQueue(){clear();}//Destructorvoidclear(){//clearqueuewhile(front!=NULL){//deleteeachlinknoderear=front;front=front->next;deleterear;}rear

8、=NULL;size=0;}boolenqueue(constElem&it){if(rear