【环形数组技巧及实现】

一、环形数组原理

环形数组技巧利用求模（余数）运算（5%2=1），将普通数组变成逻辑上的环形数组，可以让我们用 O(1) 的时间在数组头部增删元素。

# 长度为 5 的数组
arr = [1, 2, 3, 4, 5]
i = 0
# 模拟环形数组，这个循环永远不会结束
while i < len(arr):
    print(arr[i])
    i = (i + 1) % len(arr)

环形数组的原理就是取余，当 i+1为数组的最后一个元素的时候， i+1 对 len(arr)取模，就成了0，然后会重新进入数组的头部，就在逻辑上形成了一个环形数组

环形数组的关键在于，它维护了两个指针 start 和 end，start 指向第一个有效元素的索引，end 指向最后一个有效元素的下一个位置索引。

这样，当我们在数组头部添加或删除元素时，只需要移动 start 索引，而在数组尾部添加或删除元素时，只需要移动 end 索引。

当 start, end 移动超出数组边界（< 0 或 >= arr.length）时，我们可以通过求模运算 % 让它们转一圈到数组头部或尾部继续工作，这样就实现了环形数组的效果。

二、应用

循环数组的特点是，当数组的末尾被填满时，可以循环回到数组的开头继续使用空间。

环形数组的区间被定义为左闭右开的，即 [start, end) 区间包含数组元素

理论上，你可以随意设计区间的开闭，但一般设计为左闭右开区间是最方便处理的

理论上，你可以随意设计区间的开闭，但一般设计为左闭右开区间是最方便处理的。

因为这样初始化 start = end = 0 时，区间 [0, 0) 中没有元素，但只要让 end 向右移动（扩大）一位，区间 [0, 1) 就包含一个元素 0 了。

如果你设置为两端都开的区间，
那么让 end 向右移动一位后开区间 (0, 1) 仍然没有元素；

如果你设置为两端都闭的区间，
那么初始区间 [0, 0] 就已经包含了一个元素。

这两种情况都会给边界处理带来不必要的麻烦，如果你非要使用的话，需要在代码中做一些特殊处理。

在数组增删头部元素的时间复杂度是 O(N)，因为需要搬移元素。

但是，如果我们使用环形数组，其实是可以实现在 O(1)的时间复杂度内增删头部元素的。 

环形数组也可以删除指定索引的元素，也要做数据搬移，和普通数组一样，复杂度是 O(N)

环形数组也可以获取指定索引的元素（随机访问），只不过不是直接访问对应索引，而是要通过 start 计算出真实索引，但计算和访问的时间复杂度依然是 O(1)

环形数组也可以在指定索引插入元素，当然也要做数据搬移，和普通数组一样，复杂度是 O(N)