第三章-栈与队列PPT课件

.,1,第三章栈与队列,栈(Stack)队列(Queue),.,2,3.4队列(Queue),定义队列是只允许在一端删除，在另一端插入的线性结构允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut),.,3,队列的抽象数据类型,ADTQueueD=ai|aiElemSet,i=1,2,nR=|ai-1,aiD,i=2,n约定a1端为队首，an端为队尾P:InitQueue(intfront;intrearSqQueue;SqQueueQ;,.,5,顺序队列的实现,当front=rear=0时表示空队列当插入新元素到队尾时，rear加1当删除队首元素时，front加1这种顺序队列空间利用率低，每个位置只能使用一次,.,6,循环队列及其实现,循环队列为了提高队列的空间利用率，提出循环队列结构与顺序队列相同，只是界线处理稍有不同,.,7,循环队列的进队和出队,队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;,.,8,存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front=rear;队满条件：(rear+1)%maxSize=frontfront=rear可能表示队空，也可能表示队满应另设标志以便区别队空状态或少用一个位置,循环队列(CircularQueue),.,9,循环队列及其实现,循环队列为了提高队列的空间利用率，提出循环队列结构与顺序队列相同，只是界线处理稍有不同,StatusInitQueue(SqQueue,.,10,循环队列及其实现,intQueueLength(SqQueueQ)return(Q.rearQ.front+MAXQSIZE)%MAXQSIZE;,StatusEnQueue(SqQueue,StatusDeQueue(SqQueue,第三种方法：使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面是实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。#defineQueueSize100typedefcharDataType;typedefStructintfront;intrear;intcount;datatypedataqueuesizecirqueue;,（1）置空队voidinitqueue(cirqueue*q)qfront=qrear=0;qcount=0;（2）判断队空intqueueempty(cirqueue*q)returnqcount=0;（3）判断队满intqueuefull(cirqueue*q)returnqcount=queuesize;,（4）入队voidenqueue(cirqueue*q,datatypex)if(queuefull(q)error(“queueoverflow”);qcount+;qdataqrear=x;qrear=(qrear+1)%queuesize;,（5）出队datatypedequeue(cirqueue*q)datatypetemp;if(queueempty(q)error(“queueunderflow”);temp=qdataqfront;qcount-;qfront=(qfront+1)%queuesize;returntemp;,（6）取队首元素datatypequeuefront(cirqueue*q)if(queueempty(q)error(“queueisempty.”);returnqdataqfront;,1、循环队列的优点是什么？如何判断它的空和满？2、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？3、用第一种、第二种方法，即设状态标识、少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。4、如果头指针、尾指针、队列长度中只能选两个来实现队列，你使用哪两个？,思考、练习题,假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队算法。作业,习题,.,18,队列的链接表示链式队列,队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为front=NULL,3.4.3链队列和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：typedefstructqueuenodedatatypedata;structqueuenode*next;queuenode;,typedefstructqueuenode*front;queuenode*rear;linkqueue;下面给出链队列上实现的基本运算：voidinitqueue(linkqueue*q)qfront=qrear=null;,intqueueempty(linkqueue*q)returnqfront=null,elseqrearnext=p;qrear=p;Datatypedequeue(linkqueue*q)datatypex;queuenode*p,if(queueempty(q)error(“queueunderflow”);p=qfront;x=pdata;qfront=pnext;if(qrear=p)qrear=null;free(p);returnx;,datatypequeuefront(linkqueue*q)if(queueempty(q)error(“queueisempty.”);returnqfrontdata;注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。,.,25,队列的表示和实现带头结点,队首指针front和队尾指针rear,typedefstructQElemTypedata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;QueuePtrrear;LinkQueue;LinkQueueQ;,Q.front,Q.rear,data,next,队首,队尾,头结点,.,26,链队列的实现,x,空队,元素x入队,.,27,队列应用,1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；,3）离散事件的模拟-模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程；,在操作系统课程中会讲到,.,28,优先级队列(PriorityQueue)？,优先级