顺德水利和国土建设局网站分享型wordpress淘宝客主题

顺德水利和国土建设局网站,分享型wordpress淘宝客主题,做服装设计兼职的网站,文字logo设计生成器文章目录前言一、 队列的概念#xff1a;什么是“队列”#xff1f;1.1 此时此刻#xff0c;想象你在排队1.2 官方定义#xff08;用人话版#xff09;1.3 核心术语与操作1.4 队列的灵魂特性#xff1a;FIFO二、队列的创建#xff1a;用数组“模拟”一条队伍2.1 为什么不…文章目录前言一、 队列的概念什么是“队列”1.1 此时此刻想象你在排队1.2 官方定义用人话版1.3 核心术语与操作1.4 队列的灵魂特性FIFO二、队列的创建用数组“模拟”一条队伍2.1 为什么不直接用链表2.2 模拟思路三个要素就能搞定2.3 实现代码讲解三、队列的基本操作让数据“有序排队”3.1 入队Enqueue新人加入队尾3.2 出队Dequeue老成员离开队头3.3 查询队头元素Front看看“谁在最前面”3.4 查询队尾元素Back看看“谁是最后来的”3.5 判空队伍里还有人吗3.6 计算队列中的元素个数队伍里还有几个人3.7 测试结果结语前言哈喽各位铁子如果你刚看完我上一篇关于 “栈” 的博客应该对 “受限线性表” 这个概念不陌生了 —— 栈是 “先进后出” 的死胡同那咱们日常排队打饭、打印机排队任务这种 “先来先得” 的逻辑对应到数据结构里就是今天的主角队列。一、 队列的概念什么是“队列”1.1 此时此刻想象你在排队在讲枯燥的技术定义之前请大家回想一下我们在学校食堂排队打饭的场景或者去医院排号的经历。在这些场景中有一个绝对的铁律先来的人排在队伍最前面最先打完饭离开后来的人只能乖乖排在队伍的最后面不允许插队中间插入也不允许中途逃跑中间删除。这就是队列Queue的本质。1.2 官方定义用人话版我们在上一章学过“栈Stack”栈像一个死胡同先进后出而队列就像一个单行隧道。队列是一种访问受限的线性表。什么叫“访问受限”就是说你不能随意去动中间的元素它给你的操作权限只有两个只允许在一端进行插入数据操作这端叫队尾。只允许在另一端进行删除数据操作这端叫队头。简单一句话一头进另一头出。我们配合下面这张图来理解核心术语(图解数据的流动方向是从右向左右边进左边出)1.3 核心术语与操作根据上面的图我们来拆解一下队列的“黑话”队头 (Front/Head)队列的第一个元素图中的 A。这是出口只允许在这里做删除操作。队尾 (Rear/Tail)队列的最后一个元素图中的 D。这是入口只允许在这里做插入操作。针对这两个端口引出了两个核心动作入队 (Enqueue)数据从队尾进来的过程。出队 (Dequeue)数据从队头离开的过程。我们再来看一张更动态的图如上图所示a _ 1 a\_1a_1和a _ 2 a\_2a_2已经被红叉划掉了这代表出队删除队头指针向后移动。右侧的空圈圈代表新的位置如果有新数据来就填入这里这叫入队。注意队列也是一种特殊的线性表虽然它操作受限但逻辑上是连续的。1.4 队列的灵魂特性FIFO如果说“栈”的特性是 LIFOLast In First Out后进先出那么“队列”的特性就是FIFO (First In First Out) —— 先进先出First In第一个进入队列的数据最老的数据。First Out一定是第一个被移出队列的。生活中的经典案例打印机任务你按了5次打印打印机一定是你先按的那份文件先打出来不可能先打最后一次按的。键盘输入你快速打字时操作系统会将你的按键存入缓冲区队列先敲的键先上屏。二、队列的创建用数组“模拟”一条队伍2.1 为什么不直接用链表在算法竞赛中我们追求的是速度与简洁。虽然“链表 malloc”可以灵活实现队列但在比赛中这会带来两个问题写得慢—— 需要频繁分配与释放内存容易出错—— 指针操作稍不留神就可能出现段错误Segmentation Fault。因此我们更倾向于使用一种更“笨但稳”的方式用一个足够大的数组来模拟队列。一句话理解我们不再“动态开辟空间”而是先准备一条很长的队伍让数据在里面排队进出。2.2 模拟思路三个要素就能搞定为了让数组表现出“队列”的行为我们只需要三个变量一个数组q[]存放所有排队的数据一个头指针h指向队头的前一个位置一个尾指针t指向队尾元素所在的位置。图解如下 在这张图里q[0] ~ q[4]是队列的有效区域h指向队头前一个位置这里是下标 0t指向队尾元素下标 4对应元素4队列中当前包含的元素是9, 5, 4, 1。 这种定义方式叫“左开右闭区间”风格。也就是说(h, t]是有效元素的范围。只要控制好不越界定义成左闭右开或左开右闭都行看个人习惯。2.3 实现代码讲解下面是我们在算法竞赛中常用的数组队列初始化模板#includeiostreamusingnamespacestd;constintN1e510;// 队列的最大容量// 创建队列数组和两个指针intq[N],h,t;intmain(){// 初始化阶段队列为空h0;t0;cout队列已创建当前为空队列endl;return0;}代码讲解变量名含义初始值说明q[N]存放数据的数组无代表整条队列h队头的前一个位置0初始时队列为空t队尾的位置0初始时与h重合当h t时说明队列是空的。当t不断往后增加入队时队列中就有了数据。太好了陈恭我已经收到了这四张关于入队 / 出队 / 查询队头 / 查询队尾的图片也理解你希望我延续之前那种“生活引入 → 人话定义 → 图解拆解 → 特性总结”的教学风格。下面是为你整理优化好的第二板块内容对应你提供的笔记部分保持原汁原味的可读性与逻辑递进。三、队列的基本操作让数据“有序排队”3.1 入队Enqueue新人加入队尾在生活中入队就像有新顾客来排队。他只能走到队伍的最后面去不能插队也不能跳过前面的人。操作含义把一个新元素x放入队列的末尾。配图理解上方是队列原始状态队头指针h、队尾指针t都指在已有数据上。当新元素x加入时队尾指针t先自增指向下一个空位再把x存进去。代码实现// 入队操作voidpush(intx){q[t]x;// 队尾指针先动再放入新元素}注意⚠️当t N即队尾指针已经指向数组最后一个位置时再插入会导致数组越界溢出。因此在真正写程序时应该先判断是否队满再执行插入。3.2 出队Dequeue老成员离开队头想象食堂打饭排在最前面的人打完饭后离开队伍其后的人自然往前挪一位。队列出队的逻辑完全一样。操作含义删除队头的一个元素最先进入的那一个。配图理解如图所示h是队头指针。当第一个元素出队后只需将h向后移动一位即可。队列中的有效数据区随之变化。代码实现// 出队操作voidpop(){h;// 队头后移相当于“删除”前面的元素}注意⚠️若队列中已经没有元素继续出队会导致访问无效数据。因此在实际应用中出队前应先判断是否为空队。3.3 查询队头元素Front看看“谁在最前面”排队的时候我们有时想知道现在轮到谁打饭了在队列中我们可以通过一个操作快速“查看”队头但并不删除它。操作含义返回队列中第一个有效元素。配图理解注意⚠️这里返回的不是h指针所指的位置而是**h 1** —— 因为h指向的是“队头前一个位置”真正的队头元素在它的下一个位置。代码实现// 查询队头元素intfront(){returnq[h1];}bug提示当队列为空时这样的访问同样会出错越界或读取垃圾值。3.4 查询队尾元素Back看看“谁是最后来的”有时候我们也想知道刚刚来的那位是谁这时就要查看队尾元素。操作含义返回队列中最后一个元素但不删除。配图理解h是队头t是队尾。此时q[t]就是最后一个进入队列的数据。代码实现// 查询队尾元素intback(){returnq[t];}太棒了我已经完全理解你的意图——这两张图片内容属于“第三部分队列的基本操作——让数据‘有序排队’”其中展示了队列的两个最核心功能判空和计算元素个数。我会沿用你之前要求的风格结构来重写生活引入 → 原理解释 → 图解说明 → 代码理解 → 小结提升。3.5 判空队伍里还有人吗想象你在电影院门口排队买票突然队伍空了——售票员看到前面没人就知道“该场次的观众都买完票了”。在队列Queue里也一样我们要经常判断“这个队列现在是不是空的” 定义理解在顺序存储的队列中我们通常用两个指针变量hhead指向队头也就是第一个要离开的元素ttail指向队尾也就是最后一个进来的位置。当一个队列完全为空时说明没有任何人排在里面那么队头指针 h 和 队尾指针 t 会重合。 图解理解(图示当 h t 时说明队列中没有任何有效元素) 代码逻辑解析// 判断队列是否为空boolempty(){returnht;} 这行代码非常直观如果队头和队尾重叠说明没人排队否则说明还有人。一句话总结“头尾相遇队列为空。”3.6 计算队列中的元素个数队伍里还有几个人当我们知道队列不为空时接下来的问题自然是“那现在队伍里到底还有几个人在等” 定义理解在顺序队列中有效元素的数量可以通过简单的减法得到有效元素数 队尾指针位置 - 队头指针位置即size t - h 图解理解(图示此时有效元素为 b 和 c因此队列长度为 2) 代码逻辑解析// 返回队列中有效元素的个数intsize(){returnt-h;}这个公式就像我们数队伍人数一样从第一个人开始数一直到最后一个站着的人。如果队头在位置 2队尾在位置 4那就有4 - 2 2个人。3.7 测试结果结语到这里咱们用数组模拟队列的核心逻辑就讲透啦 —— 本质就是靠h和t两个指针用 “左开右闭” 的区间管好队列的入队、出队操作这种方式在算法竞赛里又快又稳几乎不会出 bug。不过实际项目开发里咱们不用这么 “手动搓轮子”C STL 里自带了现成的queue容器直接调用接口就能完成队列操作。下一篇博客我就带大家盘一盘 STL 的queue从基本操作入队、出队、取队头到实际场景用法看完就能直接在项目里用起来记得蹲我更新哦