《数据结构课件队列》由会员分享，可在线阅读，更多相关《数据结构课件队列（30页珍藏版）》请在金锄头文库上搜索。
1、n栈栈n栈的应用栈的应用n队列队列n队列的应用队列的应用3.4 3.4 队列队列3.4.1 3.4.1 抽象数据类型队列的定义抽象数据类型队列的定义 队列队列队列队列(Queue)(Queue)(Queue)(Queue)也是一种运算受限的线性表。它也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为删除。允许删除的一端称为队头队头队头队头(front)(front)(front)(front)，允许，允许插入的一端称为插入的一端称为队尾队尾队尾队尾(rear)(rear)(rear)(rear)。（a0,a1,.
2、,ai-1,ai,ai+1,an-1）插入插入删除删除例如：排队购物。操作系统中的作业排队。先例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦进入队列的成员总是先离开队列。因此队列亦称作称作先进先出先进先出(First In First Out)(First In First Out)的线性表，的线性表，简称简称FIFOFIFO表。表。 a a0 0 a a1 1 a a2 2 a an-1n-1rearrear队队头头队队尾尾frontfront队队 列列 的的 示示 意意 图图队列的特点队列的特点先进先出先进先出说明：说明：第一个入队的元素在队头，第一个入队
3、的元素在队头，最后一个入队的元素在队尾，最后一个入队的元素在队尾，第一个出队的元素为队头元素，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素最后一个出队的元素为队尾元素队列的抽象数据定义见书59队列的基本运算队列的基本运算 队列可定义如下五种基本运算：队列可定义如下五种基本运算：1初始化队列初始化队列InitQueue(&Q) 将队列Q设置成一个空队列。2入队列入队列EnQueue(&Q,X)将元素X插入到队尾中，也称“进队” ，“插入”。 3出队列出队列DeQueue(&Q,&e) 将队列Q的队头元素删除，并用e返回其值，也称“退队”、“删除”。4取队头元素取队头元素GetHead
4、(Q,&e) 得到队列Q的队头元素之值，并用e返回其值。5判队空判队空QueueEmpty(Q) 判断队列Q是否为空，若为空返回1，否则返回0。3.4.2 3.4.2 非循环队列和循环队列非循环队列和循环队列分配一块连续的存储区域来存放队列里的元素。由分配一块连续的存储区域来存放队列里的元素。由于队列的队头和队尾的位置是变化的，因而要设两个于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置。指针和分别指示队头和队尾元素在队列中的位置。它们的初始值在队列初始化时均应置为。入队时它们的初始值在队列初始化时均应置为。入队时将新元素插入所指的位置，然后尾指针加。出
5、队将新元素插入所指的位置，然后尾指针加。出队时，删去所指的元素，然后头指针加并返回被删时，删去所指的元素，然后头指针加并返回被删元素。由此可见，元素。由此可见，当头尾指针相等时队列为空当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。针始终指向队尾元素的下一位置。 0 1 2 3FrontrearabcFront rear(a)(a)队列初始为空（队列初始为空（b b）A,B,CA,B,C入队入队 b c front rear front rear（c)a出队出队(d)b,c出队，队为出队，队为空空
6、#defineMAXQSIZE100typedefstructElemTypedataMAXQSIZE;intfront;/*队头位置队头位置*/intrear;/*队尾位置队尾位置*/SqQueue;顺序队列的操作演示顺序队列的操作演示队列的顺序存储结构定义：队列的顺序存储结构定义：SqQueueQQ-front存放即将要被删除的元素的下标。存放即将要被删除的元素的下标。Q-rear存放即将要被插入的元素（目前不在队列中）存放即将要被插入的元素（目前不在队列中）的下标。的下标。Q-dataQ-front和和Q-dataQ-rearn初始化：初始化： Q.front=Q.rear=0n队空：队
7、空：Q.front=Q.rearn队满：队满：Q.rear=maxsize（假溢出）假溢出）n求求队长：队长： Q.rear-Q.frontn 入队：新元素按入队：新元素按 rear 指示位置加入，再将指示位置加入，再将队尾指针加一队尾指针加一 ，即，即 rear = rear + 1n 出队：将出队：将front指示的元素取出，再将队头指示的元素取出，再将队头指针加一，即指针加一，即front = front + 1非循环队列非循环队列注意：注意：入队应考虑队满；出队应考虑队空。入队应考虑队满；出队应考虑队空。 和栈类似，队列中亦有上溢和下溢现象。此外，和栈类似，队列中亦有上溢和下溢现象。此
8、外，和栈类似，队列中亦有上溢和下溢现象。此外，和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在顺序队列中还存在顺序队列中还存在顺序队列中还存在“假上溢假上溢假上溢假上溢”现象。因为在入队和出现象。因为在入队和出现象。因为在入队和出现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元队的操作中，头尾指针只增加不减小，致使被删除元队的操作中，头尾指针只增加不减小，致使被删除元队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际素的空间永远无法重新利用。因此，尽管队列中实际素的空间永远无法重新利用。因此，尽管队列中实际素的空间永远无法重
9、新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于的元素个数远远小于向量空间的规模，但也可能由于的元素个数远远小于向量空间的规模，但也可能由于的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该尾指针巳超出向量空间的上界而不能做入队操作。该尾指针巳超出向量空间的上界而不能做入队操作。该尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。现象称为假上溢。现象称为假上溢。现象称为假上溢。为充分利用向量空间，克服上述假上溢现象，可以为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首尾相接的圆环，并称这种将向量空
10、间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为向量为循环向量，存储在其中的队列称为循环队列循环队列（Circular Queue)。在循环队列中进行出队、入队。在循环队列中进行出队、入队操作时，头尾指针仍要加操作时，头尾指针仍要加1，朝前移动。只不过当，朝前移动。只不过当头尾指针指向向量上界（头尾指针指向向量上界（QueueSize-1）时，其加）时，其加1操作的结果是指向向量的下界操作的结果是指向向量的下界0。 显然，因为循环队列元素的显然，因为循环队列元素的空间可以被利用，除非向量空间空间可以被利用，除非向量空间真的被队列元素全部占用，否则真的被队列元素全部占用，
11、否则不会上溢。因此，除一些简单的不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是应用外，真正实用的顺序队列是循环队列（环形队列）。循环队列（环形队列）。 由于入队时尾指针向前追赶头指针，出队由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过头尾指针均相等。因此，我们无法通过Q-f = Q-r来判断队列来判断队列“空空”还是还是“满满”。 frontfront5 54 04 03 13 12 2J6J6J7J7J8J8J4J4J5J5rearrear012345rearfrontJ5J6J70
12、12345rearfrontJ4J9J8J4J5J6012345rearfront初始状态初始状态J4,J5,J6出队出队J7,J8,J9入队入队队空：队空：front=rear队满：队满：front=rear解决方案：解决方案：1.另外另外设一个标志设一个标志以区别队空、队满以区别队空、队满2.少用一个元素空间少用一个元素空间：队空：队空：Q-front=Q-rear队满：队满：(Q-rear+1)%M=Q-front队空：队空： Q.front =Q. rear队满：队满： Q.front =(Q.rear + 1) % maxSize入队入队: Q.rear = (Q.rear + 1)
13、 % maxSize出队出队: Q.front = (front + 1) % maxSize;求队长求队长: (Q.rear-Q.front+maxSize)%maxSize循环队列循环队列【例例】设设循循环环队队列列的的容容量量为为4040（序序号号从从0 0到到3939），现经过一系列的入队和出队运算后，有），现经过一系列的入队和出队运算后，有 front=11 front=11，rear=19; rear=19; front=19front=19，rear=11rear=11；问问在在这这两两种种情情况况下下，循环队列中各有元素多少个？循环队列中各有元素多少个？答：用队列长度计算公式：
14、答：用队列长度计算公式： (Q.rear-Q.front+maxSize)%maxSize L=（401911）% 40=8 L=（401119）% 40=32 循环队列的循环队列的操作演示操作演示循环队列的基本运算实现循环队列的基本运算实现 1 1、进队列、进队列1）进队列算法）进队列算法2)进队列实现程序进队列实现程序StatusEnQueue(SqQueue&Q,ElemTypee)if(Q.rear+1)%MAXQSIZE=Q.front)return(ERROR);Q.dataQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return(OK);（1）检查队列
15、是否已满，若队满，则进行溢出错误处理；）检查队列是否已满，若队满，则进行溢出错误处理；（2）将新元素赋给队尾指针所指单元；）将新元素赋给队尾指针所指单元；（3）将队尾指针后移一个位置（即加）将队尾指针后移一个位置（即加1），指向下一单元。），指向下一单元。2)出队列实现程序出队列实现程序StatusDeQueue(SqQueue&Q,ElemType&e)if(Q.rear=Q.front)return(ERROR);e=Q.dataQ.front;Q.front=(Q.front+1)%MAXQSIZE;return(OK);2. 2. 出队列出队列1)出队列算法出队列算法（1）检查队列是否
16、为空，若队空，则进行下溢错误处理；）检查队列是否为空，若队空，则进行下溢错误处理；（2）取队首元素的值。）取队首元素的值。（3）将队首指针后移一个位置（即加）将队首指针后移一个位置（即加1）；）；(4)取队头元素取队头元素ElemTypeGetHead(SqQueueQ)if(Q.front=Q.rear)return(ERROR);return(Q.dataQ.front);(3)队列初始化队列初始化Q.front=Q.rear=0;(5)判队列空否判队列空否intQueueEmpty(SqQueueQ)if(Q.front=Q.rear)reurn(1);elsereturn(0);3.4
17、.3 3.4.3 链队列链队列 队列的链式存储结构简称为链队队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。列由头指针和尾指针唯一确定。null*qq.frontq.rear非空队列非空队列q.frontq.rearnull空队列空队列*qn链队列示意图链队列示意图 和顺序队列类似，我们也是
18、将这两个指针封和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型装在一起，将链队列的类型LinkQueueLinkQueue定义为一定义为一个结构类型：个结构类型：typedef struct queuenode ElemType data; struct queuenode *next; QueueNode;typedef struct QueueNode *front; QueueNode *rear; LinkQueue;LinkQueueQ;Q-front队列的头指针队列的头指针Q-rear队列的尾指针队列的尾指针运算的实现运算的实现voidInitQueue(LinkQu
19、eue&Q)Q.front=Q.rear=(queuenode*)malloc(sizeof(queuenode);Q.front-next=Q.rear-next=NULL; q.f q.rnull*q1、创建一个空队列、创建一个空队列：2、队列的判空、队列的判空:intQueueEmpty(LinkQueueQ)return(Q.front-next=NULL&Q.rear-next=NULL);voidEnQueue(LinkQueue&Q,ElemTypee)QueueNode*p;p=(QueueNode*)malloc(sizeof(QueueNode);pdata=x;pnext
20、=NULL;Q.rearnext=p;Q.rear=p;3、入队操作、入队操作null*qq.frontq.rearxnullp4、出队操作：、出队操作：StatusDeQueue(LinkQueue&Q,ElenType&e)QueueNode*p;if(QueueEmpty(Q)returnERROR;p=Q.front-next;e=pdata;Q.front-next=pnext;null*qq.rearxnullq.frontp存储池 if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;队列的应用队列的应用 队列在日常生活中和计算机程序设计中，有着
21、非常重要的作用，在此，仅举出两个方面例子来说明它，其它应用在后面章节中将会遇到。第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。第二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打
22、印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。讨论（本章小结）讨论（本章小结）线性表、栈与队的异同点线性表、栈与队的异同点相相同同点点：逻逻辑辑结结构构相相同同，都都是是线线性性的的；都都可可以以用用顺顺序序存存储储或或链链表表存存储储；栈栈和和队队列列是是两两种种特特殊殊的的线线性性表表，即即受限的线性表受限
23、的线性表（只是对插入、删除运算加以限制）。（只是对插入、删除运算加以限制）。不同点：不同点： 运运算算规规则则不不同同，线线性性表表为为随随机机存存取取，而而栈栈是是只只允允许许在在一一端端进进行行插插入入和和删删除除运运算算，因因而而是是后后进进先先出出表表LIFOLIFO；队队列列是是只只允允许许在在一一端端进进行行插插入入、另另一一端端进进行行删除运算，因而是先进先出表删除运算，因而是先进先出表FIFOFIFO。 用途不同，线性表比较通用；堆栈用于函数调用、用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道递归和简化设计等；队列用于离散事件模拟、多道
24、作业处理和简化设计等。作业处理和简化设计等。1、称正读和反读都相同的字符序列为“回文”，例如“abba”，写一个算法，判别读入以“”为结束符的字符序列是否为“回文”。2、假设以带头结点的循环链表表是队列，并且只设一个指针指向队尾结点，但不设头指针，设计相应的入队和出队算法。intTest()/判别输入的字符串是否回文序列判别输入的字符串是否回文序列,是返回是返回1,否返回否返回0StackS;QueueQ;chara,b;InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c);/同时使用栈和队列两种结构同时使用栈和队列两种结构while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b)returnERROR;returnOK;1 1、试写一个算法判别读入的一个以、试写一个算法判别读入的一个以 为结为结束符的字符序列是否是束符的字符序列是否是“回文回文”。
