目录什么是假溢出如何解决链式队列的结构出队举例总结顺序队列顺序存储的队列会发生“假溢出”这是它的一个典型问题。什么是假溢出假溢出指的是队列的存储空间还有空闲位置但由于队头指针已经移动队尾指针到达了数组末尾导致无法继续入队。也就是说逻辑上有空位物理上却不能利用举个例子假设顺序队列用数组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释放原来的 Afree(p)所以新的 front 就是原来 front 的下一个结点。front 是一个指针变量它自己有地址 frontp 是一个指针变量它自己有地址 p它们里面存的是节点的地址总结队列类型会不会假溢出普通顺序队列✅ 会循环队列❌ 不会链式队列❌ 不会只受内存限制顺序队列存在“假溢出”问题循环队列用于解决假溢出。
目录什么是假溢出如何解决链式队列的结构出队举例总结顺序队列顺序存储的队列会发生“假溢出”这是它的一个典型问题。什么是假溢出假溢出指的是队列的存储空间还有空闲位置但由于队头指针已经移动队尾指针到达了数组末尾导致无法继续入队。也就是说逻辑上有空位物理上却不能利用举个例子假设顺序队列用数组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释放原来的 Afree(p)所以新的 front 就是原来 front 的下一个结点。front 是一个指针变量它自己有地址 frontp 是一个指针变量它自己有地址 p它们里面存的是节点的地址总结队列类型会不会假溢出普通顺序队列✅ 会循环队列❌ 不会链式队列❌ 不会只受内存限制顺序队列存在“假溢出”问题循环队列用于解决假溢出。
)
