Mark's Backyard< Back to Blog
#Data Structure#Computer Science#408
队列的实现方式——从约束条件到决策树
Tech Sharing513 words
最近回顾数据结构，发现自己在逻辑结构和物理结构的对应关系选择中总是做错，上网搜了搜方法也没有比较易于理解的方法，于是自己做了个决策树建模，有一个大致的印象，理清楚不少思路。
决策树中的关键约束
在画这棵树时，我固定了以下几个判断维度（也是 408 的高频考点）：
- 存储方式：顺序 / 链式
- 是否循环：解决“假溢出”与“双端访问”
- 链表类型：单向 / 双向
- 指针设置：头指针 / 尾指针 / 头尾双指针
- 头结点：是否引入哨兵结点简化边界
其中最关键的一条经验是：
非循环结构必须头尾双指针；循环结构才有可能只用一个指针。
各类实现的性能指标对比
| 实现方式 | 判空 | 判满 | 入队 | 出队 | 空间开销 | 推荐度 |
|---|---|---|---|---|---|---|
| 顺序循环队列 | front == rear | (rear+1)%M == front | O(1) | O(1) | 低 | ⭐⭐⭐ |
| 非循环单链 + 头+尾（带头） | front->next == NULL | 无 | O(1) | O(1) | 中 | ⭐⭐⭐ |
| 非循环单链 + 头+尾（无头） | front == NULL | 无 | O(1) | O(1) | 中 | ⭐⭐ |
| 循环单链 + 仅尾指针 ⭐ | rear->next == rear | 无 | O(1) | O(1) | 最低 | ⭐⭐⭐⭐⭐ |
| 循环双链 + 仅尾指针 | rear->next == rear | 无 | O(1) | O(1) | 高 | ⭐⭐⭐ |
| 循环双链 + 头+尾 | front == NULL | 无 | O(1) | O(1) | 最高 | ⭐⭐ |
一个容易忽视的细节：头结点
头结点并不是为了“省时间”或“省空间”，而是为了消除空队列的特殊性：
- 链队：删空后容易涉及
rear悬空，带头结点更安全。 - 链栈：操作单一，
top == NULL已足够清晰，不带头结点更简洁。 - 循环链队：闭环结构天然解决了边界问题，通常不需要头结点。
栈的物理和逻辑关系
栈分为 顺序栈（数组实现）和 链栈（单链表）
用双链表完全没有必要，太过剩了，而且栈的最佳选择是唯一的，也就是下面的这种情况：
- 操作在表头
- 只有头指针
- 不带头结点
- 单向
- 非循环
Copyright
- Author:Mark Xu
- Copyright:All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating otherwise.