环形数组技巧及实现
原创
一句话总结
环形数组技巧利用求模（余数）运算，将普通数组变成逻辑上的环形数组，可以让我们用 的时间在数组头部增删元素。
环形数组原理
数组可能是环形的么？不可能。数组就是一块线性连续的内存空间，怎么可能有环的概念？
但是，我们可以在「逻辑上」把数组变成环形的，比如下面这段代码：
java
// 长度为 5 的数组 int[] arr = new int[]{1, 2, 3, 4, 5}; int i = 0; // 模拟环形数组，这个循环永远不会结束 while (i < arr.length) { System.out.println(arr[i]); i = (i + 1) % arr.length; }cpp
#include <iostream> #include <vector> using namespace std; // 长度为 5 的数组 vector<int> arr = {1, 2, 3, 4, 5}; int i = 0; // 模拟环形数组，这个循环永远不会结束 while (i < arr.size()) { cout << arr[i] << endl; i = (i + 1) % arr.size(); }python
# 长度为 5 的数组 arr = [1, 2, 3, 4, 5] i = 0 # 模拟环形数组，这个循环永远不会结束 while i < len(arr): print(arr[i]) i = (i + 1) % len(arr)go
import "fmt" func main() { // 长度为 5 的数组 arr := []int{1, 2, 3, 4, 5} i := 0 // 模拟环形数组，这个循环永远不会结束 for i < len(arr) { fmt.Println(arr[i]) i = (i + 1) % len(arr) } }javascript
// 长度为 5 的数组 var arr = [1, 2, 3, 4, 5]; var i = 0; // 模拟环形数组，这个循环永远不会结束 while (i < arr.length) { console.log(arr[i]); i = (i + 1) % arr.length; }这段代码的关键在于求模运算 %，也就是求余数。当 i 到达数组末尾元素时，i + 1 和 arr.length 取余数又会变成 0，即会回到数组头部，这样就在逻辑上形成了一个环形数组，永远遍历不完。
这就是环形数组技巧。这个技巧如何帮助我们在 的时间在数组头部增删元素呢？
是这样，假设我们现在有一个长度为 6 的数组，现在其中只装了 3 个元素，如下（未装元素的位置用 _ 标识）：
[1, 2, 3, _, _, _]现在我们要在数组头部删除元素 1，那么我们可以把数组变成这样：
[_, 2, 3, _, _, _]即，我们仅仅把元素 1 的位置标记为空，但并不做数据搬移。
此时，如果我们要在数组头部增加元素 4 和元素 5，我们可以把数组变成这样：
[4, 2, 3, _, _, 5]你可以看到，当头部没有位置添加新元素时，它转了一圈，把新元素加到尾部了。
核心原理
上面只是让大家对环形数组有一个直观地印象，环形数组的关键在于，它维护了两个指针 start 和 end，start 指向第一个有效元素的索引，end 指向最后一个有效元素的下一个位置索引。
这样，当我们在数组头部添加或删除元素时，只需要移动 start 索引，而在数组尾部添加或删除元素时，只需要移动 end 索引。
当 start, end 移动超出数组边界（< 0 或 >= arr.length）时，我们可以通过求模运算 % 让它们转一圈到数组头部或尾部继续工作，这样就实现了环形数组的效果。
动手环节
纸上得来终觉浅，绝知此事要躬行。
我在可视化面板实现了一个简单的环形数组，你可以点击下面代码中的 arr.addLast 或 arr.addFirst，注意观察 start, end 指针以及 arr 数组中元素的变化：
算法可视化面板
代码实现
关键点、注意开闭区间
在我的代码中，环形数组的区间被定义为左闭右开的，即 [start, end) 区间包含数组元素。所以其他的方法都是以左闭右开区间为基础实现的。
那么肯定就会有读者问，为啥要左闭右开，我就是想两端都开，或者两端都闭，不行么？
在 滑动窗口算法核心框架 中定义滑动窗口的边界时也会有类似的问题，这里我也解释一下。
理论上，你可以随意设计区间的开闭，但一般设计为左闭右开区间是最方便处理的。
因为这样初始化 start = end = 0 时，区间 [0, 0) 中没有元素，但只要让 end 向右移动（扩大）一位，区间 [0, 1) 就包含一个元素 0 了。
如果你设置为两端都开的区间，那么让 end 向右移动一位后开区间 (0, 1) 仍然没有元素；如果你设置为两端都闭的区间，那么初始区间 [0, 0] 就已经包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦，如果你非要使用的话，需要在代码中做一些特殊处理。
最后，请看代码实现：
java
public class CycleArray<T> { private T[] arr; private int start; private int end; private int count; private int size; public CycleArray() { this(1); } @SuppressWarnings("unchecked") public CycleArray(int size) { this.size = size; // 因为 Java 不支持直接创建泛型数组，所以这里使用了类型转换 this.arr = (T[]) new Object[size]; // start 指向第一个有效元素的索引，闭区间 this.start = 0; // 切记 end 是一个开区间， // 即 end 指向最后一个有效元素的下一个位置索引 this.end = 0; this.count = 0; } // 自动扩缩容辅助函数 @SuppressWarnings("unchecked") private void resize(int newSize) { // 创建新的数组 T[] newArr = (T[]) new Object[newSize]; // 将旧数组的元素复制到新数组中 for (int i = 0; i < count; i++) { newArr[i] = arr[(start + i) % size]; } arr = newArr; // 重置 start 和 end 指针 start = 0; end = count; size = newSize; } // 在数组头部添加元素，时间复杂度 O(1) public void addFirst(T val) { // 当数组满时，扩容为原来的两倍 if (isFull()) { resize(size * 2); } // 因为 start 是闭区间，所以先左移，再赋值 start = (start - 1 + size) % size; arr[start] = val; count++; } // 删除数组头部元素，时间复杂度 O(1) public void removeFirst() { if (isEmpty()) { throw new IllegalStateException("Array is empty"); } // 因为 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; } }cpp
#include <iostream> #include <stdexcept> #include <vector> #include <ostream> template<typename T> class CycleArray { std::vector<T> arr; int start; int end; int count; // 自动扩缩容辅助函数 void resize(int newSize) { // 创建新的数组并复制元素 std::vector<T> newArr(newSize); for (int i = 0; i < count; ++i) { newArr[i] = arr[(start + i) % arr.size()]; } arr = std::move(newArr); // 重置 start 和 end 指针 start = 0; end = count; } public: CycleArray() : CycleArray(1) {} explicit CycleArray(int size) : arr(size), start(0), end(0), count(0) {} // 在数组头部添加元素，时间复杂度 O(1) void addFirst(const T &val) { // 当数组满时，扩容为原来的两倍 if (isFull()) { resize(arr.size() * 2); } // 因为 start 是闭区间，所以先左移，再赋值 start = (start - 1 + arr.size()) % arr.size(); arr[start] = val; count++; } // 删除数组头部元素，时间复杂度 O(1) void removeFirst() { if (isEmpty()) { throw std::runtime_error("Array is empty"); } // 因为 start 是闭区间，所以先赋值，再右移 arr[start] = T(); start = (start + 1) % arr.size(); count--; // 如果数组元素数量减少到原大小的四分之一，则减小数组大小为一半 if (count > 0 && count == arr.size() / 4) { resize(arr.size() / 2); } } // 在数组尾部添加元素，时间复杂度 O(1) void addLast(const T &val) { if (isFull()) { resize(arr.size() * 2); } // 因为 end 是开区间，所以是先赋值，再右移 arr[end] = val; end = (end + 1) % arr.size(); count++; } // 删除数组尾部元素，时间复杂度 O(1) void removeLast() { if (isEmpty()) { throw std::runtime_error("Array is empty"); } // 因为 end 是开区间，所以先左移，再赋值 end = (end - 1 + arr.size()) % arr.size(); arr[end] = T(); count--; // 缩容 if (count > 0 && count == arr.size() / 4) { resize(arr.size() / 2); } } // 获取数组头部元素，时间复杂度 O(1) T getFirst() const { if (isEmpty()) { throw std::runtime_error("Array is empty"); } return arr[start]; } // 获取数组尾部元素，时间复杂度 O(1) T getLast() const { if (isEmpty()) { throw std::runtime_error("Array is empty"); } // end 是开区间，指向的是下一个元素的位置，所以要减 1 return arr[(end - 1 + arr.size()) % arr.size()]; } bool isFull() const { return count == arr.size(); } int size() const { return count; } bool isEmpty() const { return count == 0; } };python
class CycleArray: def __init__(self, size=1): self.size = size # 因为 Python 支持直接创建泛型数组，所以不需要类型转换 self.arr = [None] * size # start 指向第一个有效元素的索引，闭区间 self.start = 0 # 切记 end 是一个开区间， # 即 end 指向最后一个有效元素的下一个位置索引 self.end = 0 self.count = 0 # 自动扩缩容辅助函数 def resize(self, newSize): # 创建新的数组 new_arr = [None] * newSize # 将旧数组的元素复制到新数组中 for i in range(self.count): new_arr[i] = self.arr[(self.start + i) % self.size] self.arr = new_arr # 重置 start 和 end 指针 self.start = 0 self.end = self.count self.size = newSize # 在数组头部添加元素，时间复杂度 O(1) def add_first(self, val): # 当数组满时，扩容为原来的两倍 if self.is_full(): self.resize(self.size * 2) # 因为 start 是闭区间，所以先左移，再赋值 self.start = (self.start - 1 + self.size) % self.size self.arr[self.start] = val self.count += 1 # 删除数组头部元素，时间复杂度 O(1) def remove_first(self): if self.is_empty(): raise Exception("Array is empty") # 因为 start 是闭区间，所以先赋值，再右移 self.arr[self.start] = None self.start = (self.start + 1) % self.size self.count -= 1 # 如果数组元素数量减少到原大小的四分之一，则减小数组大小为一半 if self.count > 0 and self.count == self.size // 4: self.resize(self.size // 2) # 在数组尾部添加元素，时间复杂度 O(1) def add_last(self, val): if self.is_full(): self.resize(self.size * 2) # 因为 end 是开区间，所以是先赋值，再右移 self.arr[self.end] = val self.end = (self.end + 1) % self.size self.count += 1 # 删除数组尾部元素，时间复杂度 O(1) def remove_last(self): if self.is_empty(): raise Exception("Array is empty") # 因为 end 是开区间，所以先左移，再赋值 self.end = (self.end - 1 + self.size) % self.size self.arr[self.end] = None self.count -= 1 # 缩容 if self.count > 0 and self.count == self.size // 4: self.resize(self.size // 2) # 获取数组头部元素，时间复杂度 O(1) def get_first(self): if self.is_empty(): raise Exception("Array is empty") return self.arr[self.start] # 获取数组尾部元素，时间复杂度 O(1) def get_last(self): if self.is_empty(): raise Exception("Array is empty") # end 是开区间，指向的是下一个元素的位置，所以要减 1 return self.arr[(self.end - 1 + self.size) % self.size] def is_full(self): return self.count == self.size def size(self): return self.count def is_empty(self): return self.count == 0go
import "errors" // CycleArray is a cyclic array data structure type CycleArray[T any] struct { arr []T start int end int count int size int } func NewCycleArray[T any]() *CycleArray[T] { return NewCycleArrayWithSize[T](1) } func NewCycleArrayWithSize[T any](size int) *CycleArray[T] { return &CycleArray[T]{ arr: make([]T, size), start: 0, end: 0, count: 0, size: size, } } // 自动扩缩容辅助函数 func (ca *CycleArray[T]) resize(newSize int) { // 创建新的数组 newArr := make([]T, newSize) // 将旧数组的元素复制到新数组中 for i := 0; i < ca.count; i++ { newArr[i] = ca.arr[(ca.start+i)%ca.size] } ca.arr = newArr // 重置 start 和 end 指针 ca.start = 0 ca.end = ca.count ca.size = newSize } // 在数组头部添加元素，时间复杂度 O(1) func (ca *CycleArray[T]) AddFirst(val T) { // 当数组满时，扩容为原来的两倍 if ca.isFull() { ca.resize(ca.size * 2) } // 因为 start 是闭区间，所以先左移，再赋值 ca.start = (ca.start - 1 + ca.size) % ca.size ca.arr[ca.start] = val ca.count++ } // 删除数组头部元素，时间复杂度 O(1) func (ca *CycleArray[T]) RemoveFirst() error { if ca.isEmpty() { return errors.New("array is empty") } // 因为 start 是闭区间，所以先赋值，再右移 ca.arr[ca.start] = *new(T) ca.start = (ca.start + 1) % ca.size ca.count-- // 如果数组元素数量减少到原大小的四分之一，则减小数组大小为一半 if ca.count > 0 && ca.count == ca.size/4 { ca.resize(ca.size / 2) } return nil } // 在数组尾部添加元素，时间复杂度 O(1) func (ca *CycleArray[T]) AddLast(val T) { if ca.isFull() { ca.resize(ca.size * 2) } // 因为 end 是开区间，所以是先赋值，再右移 ca.arr[ca.end] = val ca.end = (ca.end + 1) % ca.size ca.count++ } // 删除数组尾部元素，时间复杂度 O(1) func (ca *CycleArray[T]) RemoveLast() error { if ca.isEmpty() { return errors.New("array is empty") } // 因为 end 是开区间，所以先左移，再赋值 ca.end = (ca.end - 1 + ca.size) % ca.size ca.arr[ca.end] = *new(T) ca.count-- // 缩容 if ca.count > 0 && ca.count == ca.size/4 { ca.resize(ca.size / 2) } return nil } // 获取数组头部元素，时间复杂度 O(1) func (ca *CycleArray[T]) GetFirst() (T, error) { if ca.isEmpty() { return *new(T), errors.New("array is empty") } return ca.arr[ca.start], nil } // 获取数组尾部元素，时间复杂度 O(1) func (ca *CycleArray[T]) GetLast() (T, error) { if ca.isEmpty() { return *new(T), errors.New("array is empty") } // end 是开区间，指向的是下一个元素的位置，所以要减 1 return ca.arr[(ca.end-1+ca.size)%ca.size], nil } func (ca *CycleArray[T]) isFull() bool { return ca.count == ca.size } func (ca *CycleArray[T]) Size() int { return ca.count } func (ca *CycleArray[T]) isEmpty() bool { return ca.count == 0 }javascript
class CycleArray { constructor(size = 1) { this.size = size; this.arr = new Array(size); // start 指向第一个有效元素的索引，闭区间 this.start = 0; // 切记 end 是一个开区间， // 即 end 指向最后一个有效元素的下一个位置索引 this.end = 0; this.count = 0; } resize(newSize) { // 创建新的数组 var newArr = new Array(newSize); // 将旧数组的元素复制到新数组中 for (var i = 0; i < this.count; i++) { newArr[i] = this.arr[(this.start + i) % this.size]; } this.arr = newArr; // 重置 start 和 end 指针 this.start = 0; this.end = this.count; this.size = newSize; } // 在数组头部添加元素，时间复杂度 O(1) addFirst(val) { // 当数组满时，扩容为原来的两倍 if (this.isFull()) { this.resize(this.size * 2); } // 因为 start 是闭区间，所以先左移，再赋值 this.start = (this.start - 1 + this.size) % this.size; this.arr[this.start] = val; this.count++; } // 删除数组头部元素，时间复杂度 O(1) removeFirst() { if (this.isEmpty()) { throw new Error("Array is empty"); } // 因为 start 是闭区间，所以先赋值，再右移 this.arr[this.start] = null; this.start = (this.start + 1) % this.size; this.count--; // 如果数组元素数量减少到原大小的四分之一，则减小数组大小为一半 if (this.count > 0 && this.count == this.size / 4) { this.resize(this.size / 2); } } // 在数组尾部添加元素，时间复杂度 O(1) addLast(val) { if (this.isFull()) { this.resize(this.size * 2); } // 因为 end 是开区间，所以是先赋值，再右移 this.arr[this.end] = val; this.end = (this.end + 1) % this.size; this.count++; } // 删除数组尾部元素，时间复杂度 O(1) removeLast() { if (this.isEmpty()) { throw new Error("Array is empty"); } // 因为 end 是开区间，所以先左移，再赋值 this.end = (this.end - 1 + this.size) % this.size; this.arr[this.end] = null; this.count--; // 缩容 if (this.count > 0 && this.count == this.size / 4) { this.resize(this.size / 2); } } // 获取数组头部元素，时间复杂度 O(1) getFirst() { if (this.isEmpty()) { throw new Error("Array is empty"); } return this.arr[this.start]; } // 获取数组尾部元素，时间复杂度 O(1) getLast() { if (this.isEmpty()) { throw new Error("Array is empty"); } // end 是开区间，指向的是下一个元素的位置，所以要减 1 return this.arr[(this.end - 1 + this.size) % this.size]; } isFull() { return this.count === this.size; } size() { return this.count; } isEmpty() { return this.count === 0; } }思考题
数组增删头部元素的效率真的只能是 么？
我们都说，在数组增删头部元素的时间复杂度是 ，因为需要搬移元素。但是，如果我们使用环形数组，其实是可以实现在 的时间复杂度内增删头部元素的。
当然，上面实现的这个环形数组只提供了 addFirst, removeFirst, addLast, removeLast 这几个方法，并没有提供 我们之前实现的动态数组 的某些方法，比如删除指定索引的元素，获取指定索引的元素，在指定索引插入元素等等。
但是你可以思考一下，难道环形数组实现不了这些方法么？环形数组实现这些方法，时间复杂度相比普通数组，有退化吗？
好像没有吧。
环形数组也可以删除指定索引的元素，也要做数据搬移，和普通数组一样，复杂度是 ；
环形数组也可以获取指定索引的元素（随机访问），只不过不是直接访问对应索引，而是要通过 start 计算出真实索引，但计算和访问的时间复杂度依然是 ；
环形数组也可以在指定索引插入元素，当然也要做数据搬移，和普通数组一样，复杂度是 。
你可以思考一下是不是这样。如果是这样，为什么编程语言的标准库中提供的动态数组容器底层并没有用环形数组技巧。