大学《数据结构》第三章：栈和队列-第三节-队列（一）

第三节队列（一）一、队列的定义及其运算1、队列的定义队列（Oueue）是一种操作受限的线性表，它只允许在表的一端进行元素插入，而在另一端进行元素删除。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。新插入的结点只能添加到队尾，被删除的只能是排在队头的结点，因此，队列又称为先进先出(FirstInFirstOut)的线性表，简称为FIFO表。【真题选解】某队列初始为空，若它的输入序列为（a，b，c，d），它的输出序列应为（）。A．a，b，c，dB．d，c，b，aC．a，c，b，dD．d，a，c，b隐藏答案【答案】A【解析】队列的出队序列一定与入队序列完全一样。2、队列的基本运算(1)置空队列InitQueue(Q)，构造一个空队列。(2)判队空QueueEmpty(Q)，若Q为空队列，则返回TRUE，否则返回FALSE。(3)入队列En(jueue(Q，x)，若队列不满，则将数据x插入到Q的队尾。(4)出队列DeQueue(Q)，若队列不空，则删除队头元素，并返回该元素。(5)取队头GetFront(Q)，若队列不空，则返回队头元素。二、顺序循环队列1、顺序队列的概念队列的顺序存储结构称为顺序队列。队列的顺序存储结构是利用一块连续的存储单元存放队列中的元素的，设置两个指针front和rear分别指示队头和队尾元素在表中的位置。【例】设有一顺序队列Q，容量为5，初始状态时Q.front=Q.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理。（1）d，e，b入队（2）d，e出队（3）i，j入队（4）b出队（5）n，o，p入队【解答】队列及其头尾指针的状态变化情况如图所示第（5）步操作无法进行，因队列已满，再有元素入队，就会溢出，发生假溢。2、顺序循环队为了解决顺序队的"假溢"问题采用循环队。约定循环队的队头指针指向队头元素在数组中实际位置的前一个位置，队尾指针指示队尾元素在数组中的实际位置。其次再约定队头指针指示的结点不用于存储队列元素，只起标志作用。这样当队尾指针"绕一圈"后赶上队头指针时视为队满。【例】设Q是一个有11个元素存储空间的顺序循环队列，初始状态Q．front=Q．rear=0，写出下列操作后头、尾指针的变化情况，若不能入队，请说明理由。d，e，b，g，h入队；d，e出队；i，j，k，l，m入队；b出队；n，o，p，q，r入队【解答】注意：p入队以后，队列就满了，不能再入队了，此时队列中的元素个数为10个（数组长度是11）总结：队中元素个数：

两种情况合并为：（QueueSize+rear-front）%QueueSize；【真题选解】设循环队列的容量为50(序号从0到49)，现经过一系列的入队和出队运算后，有①front=11，rear=29；②front=29，rear=11；在这两种情况下，循环队列中的元素个数分别是______和______。隐藏答案【解析】当front=11，rear=29时，循环队列中的元素个数=rear-front=29-11=18；当front=29，rear=11时，循环队列中的元素个数50-（front-rear）=50+rear-front=50+11-29=32。【答案】18323、循环队的顺序存储的类型定义#defineQueLleSize100typedefcharDataType；//假设数据为字符型typedefstruct{DataTypedata[QueueSize]；intfront，rear；}CirQueue；4、循环队列基本运算的各算法（1）置空队列voidInitQueue(CirQueue*Q){Q->front=Q->rear=0;}（2）判队空intQueueEmpty(CirQueue*Q){returnQ->rear==Q->front；}（3）判队满intQueueFull(CirQueue*Q){return(Q->rear+1)%QueueSize==Q->front;}(4)入队列voidEnQueue(CirQueue*Q，DataTypex){//插入元素x为队列Q新的队尾元素if(QueueFull(Q))printf("Queueoverflow")；e1se{Q->data[Q->rear]=x；Q->ear=(Q->rear+1)％QueueSize；//循环意义下的加1}}（5）取队头元素DataTypeGetFront(CirQueue*Q){//获取Q的队头元素值if(QueueEmpty(Q)){printf("Queueempty");exit(0)；｝elsereturnQ->data[Q->front]j｝（6）出队列DataTypeDeQueue(CirQueue*Q){//删除Q的队头元素，并返回其值DataTypex；if(QueueEmpty(Q)){printf("Queueempty")；exit(0)；}else{x=Q->data[Q->front];//保存待删除元素值Q->front=(Q->front+1)％QueueSize；//头指针加1returnx；//返回删除元素值}}【例】设栈S=(1，2，3，4，5，6，7)，其中7为栈顶元素。请写出调用函数Algo(S)后栈S的状态。其函数为：voidAlgo(SeqStackS){inti=l；CirQueueQ；SeqStackT;//定义一个循环队列和一个栈InitQueue(&Q);Initstack(&T)；//初始化队列和栈while(!StackEmpty(&S)){if(i％2!=0)Push(&T，Pop(&S))；//栈中序号为奇数的元素入T栈中//7、5、3、1顺序入栈T。elseEnQueue(&Q，Pop(&S))；//序号为偶数的元素入队列Q中//6、4、2顺序入队Q。i++；}while(!QueueEmpty(&Q))Push(&S，DeQueue(&Q))；//队Q中6、4、2顺序出队并入栈Swhile(!StackEmpty(&T))Push(&S，Pop(&T));//队栈T中按1、3、5、7顺序出栈并入栈S}最后栈S中的元素为（6、4、2、1、3、5、7）。三、链队1、链队的定义队列的链式存储结构称为链队列。它是一种限制在表头删除和表尾插入操作的单链表。2、链队的数据类型定义typedefstructqnode{DataTypedata;structqnode*next;｝QueueNode；typedefstruct{QueueNode*front；//队头指针QueueNode*rear；//队尾指针｝LinkQueue；LinkQueueQ；3、链队的基本运算实现（1）构造空队列voidInitQueue(LinkQueue*Q){Q->front=(QueueNode*)malloc(sizeof(QueueNode))；//申请头结点Q->rear=Q->front;//尾指针也指向头结点Q->rear->next=NULL;)（2）判队空intQueueEmpty(LinkQueue*Q){returnQ->rear==Q->front；//头尾指针相等队列为空)（3）入队列voidEnQueue(LinkQueue*Q，DataTypex){//将元素x插入链队列尾部QueueNode*p=(QueueNode*)malloc(Sizeof(QueueNode));//申请新结点p->data=x;p->next=NULL;Q->rear->next=p；//*p链到原队尾结点之后Q->rear=p;//队尾指针指向新的队尾结点}（4）取队头元素DataTypeGetFront(LinkQueue*Q){//取链队列的队头元素值if(QueueEmpty(Q))//判队空{printf("Queueunderflow")；exit(0)；//出错退出处理}elsereturnQ->front->next->data；//返回原队头元素值)（5）出队列链队列的出队操作有两种不同情况要分别考虑。①当队列的长度大于1时，则出队操作只需要修改头结点的指针域即可，尾指针不变,类似于单链表删除首结点，操作步骤：s=Q->front->next；Q->fron->next=s->next；x=s->data；free(s)；returnx；//释放队头结点，并返回其值②若列队长度等于l，则出队时不仅要修改头结点指针域，而且还需要修改尾指针。s=Q->front->next；Q->front->next=NULL；//修队头指针Q->rear=Q->front；//修改尾指针x=s->data；free(s)；returnx；//释放队头结点，并返回其值为了方便，直接删除头结点，将原队头结点当头结点使，这样算法就简单了。链队列的出队算法描述DataTypeDeQueue(LinkQueue*Q){//删除链队列的头结点，并返回头结点的元素值QueueNode*P；if(QueueEmpty(Q)){printf("Queueunderflow")；exit(0)；//出错退出处理}else{p=Q->front；//p指向头结点Q->front=Q->front->next;//头指针指向原队头结点free(p)；//删除释放原头结点return(Q->front->data);//返回原队头结点的数据值}}【真题选解】算法f31的功能是清空带头结点的链队列Q.请在空缺处填入合适的内容,使其成为一个完整的算法.typedefstructnode{DataTypedata；structnode*next；}QueueNode；typedefstruct{QueueNode*front；//队头指针QueueNode*rear；//队尾指针}LinkQueue；voidf31(LinkQueue*Q){QueueNode*p,*s；p=(1)；while(p！=NULL){s=p；p=p->next;free(s);}________(2)=NULL;Q->rear=_______(3)_______；}(1)__________________________________________(2)__________________________________________(3)__________________________________________隐藏答案【解析】算法f31的功能是清空带头结点的链队列Q，就是要删除除了头结点以外的所有结点，指针p负责扫描整个队列，所以第（1）空应该填Q->front->next。通过执行while循环，删除了除了头结点以外的所有结点，最后要将头结点的指针域填上NULL，队尾指针指向头结点。所以，第（2）空应该填Q->front->next，第（3）空填Q->front。【答案】（1）Q->front->next（2）Q->front->next（3）Q->front4、循环链队列循环链队列的类型定义typedefstructqueuenode{DataTypedata；structqueuenode*next；}QueueNode；QuelaeNode*rear；（1）初始化空队列QueueNode*InitQueue(QueueNode*rear){tear=(QueueNode*)malloc(sizeof(QueueNode))；//申请头结点rear->next=rear；returnrear；}（2）入队列voidEnQueue(QueueNode*rear，Datatypex){QueueNode*s=(QueueNode*)malloc(sizeof(QueueNode))；//申请新结点s->data=x：s->next=rear->next；rear->next=s；rear=s；}当前讲授（3）出队列DataTypeDelQueue(QueueNode*rear){QueueNode*s，*t；DataTy