考点频率★★★★★数据结构必考选择题常考循环队列的判空/判满条件难度⭐⭐⭐建议重点理解队列的FIFO特性掌握循环队列中front和rear指针的含义以及判空、判满的条件判断1️⃣ 什么是队列队列Queue是一种操作受限的线性表。它的核心特征是只允许在表的一端进行插入在另一端进行删除。队尾Rear允许插入的一端队头Front允许删除的一端核心特性先进先出FIFOFirst In First Out——最先进入队列的元素最先被移出。打个比方队列就像食堂打饭的排队。新来的人站在队伍末尾入队队伍最前面的人打完饭离开出队。先来的人先打饭后来的人后打饭——这就是FIFO。队列在计算机系统里非常常见CPU的进程调度、打印机任务队列、键盘缓冲区……都是队列的应用。2️⃣ 队列的基本操作操作含义时间复杂度入队Enqueue将元素插入到队尾O(1)O(1)O(1)出队Dequeue移除队头元素并返回O(1)O(1)O(1)取队头Front / Peek查看队头元素但不移除O(1)O(1)O(1)判空IsEmpty检查队列是否为空O(1)O(1)O(1)判满IsFull检查队列是否已满顺序队列O(1)O(1)O(1)3️⃣ 顺序队列数组实现3.1 普通顺序队列的“假溢出”问题用数组实现队列时我们使用两个指针front指向队头元素rear指向队尾元素的下一个位置#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];intfront;// 队头指针intrear;// 队尾指针指向下一个空闲位置}SeqQueue;入队操作data[rear] 元素; rear出队操作元素 data[front]; front问题随着入队和出队的进行front和rear都在不断向后移动。当rear MAXSIZE时即使数组前面还有空闲位置因为出队释放了空间也无法再入队了。这就是假溢出。3.2 循环队列解决假溢出核心思想把数组想象成一个首尾相连的环。当rear到达数组末尾时下一步就绕回到数组开头。关键约定软考必考约定项说明front指向队头元素的位置rear指向队尾元素的下一个位置判空front rear判满(rear 1) % MAXSIZE front元素个数(rear - front MAXSIZE) % MAXSIZE⚠️注意循环队列中为了区分“空”和“满”我们牺牲一个存储单元——当(rear1) % MAXSIZE front时判满此时实际上还有一个空位没有放数据。入队操作if((rear1)%MAXSIZEfront){// 队列已满报错}data[rear]元素;rear(rear1)%MAXSIZE;出队操作if(frontrear){// 队列为空报错}元素data[front];front(front1)%MAXSIZE;为什么牺牲一个空间因为我们无法区分front rear到底代表“队列为空”还是“队列为满”。如果不牺牲这个空间两种状态的条件就会完全一样。牺牲一个空间后“满”的条件变成了(rear1)%MAXSIZE front和“空”的条件front rear区分开了。4️⃣ 链式队列链表实现4.1 核心结构链式队列用单链表实现队头是链表的头节点队尾是链表的尾节点。// 队列节点typedefstructQNode{intdata;structQNode*next;}QNode;// 链式队列记录队头和队尾指针typedefstruct{QNode*front;// 队头指针QNode*rear;// 队尾指针}LinkQueue;4.2 基本操作入队在队尾插入新节点QNode*newNode(QNode*)malloc(sizeof(QNode));newNode-data元素;newNode-nextNULL;if(rearNULL){// 队列为空frontrearnewNode;}else{rear-nextnewNode;rearnewNode;}出队移除队头节点if(frontNULL){// 队列为空}QNode*tempfront;元素temp-data;frontfront-next;if(frontNULL){rearNULL;// 队列变空}free(temp);4.3 链式队列的优缺点优点缺点容量动态增长无假溢出问题每个节点需要额外的指针空间不需要预先分配连续空间存储密度低5️⃣ 循环队列 vs 链式队列对比表对比项循环队列顺序链式队列底层结构数组单链表容量固定需预先分配动态增长假溢出问题通过循环解决不存在判空条件front rearfront NULL判满条件(rear1) % MAXSIZE front无受内存限制存储密度高低适用场景元素个数可预知元素个数不可预知6️⃣ 经典例题例题1循环队列判空判满某循环队列的数组大小为 6front 2rear 5则队列中的元素个数为 。A. 2B. 3C. 4D. 5解析元素个数 (rear - front MAXSIZE) % MAXSIZE (5 - 2 6) % 6 9 % 6 3。选B。例题2循环队列判满某循环队列的数组大小为 8若front 3则rear为多少时表示队列已满A. 2B. 3C. 4D. 6解析判满条件为(rear 1) % 8 front即(rear 1) % 8 3→rear 2。选A。例题3判断链式队列不存在“假溢出”问题因为它的存储空间是动态分配的。 解析正确。7️⃣ 记忆口诀队列先进先出队尾入队头出。循环队列看指针判空判满要分清。front rear为空(rear1)%max front为满。元素个数公式记(rear-frontmax)%max。8️⃣ 小测验评论区对答案某循环队列的数组大小为 10front 7rear 2则队列中的元素个数为 。A. 3B. 4C. 5D. 6本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #队列 #循环队列 #链式队列 #数据结构 #软考备考 【数据结构】队列：定义、顺序队列与链式队列
考点频率★★★★★数据结构必考选择题常考循环队列的判空/判满条件难度⭐⭐⭐建议重点理解队列的FIFO特性掌握循环队列中front和rear指针的含义以及判空、判满的条件判断1️⃣ 什么是队列队列Queue是一种操作受限的线性表。它的核心特征是只允许在表的一端进行插入在另一端进行删除。队尾Rear允许插入的一端队头Front允许删除的一端核心特性先进先出FIFOFirst In First Out——最先进入队列的元素最先被移出。打个比方队列就像食堂打饭的排队。新来的人站在队伍末尾入队队伍最前面的人打完饭离开出队。先来的人先打饭后来的人后打饭——这就是FIFO。队列在计算机系统里非常常见CPU的进程调度、打印机任务队列、键盘缓冲区……都是队列的应用。2️⃣ 队列的基本操作操作含义时间复杂度入队Enqueue将元素插入到队尾O(1)O(1)O(1)出队Dequeue移除队头元素并返回O(1)O(1)O(1)取队头Front / Peek查看队头元素但不移除O(1)O(1)O(1)判空IsEmpty检查队列是否为空O(1)O(1)O(1)判满IsFull检查队列是否已满顺序队列O(1)O(1)O(1)3️⃣ 顺序队列数组实现3.1 普通顺序队列的“假溢出”问题用数组实现队列时我们使用两个指针front指向队头元素rear指向队尾元素的下一个位置#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];intfront;// 队头指针intrear;// 队尾指针指向下一个空闲位置}SeqQueue;入队操作data[rear] 元素; rear出队操作元素 data[front]; front问题随着入队和出队的进行front和rear都在不断向后移动。当rear MAXSIZE时即使数组前面还有空闲位置因为出队释放了空间也无法再入队了。这就是假溢出。3.2 循环队列解决假溢出核心思想把数组想象成一个首尾相连的环。当rear到达数组末尾时下一步就绕回到数组开头。关键约定软考必考约定项说明front指向队头元素的位置rear指向队尾元素的下一个位置判空front rear判满(rear 1) % MAXSIZE front元素个数(rear - front MAXSIZE) % MAXSIZE⚠️注意循环队列中为了区分“空”和“满”我们牺牲一个存储单元——当(rear1) % MAXSIZE front时判满此时实际上还有一个空位没有放数据。入队操作if((rear1)%MAXSIZEfront){// 队列已满报错}data[rear]元素;rear(rear1)%MAXSIZE;出队操作if(frontrear){// 队列为空报错}元素data[front];front(front1)%MAXSIZE;为什么牺牲一个空间因为我们无法区分front rear到底代表“队列为空”还是“队列为满”。如果不牺牲这个空间两种状态的条件就会完全一样。牺牲一个空间后“满”的条件变成了(rear1)%MAXSIZE front和“空”的条件front rear区分开了。4️⃣ 链式队列链表实现4.1 核心结构链式队列用单链表实现队头是链表的头节点队尾是链表的尾节点。// 队列节点typedefstructQNode{intdata;structQNode*next;}QNode;// 链式队列记录队头和队尾指针typedefstruct{QNode*front;// 队头指针QNode*rear;// 队尾指针}LinkQueue;4.2 基本操作入队在队尾插入新节点QNode*newNode(QNode*)malloc(sizeof(QNode));newNode-data元素;newNode-nextNULL;if(rearNULL){// 队列为空frontrearnewNode;}else{rear-nextnewNode;rearnewNode;}出队移除队头节点if(frontNULL){// 队列为空}QNode*tempfront;元素temp-data;frontfront-next;if(frontNULL){rearNULL;// 队列变空}free(temp);4.3 链式队列的优缺点优点缺点容量动态增长无假溢出问题每个节点需要额外的指针空间不需要预先分配连续空间存储密度低5️⃣ 循环队列 vs 链式队列对比表对比项循环队列顺序链式队列底层结构数组单链表容量固定需预先分配动态增长假溢出问题通过循环解决不存在判空条件front rearfront NULL判满条件(rear1) % MAXSIZE front无受内存限制存储密度高低适用场景元素个数可预知元素个数不可预知6️⃣ 经典例题例题1循环队列判空判满某循环队列的数组大小为 6front 2rear 5则队列中的元素个数为 。A. 2B. 3C. 4D. 5解析元素个数 (rear - front MAXSIZE) % MAXSIZE (5 - 2 6) % 6 9 % 6 3。选B。例题2循环队列判满某循环队列的数组大小为 8若front 3则rear为多少时表示队列已满A. 2B. 3C. 4D. 6解析判满条件为(rear 1) % 8 front即(rear 1) % 8 3→rear 2。选A。例题3判断链式队列不存在“假溢出”问题因为它的存储空间是动态分配的。 解析正确。7️⃣ 记忆口诀队列先进先出队尾入队头出。循环队列看指针判空判满要分清。front rear为空(rear1)%max front为满。元素个数公式记(rear-frontmax)%max。8️⃣ 小测验评论区对答案某循环队列的数组大小为 10front 7rear 2则队列中的元素个数为 。A. 3B. 4C. 5D. 6本专栏日更点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #队列 #循环队列 #链式队列 #数据结构 #软考备考