顺序队列假溢出及链式队列

目录

什么是假溢出？

如何解决？

 链式队列的结构

出队举例：

总结

顺序队列（顺序存储的队列）会发生“假溢出”，这是它的一个典型问题。

什么是假溢出？

假溢出指的是：

队列的存储空间还有空闲位置，但由于队头指针已经移动，队尾指针到达了数组末尾，导致无法继续入队。

也就是说，逻辑上有空位，物理上却不能利用，举个例子

假设顺序队列用数组 Q[5] 存储：

下标: 0 1 2 3 4
—————–
Q: A B C D E

初始：

front = 0
rear = 5

队列满。

现在连续出队两个元素：

出队 A、B

下标: 0 1 2 3 4
—————–
Q: 空 C D E

front = 2
rear = 5

此时数组前面：

Q[0], Q[1]

已经空出来了，如果继续入队 F，按照普通顺序队列的规则：

rear = 5

已经超过数组最大下标，因此认为“队满”。

但实际上：

Q[0]、Q[1]还有空间

所以这就是假溢出。

如何解决？

常用方法：采用循环队列（推荐）让数组首尾相连：队尾到末尾后可以回到开头继续存储。

0 → 1 → 2 → 3 → 4 → 0

移动元素：每次出队后把剩余元素向前移动，但效率低，时间复杂度高。

链式队列是指采用链式存储结构实现的队列，通常用单链表表示。它通过指针连接各个结点，不需要连续的存储空间。

 链式队列的结构

一个链式队列通常设置两个指针：

• 队头指针 front：指向队头结点（出队位置）
• 队尾指针 rear：指向队尾结点（入队位置）

结构如下：

front rear
↓ ↓
[数据|next] → [数据|next] → [数据|null]

出队举例：

原来的链式队列：

front
↓
[A] → [B] → [C] → NULL
↑
rear

操作步骤：保存原 front 结点.front 后移：

p = front
front = front->next

此时：

front
↓
[B] → [C] → NULL
↑
rear

释放原来的 A：

free(p)

所以新的 front 就是 原来 front 的下一个结点。

front 是一个指针变量，它自己有地址 &front p 是一个指针变量，它自己有地址 &p 它们里面存的是节点的地址

总结

顺序队列存在“假溢出”问题，循环队列用于解决假溢出。