环形数组
环形数组与动/静态数组不同之处在于:
- 动/静态数组拥有的内存空间逻辑上是有边界的,比如说头部元素的前一个位置不属于该数组。因此动/静态数组插入会涉及数组迁移的操作。
- 环形数组维护的内存空间逻辑上不再有头尾之分(实际上和动/静态数组一样有边界,通过维护头尾指针打破边界),因此头尾插入不会涉及数组迁移,只需要利用头尾指针插入,在这一点与环型链表很像
- 但在数组内部插入,环形数组仍然需要数据迁移
#include <iostream>
#include <stdexcept>
#include <ostream>
template<typename T>
class CycleArray {
std::unique_ptr<T[]> arr;
int start;
int end;
int size;
int capacity;
// 自动扩缩容辅助函数
void resize(int newCapacity) {
// 创建新的数组
std::unique_ptr<T[]> newArr = std::make_unique<T[]>(newSize);
// 将旧数组的元素复制到新数组中
for (int i = 0; i < size; ++i) {
newArr[i] = arr[(start + i) % capacity];
}
arr = std::move(newArr);
// 重置 start 和 end 指针
start = 0;
end = size;
capacity = newCapacity;
}
public:
CycleArray() : CycleArray(1) {
}
explicit CycleArray(int capacity) : start(0), end(0), size(0), capacity(capacity) {
arr = std::make_unique<T[]>(capacity);
}
// 在数组头部添加元素,时间复杂度 O(1)
void addFirst(const T &val) {
// 当数组满时,扩容为原来的两倍
if (isFull()) {
recapacity(capacity * 2);
}
// 因为 start 是闭区间,所以先左移,再赋值
start = (start - 1 + capacity) % capacity;
arr[start] = val;
size++;
}
// 删除数组头部元素,时间复杂度 O(1)
void removeFirst() {
if (isEmpty()) {
throw std::runtime_error("Array is empty");
}
// 因为 start 是闭区间,所以先赋值,再右移
arr[start] = T();
start = (start + 1) % capacity;
size--;
// 如果数组元素数量减少到原大小的四分之一,则减小数组大小为一半
if (size > 0 && size == capacity / 4) {
resize(capacity / 2);
}
}
// 在数组尾部添加元素,时间复杂度 O(1)
void addLast(const T &val) {
if (isFull()) {
resize(capacity * 2);
}
// 因为 end 是开区间,所以是先赋值,再右移
arr[end] = val;
end = (end + 1) % capacity;
size++;
}
// 删除数组尾部元素,时间复杂度 O(1)
void removeLast() {
if (isEmpty()) {
throw std::runtime_error("Array is empty");
}
// 因为 end 是开区间,所以先左移,再赋值
end = (end - 1 + capacity) % capacity;
arr[end] = T();
size--;
// 缩容
if (size > 0 && size == capacity / 4) {
resize(capacity / 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 + capacity) % capacity];
}
bool isFull() const {
return size == capacity;
}
int getSize() const {
return size;
}
bool isEmpty() const {
return size == 0;
}
};