环形数组原理
数组可能是环形的么？不可能。数组就是一块线性连续的内存空间，怎么可能有环的概念？
但是，我们可以在「逻辑上」把数组变成环形的，比如下面这段代码：
这段代码的关键在于求模运算 %，也就是求余数。当 i 到达数组末尾元素时，i + 1 和 arr.length 取余数又会变成 0，即会回到数组头部，这样就在逻辑上形成了一个环形数组，永远遍历不完。
这就是环形数组技巧。这个技巧如何帮助我们在 O(1) 的时间在数组头部增删元素呢？
是这样，假设我们现在有一个长度为 6 的数组，现在其中只装了 3 个元素，如下（未装元素的位置用 _ 标识）：
现在我们要在数组头部删除元素 1，那么我们可以把数组变成这样：
即，我们仅仅把元素 1 的位置标记为空，但并不做数据搬移。
此时，如果我们要在数组头部增加元素 4 和元素 5，我们可以把数组变成这样：
你可以看到，当头部没有位置添加新元素时，它转了一圈，把新元素加到尾部了。
核心原理
上面只是让大家对环形数组有一个直观地印象，环形数组的关键在于，它维护了两个指针 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] 就已经包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦，如果你非要使用的话，需要在代码中做一些特殊处理。
最后，我给出一个支持泛型的 Java 实现，你可以参考一下：
Java
运行代码
复制代码
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
public class CycleArray {
}
// 因为 start 是闭区间，所以先赋值，再右移
arr[start] = null;
start = (start + 1) % size;
count--;
// 如果数组元素数量减少到原大小的四分之一，则减小数组大小为一半
if (count > 0 && count == size / 4) {
resize(size / 2);
}
}
// 在数组尾部添加元素，时间复杂度 O(1)
public void addLast(T val) {
if (isFull()) {
resize(size * 2);
}
// 因为 end 是开区间，所以是先赋值，再右移
arr[end] = val;
end = (end + 1) % size;
count++;
}
// 删除数组尾部元素，时间复杂度 O(1)
public void removeLast() {
if (isEmpty()) {
throw new IllegalStateException("Array is empty");
}
// 因为 end 是开区间，所以先左移，再赋值
end = (end - 1 + size) % size;
arr[end] = null;
count--;
// 缩容
if (count > 0 && count == size / 4) {
resize(size / 2);
}
}
// 获取数组头部元素，时间复杂度 O(1)
public T getFirst() {
if (isEmpty()) {
throw new IllegalStateException("Array is empty");
}
return arr[start];
}
// 获取数组尾部元素，时间复杂度 O(1)
public T getLast() {
if (isEmpty()) {
throw new IllegalStateException("Array is empty");
}
// end 是开区间，指向的是下一个元素的位置，所以要减 1
return arr[(end - 1 + size) % size];
}
public boolean isFull() {
return count == size;
}
public int size() {
return count;
}
public boolean isEmpty() {
return count == 0;
}
}
文末思考
数组增删头部元素的效率真的只能是 O(N) 么？
我们都说，在数组增删头部元素的时间复杂度是 O(N)，因为需要搬移元素。但是，如果我们使用环形数组，其实是可以实现在 O(1) 的时间复杂度内增删头部元素的。
当然，上面实现的这个环形数组只提供了 addFirst, removeFirst, addLast, removeLast 这几个方法，并没有提供 我们之前实现的动态数组 的某些方法，比如删除指定索引的元素，获取指定索引的元素，在指定索引插入元素等等。
但是你可以思考一下，难道环形数组实现不了这些方法么？环形数组实现这些方法，时间复杂度相比普通数组，有退化吗？好像没有吧。环形数组也可以删除指定索引的元素，也要做数据搬移，和普通数组一样，复杂度是 O(N)；环形数组也可以获取指定索引的元素（随机访问），只不过不是直接访问对应索引，而是要通过 start 计算出真实索引，但计算和访问的时间复杂度依然是 O(1)；环形数组也可以在指定索引插入元素，当然也要做数据搬移，和普通数组一样，复杂度是 O(N)。
你可以思考一下是不是这样。如果是这样，为什么编程语言的标准库中提供的动态数组容器底层并没有用环形数组技巧。
