《数据结构》课件 第4章 队列

数据结构第4章队列｜先进先出FIFO本章思政+学习目标本章学习要点01队列定义、FIFO特性、基本运算02顺序存储普通顺序队列、假溢出、循环队列03链式存储链队列结构、初始化/入队/出队算法04队列经典应用模拟排队、迷宫最短路径BFS05拓展应用人工智能、操作系统中的拓展应用难点循环队列判空判满、链队出队边界处理。思政要点秩序规则、资源规划、团队调度。本章思政融入01FIFO对应社会排队秩序遵守规则实现公平高效,体现了社会公共秩序的核心价值。02进程调度队列集体服从调度、有序协作,是现代高效工作团队的缩影。资源规划合理规划·节约资源03循环队列内存管理节约资源、合理规划有限资源,展现了对资源的极致尊重。生活直观队列案例1:外卖订单用户下单→入队尾;商家按接单顺序备餐,队首订单优先配送。用户下单新生成的订单自动进入系统等待队列的"队尾",成为最新待处理项。商家备餐与配送商家按接单顺序处理,永远优先操作位于"队首"的订单,体现了队列"先进先出"的核心特性。外卖APP实时追踪界面·订单状态一目了然生活直观队列案例2:网络服务器请求大量用户访问服务器,请求按到达顺序进入任务队列,先到先响应。核心机制服务器无法瞬间处理所有并发请求,需借助"请求队列"进行管理。遵循"先到先响应"的原则,保证数据处理的公平性与有序性。实际应用场景常见于高并发的Web服务、数据库连接池及消息中间件等领域。队列逻辑结构引入:栈VS队列栈Stack操作端一端进出特性LIFO·后进先出示意图垂直结构,所有操作仅在顶端进行。VS队列Queue操作端两端操作特性FIFO·先进先出示意图水平结构,操作分别在头部和尾部进行。4.1.1队列标准定义队列是特殊线性表:队尾(rear)只做插入=入队(Enqueue)队头(front)只做删除=出队(Dequeue)对于队列Q=(a₁,a₂,a₃,…,aₙ)a₁最先入队,也最先出队。aₙ最后入队,也最后出队。数据结构队列示意图·队头、队尾与入队出队操作遵循先进先出(FIFO)的操作原则队列进出规则演示入队顺序a₁→a₂→a₃→…→aₙ元素依次进入队列,形成有序的序列。出队顺序a₁必须最先出队只有当a₁,a₂,...,aₙ₋₁都出队后,aₙ才能出队。FIFO这就是队列的核心原则——"先进先出"FirstInFirstOut,简称FIFO4.1.2队列抽象数据类型ADT数据数据元素集合存储具有相同数据类型的元素。front指向队列头部元素的指针/索引。rear指向队列尾部元素的指针/索引。基础操作1QueueCreate()创建空队列2QueueIsEmpty()判断队列是否为空3QueueEnqueue(elem)入队,将元素加入队列尾部4QueueDequeue()出队,移除并返回队首元素5QueueFront()获取队首元素(不删除)6QueueSize()统计队列中当前的元素个数7QueueDestroy()销毁队列,释放占用的内存空间ADT操作功能详解(1/2)01创建空队列QueueCreate初始化front、rear为空标识。02判空QueueIsEmptyfront与rear相等则队空。03入队QueueEnqueue元素添加到尾部,更新rear指针。ADT操作功能详解(2/2)04出队QueueDequeue删除队首,更新front指针,返回删除值。05获取队首QueueFront只读不删,空队列抛异常。06计算长度QueueSize头尾指针差值。07销毁QueueDestroy释放全部内存,指针置空。队列两大存储总览01顺序队列实现方式:数组实现优点存取快缺点假溢出、容量固定分类普通顺序队列、循环队列02链队列实现方式:单链表实现优点无容量限制、无假溢出缺点额外存储指针分类单链表结构实现的链式队列课堂小提问1思考为什么外卖系统要用队列,不能用栈?参考答案:订单必须遵循"先来先服务"的原则,而栈的"后进先出"特性与此业务逻辑完全不符。课堂小提问2思考:服务器处理用户请求如果不用队列,会出现什么问题?参考答案:01请求处理乱序,导致错误。02高并发时请求丢失或系统崩溃。03无法保证服务的公平性和有序性。小结01队列核心核心特性为FIFO即先进先出的处理规则02两端操作数据元素的处理方式尾入队、头出队仅在两端进行数据操作03广泛应用覆盖多种应用场景生活、服务器等大量实际场景中均有广泛应用04ADT定义抽象数据类型包含7个标准操作定义了完整的操作接口规范学时1课堂练习题01队列和栈的操作特性有什么本质区别?02简述入队、出队操作时,指针是如何变化的?作答区域请在此处书写答案,梳理思路后再对照参考答案。习题参考答案栈在同一端进行插入和删除操作,遵循LIFO(后进先出)原则。队列在两端进行操作,队尾插入、队头删除,遵循FIFO(先进先出)原则。入队队尾指针(rear)向后移动,将新元素存入新的队尾位置。出队队头指针(front)向后移动,取出新的队头位置的元素。4.2.1顺序队列定义使用一维数组存储队列元素,并使用两个标记front和rear来指示队列的位置。约定规则front指向队头元素的前一个位置。rear指向真实的队尾元素。顺序队列假溢出示意图,展示front与rear指针移动的不同状态。顺序队列结构体定义#defineMAXSIZE1024//定义队列的最大容量typedefstruct{ElemTypedata[MAXSIZE];//存储队列元素的数组intrear,front;//队尾标记和队头标记}SeQueue;data用于存储队列元素的数组,大小由MAXSIZE决定。rear队尾指针,指向队列中最后一个有效元素的下一个位置。front队头指针,指向队列中第一个有效元素的位置。顺序队列变量与内存申请01定义队列指针SeQueuesq;02动态分配内存sq=(SeQueue*)malloc(sizeof(SeQueue));数据范围数组data的下标范围是:0到MAXSIZE-1普通顺序队列——入队操作前提队列不满,满足执行入队操作的条件。操作步骤01sq->rear++;队尾指针向后移动一位,指向新的队尾位置。02sq->data[sq->rear]=x;将待入队的新元素x,存入队尾指针指向的新位置。逻辑将队尾指针向后移动一位,然后将新元素存入新的队尾位置。普通顺序队列——出队操作前提队列非空,这是执行出队操作的必要条件。操作步骤01sq->front++;队头指针向后移动一位,指向新的队首元素。02x=sq->data[sq->front];取出并保存当前队头指针所指向的元素。逻辑将队头指针向后移动一位,然后取出新的队头位置的元素。普通顺序队列:判空、判满、长度元素个数m=sq->rear-sq->front通过队尾指针与队头指针的差值,即可计算当前队列中的元素数量。队空条件m==0⇒front==rear当队列中元素个数为0时,队头指针与队尾指针指向同一位置。队满条件m==MAXSIZE⇒rear==MAXSIZE-1当队列中元素个数达到最大容量时,队尾指针到达数组的最后一个下标。顺序队列四种状态示意:空队·有元素·一般情况·溢出普通顺序队列致命缺陷:假溢出现象当队尾指针rear到达数组末尾MAXSIZE-1时,即使队列前面有很多因出队而空出的位置,也无法再进行入队操作。原因数组空间是静态的,指针只能单向移动。示意图·顺序队列假溢出过程,最终状态front=5,rear=9假溢出低效解决方案对比01方案1:元素移动操作每次出队后,将所有元素向前移动。缺点效率极低,时间复杂度为O(n),不推荐。→02方案2:循环队列最优方案操作将数组头尾逻辑上连接起来,形成一个环。优点空间利用率高,效率高。循环队列核心思想将一维数组data[0..MAXSIZE-1]视为一个头尾相接的环形空间。实现关键:取模运算%当指针到达数组末尾MAXSIZE-1时,通过取模运算自动折返到下标0。无论是队头还是队尾指针,在移动时都对数组长度取模,这样指针就能在数组空间内循环移动。循环队列指针更新规则入队尾指针更新q->rear=(q->rear+1)%MAXSIZE;入队时,尾指针向后移动一位,再对最大容量取模。出队头指针更新q->front=(q->front+1)%MAXSIZE;出队时,头指针向后移动一位,同样对最大容量取模。取模作用限制指针下标在0到MAXSIZE-1之间,实现自动循环。当指针到达数组末尾时,再加1取模就会自动回到数组的起始位置,这正是循环队列的核心机制。循环队列矛盾点:空/满标识冲突问题:在循环队列中,front==rear既可能表示队空,也可能表示队满。01队空状态front==rear·指针相遇所有元素都出队了,front和rear相遇。02队满状态front==rear·指针相遇队列被元素填满,rear追上了front。如何区分这两种情况?同一个条件front==rear却对应两种截然不同的语义,这正是我们需要解决的核心矛盾。两种解决冲突方案01增加num变量记录元素总数队空条件num==0队满条件num==MAXSIZE02牺牲一个空位教材文档采用队满条件(q->rear+1)%MAXSIZE==q->front队空条件q->front==q->rear循环队列结构体定义typedefstruct{ElemTypedata[MAXSIZE];intfront,rear;}C_SeQueue;结构说明data存储队列元素的环形数组,用于承载队列中的具体数据。front队头指针,指向队列中第一个有效元素的位置。rear队尾指针,指向队列中最后一个元素的下一个位置。算法4-1循环队列初始化C_SeQueue*Init_SeQueue(){C_SeQueue*q;q=(C_SeQueue*)malloc(sizeof(C_SeQueue));q->front=q->rear=MAXSIZE-1;//初始化指针到数组末尾returnq;}逐行解析01分配内存,创建循环队列结构体。02将队头和队尾指针都初始化为数组的最后一个索引。03返回创建的队列指针,完成初始化。算法4-2循环队列入队intin_C_SeQueue(C_SeQueue*q,ElemTypex){//检查队列是否已满(牺牲一个单元的方式)if((q->rear+1)%MAXSIZE==q->front){printf("队列满");return0;//入队失败}q->rear=(q->rear+1)%MAXSIZE;//队尾指针后移q->data[q->rear]=x;//新元素入队return1;//入队成功}01判断队列状态通过牺牲一个单元的方式,检查队列是否已满。(q->rear+1)%MAXSIZE==q->front02队尾指针后移若队列未满,将队尾指针通过模运算向后移动一位。q->rear=(q->rear+1)%MAXSIZE;03存入新元素将新元素存入当前队尾,并返回成功状态。q->data[q->rear]=x;return1;算法4-3循环队列出队核心实现代码intOut_SeQueue(C_SeQueue*q,ElemType*x){if(q->rear==q->front){//检查队列是否为空printf("队空");return-1;//出队失败}q->front=(q->front+1)%MAXSIZE;//队头指针后移,模运算保证循环特性x=q->data[q->front];//将队头元素赋值给指针变量x,通过指针返回return1;//出队成功}01判空检查首先判断队头指针与队尾指针是否相等,若相等则表示队列为空,无法出队。02指针移动将队头指针front向后移动一位,利用模运算%MAXSIZE保证循环特性。03取值与返回将新的队头元素值赋给指针变量x,并返回1表示出队操作成功。算法4-4循环队列判空intEmpty_SeQueue(C_SeQueue*q){if(q->rear==q->front)return1;//队空elsereturn0;//队非空}说明在牺牲一个单元的方案中,队空条件仍然是:front==rear即当队尾指针rear追上队头指针front时,循环队列即为空。循环队列完整执行演示(MAXSIZE=10)01初始化front=rear=9队头与队尾指针均指向数组下标9,队列初始为空。02入队依次入队a1·a2·a3·a4·a5rear依次变为0,1,2,3,4,指针发生循环。03出队依次出队a1·a2front依次变为0,1,队头位置同步更新。04继续入队入队a6·a7·a8·a9·a10·a11rear依次变为5,6,7,8,9,0。此时(rear+1)%10=1==front,队列满。演示结论:当(rear+1)%MAXSIZE==front时,循环队列即判定为满,有效利用了数组空间。顺序队列VS循环队列对比表普通顺序队列循环队列空间形态线性数组环形数组假溢出存在无判满条件rear==MAXSIZE-1(rear+1)%MAXSIZE==front优缺点实现简单,但会造成一定的空间浪费。空间利用率高,但引入取模运算,实现逻辑略复杂。核心差异:循环队列通过模运算巧妙解决了顺序队列的"假溢出"问题,是对空间资源的更优解。课堂例题:循环队列手动推演初始状态数组容量MAXSIZE=5,队首指针front=4,队尾指针rear=401入队操作依次入队元素:A·B·C02出队操作执行操作:出队一次03入队操作依次入队元素:D·E·F思考任务请手动推演每一步操作后front和rear的值,并判断最终的队列状态。例题推演过程1初始front=4,rear=4(空)2入队Arear=(4+1)%5=0front=4,rear=03入队Brear=(0+1)%5=1front=4,rear=14入队Crear=(1+1)%5=2front=4,rear=25出队front=(4+1)%5=0front=0,rear=26入队Drear=(2+1)%5=3front=0,rear=37入队Erear=(3+1)%5=4front=0,rear=48入队Frear=(4+1)%5=0front=0,rear=0此时(rear+1)%5=1不等于front(0),可以入队。最终状态队列满。根据"牺牲一个单元"的约定,此时front与rear相等,标志着循环队列已满。小结01顺序队列数组实现,存在假溢出问题。02循环队列通过模运算解决假溢出,提高空间利用率。循环队列判空/判满方法一牺牲一个单元,作为区分空满的标志。方法二设置一个独立的计数器,记录队列中元素个数。核心操作入队和出队都通过模运算来移动指针,这是实现循环结构的关键。4.3.1链队列定义使用链表来实现的队列。它由一系列节点组成,每个节点包含数据域和指向下一个节点的指针。优势01动态扩容无需预先分配固定大小的内存。02避免假溢出插入和删除操作只需调整指针。这是它相比顺序队列的最大优势,能够更灵活地适应数据规模的变化。链队列结构定义01定义队列节点·QNodetypedefstructNode{ElemTypedata;structNode*next;}QNode;节点组成包含数据域存储元素值,以及指向下一个节点的指针,构成链式结构。02定义链队列·LQueuetypedefstruct{QNode*front;//队头指针QNode*rear;//队尾指针}LQueue;队列控制结构包含队头指针与队尾指针分别指向链表的头结点和尾结点,便于操作。链队列指针约定(带头结点)通常使用带头结点的链表来实现链队列。头结点一个额外的节点,其next指针指向真正的队头元素。队头指针(front)指向头结点,而不是直接指向第一个数据元素。队尾指针(rear)指向队列中的最后一个数据节点。队空条件q->front==q->rear图示:链式队列的入队与出队操作过程算法4-5链队列初始化LQueue*Init_LQueue(){LQueue*q=malloc(sizeof(LQueue));//创建队列结构体QNode*p=malloc(sizeof(QNode));//创建头结点p->next=NULL;//头结点的next置空q->front=q->rear=p;//头尾指针都指向头结点returnq;}01创建队列结构体调用malloc为队列指针变量q分配内存空间。02创建队列头结点同样调用malloc为队列的第一个节点p分配内存。03初始化头结点指针将头结点p的next指针置空,表示这是一个独立的空节点。04建立空队列状态将队列的头尾指针front与rear都指向头结点p,完成初始化。算法4-6链队列入队voidIn_LQueue(LQueue*q,ElemTypex){QNode*p=(QNode*)malloc(sizeof(QNode));//创建新节点p->data=x;//给新节点赋值p->next=NULL;//新节点的next置空q->rear->next=p;//将新节点链接到队尾q->rear=p;//更新队尾指针}入队操作核心步骤01创建新节点调用malloc分配内存,构造新的数据节点。02节点赋值与初始化为新节点的数据域赋值,并将指针域置空。03链接到队尾将原队尾节点的next指针指向这个新节点。04更新队尾指针将队列的队尾指针rear移动到新加入的节点。新节点成功加入到队尾,入队操作完成。算法4-7链队列判空intEmpty_LQueue(LQueue*q){if(q->front==q->rear)return1;//队空elsereturn0;//队非空}核心结论在带头结点的链队列中,队空条件是:front==rear通过判断队头指针front与队尾指针rear是否指向同一位置,即可确认链队列的空满状态。链队列的判空函数非常简单,只需要检查front指针和rear指针是否相等即可。如果相等,说明队列为空。算法4-8链队列出队(1/2)intOut_LQueue(LQueue*q,ElemType*x){QNode*p;if(Empty_LQueue(q)){//判断队列是否为空printf("队空,不能出队");return0;}p=q->front->next;//p指向真正的队头元素节点q->front->next=p->next;//绕过原队头,指向其后继x=p->data;free(p);//取值并释放节点内存}01判断队列状态调用Empty_LQueue检查队列是否为空,若为空则报错。02定位目标节点用临时指针p指向真正的队头元素节点,便于后续操作。03改变指针指向将头结点的next指针绕过原队头,指向其下一个节点。04取值与释放内存取出原队头节点的数据,并调用free释放该节点的内存。算法4-8链队列出队(2/2)//如果出队后队列变空,需要将rear指针也指向头结点if(q->front->next==NULL){q->rear=q->front;}return1;关键步骤解析if(q->front->next==NULL)这是一个关键步骤。如果出队后队列变为空(即头结点的next为NULL),必须将rear指针重新指向头结点,以维持队空状态的正确性。否则,rear指针会变成一个野指针,导致后续操作出错。链队列完整执行演示01初始化front和rear都指向头结点。初始状态下,两个指针共同指向同一个头结点。02入队A创建节点A,执行指针更新。rear->next=Arear=A03入队B创建节点B,执行指针更新。rear->next=Brear=B04出队A释放节点A,更新front指针。front->next指向Brear保持不变05出队B释放节点B,队列为空时特殊处理。队列为空,置rear=front恢复初始状态顺序队列VS链队列对比表顺序队列(循环队列)存储空间静态数组,大小固定空间利用率可能有少量浪费操作效率入队/出队均为O(1)实现复杂度较复杂,需处理循环适用场景元素数量可预估链队列存储空间动态链表,大小灵活空间利用率无浪费,但有指针开销操作效率入队/出队均为O(1)实现复杂度较简单,只需调整指针适用场景元素数量变化大课堂例题:链队列手动推演初始状态空队列,指针front和rear都指向头结点。01入队10,20,30依次添加三个节点,队列长度变为3。02出队一次操作移除队首节点10,front指针后移。03入队数据:40队尾新增节点40,rear指向新节点。04出队一次操作移除节点20,front指针再次后移。05出队一次操作移除节点30,仅剩节点40。请手动推演每一步操作后链表的结构和front、rear的指向。例题推演过程01初始front→头结点<-rear02入队10,20,30front→头结点→10→20→30<-rear03出队front→头结点→20→30<-rear(删除节点10)04入队40front→头结点→20→30→40<-rear05出队front→头结点→30→40<-rear(删除节点20)06出队front→头结点→40<-rear(删除节点30)最终状态队列中有一个元素,40学时3小结链队列基于链表实现,动态扩容,无假溢出。指针约定通常使用带头结点的链表,front指向头结点,rear指向尾结点。核心操作入队在链表尾部插入节点,移动rear指针。出队在链表头部删除节点,注意处理队空时rear指针的重置。对比顺序队列适合大小固定的场景。链队列适合大小动态变化的场景。通过对比,我们可以根据实际需求选择最合适的队列实现方式。4.4.1应用一:队列管理的模拟问题描述模拟一个队列管理系统。规则如下:01奇数将其从队尾入队输入一个奇数,执行入队操作。02偶数将队头元素出队输入一个偶数,执行出队操作。030直接退出程序输入0,结束当前的队列管理。每次操作后,显示当前队列的内容,便于观察数据结构的实时变化。队列管理模拟:核心算法intmain(){LQueueLQ,*p=&LQ;//定义并指向队列intj;Init_LQueue(p);//初始化队列printf("inputainteger:");scanf("%d",&j);while(j!=0){//循环直到输入0if(j%2==1)In_LQueue(p,j);//奇数入队elseOut_LQueue(p,&j);//偶数出队,更新jOutqueue(p);//显示当前队列状态01初始化队列调用Init_LQueue,创建空链队列。02输入整数判断循环读取输入值j,直到输入为0。03奇偶分支处理奇数入队,偶数调用出队函数。04状态实时反馈每次操作后调用Outqueue显示队列。队列管理模拟:显示队列函数voidOutqueue(LQueue*Q){QNode*p=Q->front;//p从表头开始printf("Queue:");while(p!=Q->rear){//遍历直到队尾p=p->next;//跳过表头,指向第一个元素printf("%d",p->data);}printf("\n");}核心逻辑解析01函数定义与初始化定义Outqueue函数,接收队列指针,初始化指针p指向表头。02遍历条件设置使用while循环,判断条件为指针未到达队尾p!=Q->rear。03数据遍历与输出指针后移指向下一个节点,并打印当前节点的data值。04结束与格式化循环结束后输出换行符,完成整个队列的显示。4.4.2应用二:利用队列求解迷宫最短路径问题回顾在栈的应用中,我们用深度优先搜索(DFS)找到了一条迷宫路径,但不一定是最短的。队列的优势队列可以帮助我们实现广度优先搜索(BFS),天然地找到最短路径。BFS以"层层推进"的方式探索,能保证找到的第一条路径就是迷宫的最短路径。BFS核心思想01从入口点出发,探索所有一步能到达的点(第一层)。02然后,依次从第一层的每个点出发,探索所有尚未访问过的、一步能到达的点(第二层)。03以此类推,像水波一样逐层扩散。04第一个到达出口的路径,就是最短路径。队列的作用:存储每一层需要探索的节点。迷宫问题:数据结构设计队列元素需要记录每个点的坐标(x,y),以及它的前驱点在队列中的位置pre,以便最终回溯路径。typedefstruct{intx,y;//坐标intpre;//前驱节点在队列中的索引}SqType;其他数据结构队列SqTypesq[NUM];迷宫数组maze[m][n]每个位置的状态定义:0通路1墙-1已访问算法4-10迷宫算法详解(1/2)核心代码片段voidpath(intmaze[m][n],itemmove[8]){SqTypesq[NUM];intfront=0,rear=0;//入口点(1,1)入队sq[0].x=1;sq[0].y=1;sq[0].pre=-1;maze[1][1]=-1;//标记为已访问while(front<=rear){//队列不为空intx=sq[front].x;inty=sq[front].y;01初始化队列定义顺序队列sq[NUM],并将队头队尾指针初始化为0。02入口入队与标记将起点(1,1)入队,并将迷宫对应位置置为-1,避免重复访问。03循环探索路径只要队列不为空,持续取出队头元素,获取当前探索的坐标(x,y)。算法4-10迷宫算法详解(2/2)核心逻辑代码//探索8个方向for(intv=0;v<8;v++){inti=x+