环形数组：介绍、应用、下标计算
一、环形数组介绍
对于普通数组来说，头尾的下标都是固定的，头下标为0,尾下标为length-1。
而环形数组(circular array)通常使用两个额外的数字去标识数组的头下标和尾下标。
环形数组的逻辑结构如下图：
环形数组的逻辑结构
这个像甜甜圈一样的逻辑结构即为环形数组，而在物理上它的形式还是个普通的数组。
环形数组的结构特点：
长度固定，下标永不越界，通常用两个指针标识数组的真实头尾下标。
环形数组优点：
结构较灵活，越界时可以根据业务需求选择处理方式。
结构空间利用率高，并且数组充分利用了局部性原理及CPU缓存，性能好。
环形数组缺陷：
头尾之间的元素不好维护，从中间删除某个元素会出现数组空隙。
这不是一个必须的结构，但是特定时候使用有奇效。
小结：
环形数组就是一个允许越界的数组结构。其可以在越界后通过取余的方式得到一个数组中存在的下标。
二、应用和场景
环形数组默认头尾下标都是0，它可以轻易的实现栈和队列。
栈
做栈操作的话：
新增元素：头下标+1;删除元素：头下标元素弹出、头下标-1。
队列
做队列操作的话：
新增元素，头下标+1;删除元素：尾下标元素弹出、尾下标+1;
而真正重点其实在
下标越界
的处理上。
如果发现首尾重合或元素满了便阻塞操作，这就可以是个
阻塞栈、阻塞队列
;
如果发现首尾重合或元素满了便覆盖数据，这就可以是个
环、可以是缓存
;
当然上述只是提出一个可实现的思路，工程中的阻塞队列等并不一定都是这么实现的，重点是理解这个结构都能干什么。
不过JAVA中JUC包的ArrayBlockingQueue核心就是一个带有takeIndex和putIndex的环形数组，这个设计保证了在队列元素数量固定的限制条件下，有效的利用数组空间并用lock实现了阻塞，构造了一个简单的生产消费模式。（具体细节差异读者可自行阅读源码）
Ringbuffer缓冲
数组本身访问就会得到优化，可以充分利用cpu并对缓存友好。这个特性可以完成一些高性能要求的使用场景，作为一个环形缓存使用的话，可以写数组头部且淘汰尾部数据，写满了或者删光了，可以直接阻塞处理，避免了锁争用，而且空间占用控制简单。这个利用很广，Distruptor、新版本canal等很多组件都有类似使用。
时间轮
kafka、zookeeper中采用时间轮来进行计数，本质也是个环形数组。
三、下标计算
下标加法
比如数组长度是6,当前索引位置在4，向前两位则下标应变为0。
逻辑结构
物理结构
正向比较简单，将当前索引和移动步数相加后的结果对数组length取余即可。
(4+2)%6 = 0
如果从位置0再前进10位则为：
(0+10)%6= 4
看起来非常OK。
下标减法
因为负数取余也是负数的问题，反向就有点烧脑了。（取模没有这个问题，比如python的%）
比如当前位置为1,我需要对其位置-2,那么向后两位下标应该是5。
如果还按照正向计算的话：
(1-2) % 6 = -1
减法逻辑结构
如果是python的话，这个下标-1已经可用了。不过java是没法接受负数下标的，我们只好画图研究一下：
可以发现负数下标再加一个长度的距离就可以变为对应的正数下标！
也就是：
(1-2)%6=-1
-1+6=5
这就正确了。
四、化简和总结
根据以上观察，我们得到的临时结论为：
正向前进下标=(当前下标+前进步数) % 总长度
反向前进下标=((当前下标-后退步数) % 总长度) + 总长度
可以尝试做一个化简：
因为步数会根据前进和后退自行调整正负号，所以：
正向前进下标=(当前下标+步数) % 总长度
反向前进下标=(当前下标+步数) % 总长度 +总长度
同时，我们可以思考，当数组长度为6时,我们前进6步和前进12步的位置是相同的，前进5步和前进11步位置也是相同的。所以我们可以直接把步数+长度再对长度取余，就能得到真实的前进步数，这样不管是正向前进还是反向前进，公式可以统一变为：
再进行推广可以发现：
最终下标= （(当前下标+步数) % 总长度 +总长度）% 总长度
喜欢请点个关注，谢谢～