考点频率：★★★★★（数据结构必考，选择题常考循环队列的判空/判满条件）
难度：⭐⭐⭐
建议：重点理解队列的FIFO特性，掌握循环队列中front和rear指针的含义，以及判空、判满的条件判断
1️⃣ 什么是队列？
队列（Queue）是一种操作受限的线性表。它的核心特征是：只允许在表的一端进行插入，在另一端进行删除。
- 队尾（Rear）：允许插入的一端
- 队头（Front）：允许删除的一端
核心特性：先进先出（FIFO，First 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 |
⚠️注意：循环队列中，为了区分“空”和“满”，我们牺牲一个存储单元——当
(rear+1) % MAXSIZE == front时判满，此时实际上还有一个空位没有放数据。
入队操作：
if((rear+1)%MAXSIZE==front){// 队列已满，报错}data[rear]=元素;rear=(rear+1)%MAXSIZE;出队操作：
if(front==rear){// 队列为空，报错}元素=data[front];front=(front+1)%MAXSIZE;为什么牺牲一个空间？
因为我们无法区分front == rear到底代表“队列为空”还是“队列为满”。如果不牺牲这个空间，两种状态的条件就会完全一样。牺牲一个空间后，“满”的条件变成了(rear+1)%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->next=NULL;if(rear==NULL){// 队列为空front=rear=newNode;}else{rear->next=newNode;rear=newNode;}出队（移除队头节点）：
if(front==NULL){// 队列为空}QNode*temp=front;元素=temp->data;front=front->next;if(front==NULL){rear=NULL;// 队列变空}free(temp);4.3 链式队列的优缺点
| 优点 | 缺点 |
|---|---|
| 容量动态增长，无假溢出问题 | 每个节点需要额外的指针空间 |
| 不需要预先分配连续空间 | 存储密度低 |
5️⃣ 循环队列 vs 链式队列（对比表）
| 对比项 | 循环队列（顺序） | 链式队列 |
|---|---|---|
| 底层结构 | 数组 | 单链表 |
| 容量 | 固定（需预先分配） | 动态增长 |
| 假溢出问题 | 通过循环解决 | 不存在 |
| 判空条件 | front == rear | front == NULL |
| 判满条件 | (rear+1) % MAXSIZE == front | 无（受内存限制） |
| 存储密度 | 高 | 低 |
| 适用场景 | 元素个数可预知 | 元素个数不可预知 |
6️⃣ 经典例题
例题1（循环队列判空判满）：某循环队列的数组大小为 6，front = 2，rear = 5，则队列中的元素个数为（ ）。
A. 2
B. 3
C. 4
D. 5
解析：元素个数 =(rear - front + MAXSIZE) % MAXSIZE = (5 - 2 + 6) % 6 = 9 % 6 = 3。选B。
例题2（循环队列判满）：某循环队列的数组大小为 8，若front = 3，则rear为多少时表示队列已满？
A. 2
B. 3
C. 4
D. 6
解析：判满条件为(rear + 1) % 8 == front，即(rear + 1) % 8 == 3→rear = 2。选A。
例题3（判断）：链式队列不存在“假溢出”问题，因为它的存储空间是动态分配的。（ ）
解析：正确。
7️⃣ 记忆口诀
队列先进先出，队尾入队头出。
循环队列看指针，判空判满要分清。front == rear为空，(rear+1)%max == front为满。
元素个数公式记：(rear-front+max)%max。
8️⃣ 小测验（评论区对答案）
某循环队列的数组大小为 10，
front = 7，rear = 2，则队列中的元素个数为（ ）。
A. 3
B. 4
C. 5
D. 6
🔔本专栏日更，点击头像 → 专栏《软考中级高频考点》订阅，第一时间接收新内容
#软考中级 #软件设计师 #队列 #循环队列 #链式队列 #数据结构 #软考备考