队列

13.4队列3.4.1抽象数据类型队列的定义队列（Queue）:先进先出(FirstInFirstOut)•(缩写为FIFO）的线性表。•仅在队尾进行插入和队头进行删除操作的线性表。队头（front）:线性表的表头端，即可删除端。队尾（rear）:线性表的表尾端，即可插入端。队头对尾......a1a2a3an-1an入队列(Enqueue)出队列(Dequeque)2队列的抽象数据类型ADTQueue{数据对象：D={ai|ai属于Elemset,(i=1,2,…,n,n≥0)}数据关系：R1={＜ai-1,ai＞|ai-1,ai属于D,(i=2,3,…,n)}约定an为队尾,a1为队头。基本操作：•InitQueue(&Q);DestroyQueue(&Q);•ClearQueue(&Q);QueueEmpty(Q);•QueueLength(Q);GetHead(Q,&e);•EnQueue(&Q,e);DeQueue(&Q,&e);•QueueTraverse(Q,visit())}ADTQueue3队列的基本操作(之一)InitQueue(&Q)•操作结果:构造一个空的队列Q。DestroyQueue(&Q)•初始条件:队列Q已经存在。•操作结果:销毁队列Q。ClearQueue(&Q)•初始条件:队列Q已经存在。•操作结果:将队列Q重置为空队列。4队列的基本操作(之二)QueueEmpty(Q)•初始条件:队列Q已经存在。•操作结果:若队列Q为空队列，则返回TURE;否则返回FALSE。QueueLength(Q)•初始条件:队列Q已经存在。•操作结果:返回队列Q中的数据元素个数,即队列Q的长度。GetHead(Q,&e)•初始条件:队列Q已经存在且非空。•操作结果:用e返回队列Q中队头元素的值。5队列的基本操作(之三)EnQueue(&Q,e)•初始条件:队列Q已经存在。•操作结果:插入元素e为新的队尾元素。DeQueue(&Q,&e)•初始条件:队列Q已经存在且非空。•操作结果:删除队列Q的队头元素并用e返回其值。QueueTraverse(Q,visit())•初始条件:队列Q已经存在且非空。•操作结果:从队头到队尾依次对队列Q的每个元素调用函数visit()。一旦visit()失败，则操作失败。63.4.2链队列--队列的链式表示与实现typedefstructQNode{QElemTypedata;structQNode*next;}Qnode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;#defineOK1#defineOVERFLOW-1#defineERROR0data*nextfrontrear7链队列示意图frontrearfrontrear赵frontrear钱赵frontrear钱赵(a)空队列(b)元素“赵”入队列(c)元素“钱”入队列(d)元素“赵”出队列8链队列的操作实现举例/*InitQueue构造一个空的队列Q*/StatusInitQueue(LinkQueue&Q){Q.rear=(QueuePtr)malloc(sizeof(QNode));Q.front=Q.rear;if(!Q.front)return(OVERFLOW);Q.front-next=NULL;returnOK;}//InitQueue9链队列的操作实现(DestroyQueue)//销毁队列QStatusDestroyQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;}returnOK;}//DestroyQueue10链队列的操作实现(EnQueue)//插入元素e为新的队尾元素StatusEnQueue(LinkQueue&Q,QelemTypee){p=(QueuePtr)malloc(sizeof(QNode));if(!p)return(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;}//EnQueue11链队列的操作实现(DeQueue)//若队列不空,删除队列Q的队头元素并用e返回其值,同时返回OK;否则返回ERROR。StatusDeQueue(LinkQueue&Q,QelemType&e){if(Q.front==Q.rear)retrunERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}//DeQueue123.4.3循环队列--队列的顺序表示与实现采用顺序存储结构约定:1)初始空队列：front=rear=0;2)插入新的元素时,rear++;3)删除队头元素时,front++;J1J2J3Q.frontQ.rearJ3Q.frontQ.rearJ5J6Q.frontQ.rearQ.rearQ.front10235413循环列表----解决数组越界但未占满空间的办法10maxsize-1...Q.frontQ.rear...队列当Q.rearQ.front时:Q.rear–Q.front=队列中元素个数当Q.rearQ.front时:Q.rear–Q.front+maxsize=队列中元素个数当Q.rear=Q.front时:队列是’空’或’满’14循环队列的头尾指针012345J3J4J5Q.rearQ.front(a)一般队列012345Q.rearQ.front(c)空队列J6J3J4J5012345J7J8Q.rearQ.front(b)满队列15循环队列--队列的顺序存储结构实现(1)typedefstruct{QElemType*base;//存储空间基地址intfront;//队头指针intrear;//队尾指针}SqQueue;#defineMAXSIZE100StatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(sizeof(QElemType)*MAXSIZE);if(!Q.base)return(OVERFLOW);Q.front=Q.rear=0;returnOK;}//InitQueue16循环队列--队列的顺序存储结构实现(2)StatusEnQueue(SqQueue&Q,QelemTypee){if((Q.rear+1)%MAXSIZE==Q.front)return(ERROR);Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}//EnQueue17循环队列--队列的顺序存储结构实现(3)StatusDeQueue(SqQueue&Q,QelemType&e){if(Q.front==Q.rear)retrunERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;returnOK;}//DeQueue18实验与习题习题：3.7实验题：写一个主程序来上机验证顺序存储结构--循环队列的基本操作