数据结构队列课件

栈栈的应用队列队列的应用第三章栈和队列3.4队列3.4.1抽象数据类型队列的定义

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。（a0,a1,...,ai-1,ai,ai+1,…,an-1）插入删除例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。a0a1a2……an-1rear队头队尾front队列的示意图队列的特点先进先出说明：第一个入队的元素在队头，

最后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素队列的抽象数据定义见书Ｐ593.4.2非循环队列和循环队列

分配一块连续的存储区域来存放队列里的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置。它们的初始值在队列初始化时均应置为０。入队时将新元素插入所指的位置，然后尾指针加１。出队时，删去所指的元素，然后头指针加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。０１２３0123

FrontrearabcFrontrear

(a)队列初始为空（b）A,B,C入队０１２３０１２３bc

frontrearfrontrear（c)a出队(d)b,c出队，队为空

#defineMAXQSIZE100typedefstruct{ElemTypedata[MAXQSIZE];intfront;/*队头位置*/intrear;/*队尾位置*/}SqQueue;顺序队列的操作演示队列的顺序存储结构定义：SqQueueQQ->front存放即将要被删除的元素的下标。Q->rear存放即将要被插入的元素（目前不在队列中）的下标。Q->data[Q->front]和Q->data[Q->rear]和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（CircularQueue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。

显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列（环形队列）。

入队和出队如何表示？由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过Q->f

=Q->r来判断队列“空”还是“满”。

front540312J6J7J8J4J5rear队空：Q.front=Q.rear队满：Q.front=(Q.rear+1)%maxSize入队:Q.rear=(Q.rear+1)%maxSize出队:Q.front=(front+1)%maxSize;求队长:(Q.rear-Q.front+maxSize)%maxSize循环队列【例】设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=19;②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？答：用队列长度计算公式：

(Q.rear-Q.front+maxSize)%maxSize①L=（40＋19－11）%40=8②L=（40＋11－19）%40=32循环队列的操作演示2)出队列实现程序StatusDeQueue(SqQueue&Q,ElemType&e){if(Q.rear==Q.front)return(ERROR);e=Q.data[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return(OK);}2.出队列1)出队列算法（1）检查队列是否为空，若队空，则进行下溢错误处理；（2）取队首元素的值。（3）将队首指针后移一个位置（即加1）；(4)取队头元素ElemTypeGetHead(SqQueueQ){if(Q.front==Q.rear)return(ERROR);return(Q.data[Q.front]);}(3)队列初始化Q.front=Q.rear=0;(5)判队列空否intQueueEmpty(SqQueueQ){if(Q.front==Q.rear)reurn(1);elsereturn(0);}3.4.3链队列队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：typedefstructqueuenode{ElemTypedata;structqueuenode*next;}QueueNode;typedefstruct{QueueNode*front;QueueNode*rear;}LinkQueue;LinkQueueQ;Q->front队列的头指针Q->rear队列的尾指针运算的实现voidInitQueue(LinkQueue&Q){Q.front=Q.rear=(queuenode*)malloc(sizeof(queuenode));Q.front->next=Q.rear->next=NULL;}q.fq.rnull*q1、创建一个空队列：2、队列的判空:intQueueEmpty(LinkQueueQ){return(Q.front->next==NULL&&Q.rear->next==NULL);}4、出队操作：StatusDeQueue(LinkQueue&Q,ElenType&e){QueueNode*p;if(QueueEmpty(Q))returnERROR;p=Q.front->next;e=p–>data;Q.front->next=p–>next;null*qq.rearxnullq.frontp存储池

if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}队列的应用

队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅举出两个方面例子来说明它，其它应用在后面章节中将会遇到。第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。1、称正读和反读都相同的字符序列为“回文”，例如“abba”，写一个算法，判别读入以“@”为结束符的字符序列是否为“回文”。2、假设以带头结点的循环链表表是队列，并且只设一个指针指向队尾结点，但不设头指针，设计相应的入队和出队算法。intTest()//判别输入的字符串是否回文序列,是返回1,否返回0

{StackS;QueueQ;chara,b;

InitStack(S);InitQueue(