什么是环形数组（循环数组）？它有什么用？

简化版

环形数组是把一段普通数组「首尾相接」当成一个环来用的技巧：下标走到末尾后，通过取模 (index + 1) % capacity 绕回开头，让被「用过」的前面空间能循环复用。它不是新数据结构，而是用取模模拟环。典型应用是环形缓冲区（ring buffer）和循环队列。

详细版

普通数组下标是 0 → n-1 走到头就没了。环形数组的核心动作只有一个：下标 +1 后对容量取模，于是 n-1 的下一个自动回到 0：

capacity = 5，下标序列：0,1,2,3,4,0,1,2,3,4,0,...
next = (cur + 1) % capacity

这样数组在逻辑上就成了一个环，没有「尽头」。它带来的好处是前面出队/消费掉的空间可以被后面循环利用，避免普通线性数组「用一格作废一格」的浪费（即循环队列要解决的「假溢出」问题）。

常配一对指针使用：

• 生产者/写指针 tail：写入后 tail = (tail+1) % cap。
• 消费者/读指针 head：读取后 head = (head+1) % cap。

判断空/满通常「留一个空位」（head == tail 为空、(tail+1)%cap == head 为满）或额外记 size。

完整版教学

一、为什么需要「环」

用固定数组做队列时，如果出队只是 head++，那么数组左边被消费掉的格子就永远闲置了，tail 一路往右直到「越界」——明明左边有空位却报满，这叫假溢出。环形数组用取模让 tail 走到末尾能绕回左边那些空格，于是空间循环利用，彻底消除假溢出。一句话：环形数组是为了「空间复用」而生的。

二、取模回绕的本质

(index + 1) % capacity 做的事：正常时就是 +1；到边界 capacity-1 时，(capacity-1+1) % capacity = 0，跳回开头。取模把「一条线」在逻辑上弯成了「一个环」。这也是为什么很多环形缓冲的容量喜欢取 2 的幂——那样 % capacity 可以优化成更快的位运算 & (capacity-1)。

三、典型应用

• 环形缓冲区（Ring Buffer）：固定容量的生产者-消费者缓冲，广泛用于 IO 读写缓冲、日志缓冲、音视频流、网络收发队列。写指针追着读指针跑，容量固定、无需频繁分配内存。
• 循环队列：队列的数组实现，靠环形复用空间。
• 滑动窗口的定长缓存：只保留最近 k 个元素时，用大小 k 的环形数组循环覆盖最旧的。
• 高性能框架：如 Disruptor（高并发队列框架）核心就是一个环形数组，靠它做到无锁、低延迟。

四、判空判满：环形结构的经典难点

环形复用后，head == tail 会同时出现在「空」和「刚好绕一圈填满」两种情况，必须打破二义性：

• 留一个空位：满时让 tail 停在 head 前一格，于是「满」是 (tail+1)%cap == head、「空」才是 head == tail。代价是浪费一格。
• 额外记 size：直接 size==0 判空、size==cap 判满，不浪费空间但多维护一个变量。

五、和普通队列/链表队列的对比

• 环形数组队列：定长、连续内存、缓存友好、无节点分配开销，适合容量上限已知的高性能场景。
• 链表队列：容量无上限、动态分配，但每次入队要 new 节点、缓存不友好。

按「容量是否固定、是否在意性能/内存」来选：定长高性能选环形数组，需要无限增长选链表。

判满方案	判空	判满	特点
空一格	front == rear	(rear + 1) % capacity == front	简单，但浪费一个位置
记录 size	size == 0	size == capacity	不浪费空间，维护字段更多
记录 flag	front == rear && !flag	front == rear && flag	需要在入队/出队时正确更新标记

数字例子：容量为 5 且采用“空一格”方案时，最多只能存 4 个元素。若 front=3、rear=1，有效元素跨过数组末尾，逻辑顺序是下标 3,4,0；下一次入队写到 rear=1，再把 rear 更新为 (1+1)%5=2。

循环数组的重点不是“数组真的变成环”，而是下标用取模回到开头，让固定数组反复利用。

六、常见误区与追问

• 误区：循环数组会自动扩容。 循环数组强调复用固定容量，是否扩容取决于外层容器设计，不是它的必然特性。
• 误区：front == rear 一定表示空。 如果不浪费一个格子或不维护 size/flag，front == rear 也可能表示满。
• 误区：取模操作只用于入队。 出队移动 front、入队移动 rear 都需要用 (index + 1) % capacity 回绕。
• 追问：为什么队列常用循环数组实现？ 普通数组头删要搬移元素，循环数组只移动头尾指针即可做到 O(1)。
• 追问：空一格方案为什么容量少一个？ 它用一个空位区分满和空，否则 front == rear 无法判断是哪种状态。
• 追问：循环数组适合哪些场景？ 固定容量队列、滑动窗口缓冲区、生产者消费者缓冲区、操作系统环形缓冲等。

七、加强记忆

环形数组是用取模 (i+1)%cap 把普通数组首尾相接成环的技巧，让消费掉的前面空间能循环复用，消除「假溢出」。它不是新结构，核心就一个回绕动作。典型用于环形缓冲区、循环队列、定长滑动缓存（Disruptor 等高性能框架的基础）。判空判满要打破 head==tail 二义性：留一格空位或额外记 size。