循环队列头尾指针取模应用技巧

本文深入剖析了循环队列用数组实现时头尾指针（front和rear）的设计逻辑与取模运算的核心技巧：front始终指向队首元素，rear始终指向下一个入队位置（不存数据的“哨兵”），所有指针移动必须实时取模以确保回环安全；通过牺牲一个存储单元（数组长度设为k+1），统一用front==rear判空、(rear+1)%(k+1)==front判满，巧妙化解空满歧义；同时详解了元素个数计算、队首/队尾获取、入队出队流程及内存管理的关键细节——真正掌握的不是代码模板，而是指针物理意义与模运算本质的深度理解。

循环队列用数组实现时，核心就两点：用 front 指向队首元素，用 rear 指向下一个入队位置；所有指针移动都靠 取模运算 实现回环。关键不是“怎么写代码”，而是理解为什么这么判空、这么判满、为什么 rear 总是比实际尾元素多一位。

头尾指针的物理意义必须理清

front 和 rear 都是数组下标，但含义不同：

• front 始终指向当前队列中第一个有效元素（即出队要取的那个）
• rear 始终指向下一个待插入的位置（即入队要放进去的那个下标），它不存数据，只是个“占位哨兵”
• 所以队列中实际元素个数 = (rear − front + capacity) % capacity，这个公式在需要计数但没额外 size 字段时很实用

判空与判满的统一逻辑

空和满都源于同一个现象：front 和 rear 相遇。为避免歧义，最常用且推荐的做法是牺牲一个存储单元——数组长度设为 k+1，只允许存 k 个元素。

• 判空：front == rear（初始状态也是这样）
• 判满：(rear + 1) % (k + 1) == front
  → 因为 rear 是“下一个插入位”，满的时候再往后挪一位刚好撞上 front，留出的那个空位就是区分依据
• 注意：模数必须是 k + 1，不是 k。如果申请了 k 个空间却用 k 取模，判满条件会错位，极易越界或漏判

入队、出队与取模操作细节

每次移动指针后都要立即取模，否则指针会跑出数组范围。别等最后统一处理，要在赋值前就完成映射。

• 入队流程：
  　① 判满 → ② data[rear] = value → ③ rear = (rear + 1) % (k + 1)
• 出队流程：
  　① 判空 → ② front = (front + 1) % (k + 1)
  　→ 不需要清空 data[front] 的值，逻辑上它已不属于队列
• 获取队首：直接 return data[front]（先判空）
• 获取队尾：return data[(rear - 1 + k + 1) % (k + 1)]
  → 减 1 可能为负，加容量再取模确保非负，这是安全写法

内存分配与释放的常见坑

结构体本身 malloc 了，里面的数组也 malloc 了，free 时顺序不能反，也不能漏。

• 创建时：先 malloc 结构体，再 malloc data 数组，大小为 sizeof(int) * (k + 1)
• 销毁时：先 free(obj->a)，再 free(obj)
  → 如果只 free(obj)，data 指针丢失，造成内存泄漏
• 不要对栈上定义的数组（如 int a[10]）做 free，只 free 堆上申请的空间

今天关于《循环队列头尾指针取模应用技巧》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！