循环数组

循环数组作为数组的一种基本变形，是可以在某些方面有效提升数组的效率。

数组本身是不能成为环形的，但是可以通过代码让他成为逻辑上环形的。主要就是通过维护两个指针，一个start和一个end，用于记录逻辑上数组的开头和结尾。再加上求模的方式，就可以实现一个循环数组。

#include <iostream>
#include <vector>
using namespace std;


vector<int> arr = {1,2,3,4,5};
int i = 0;
//无限循环的数组
while(i<arr.size())
{
    cout<< arr[i] <<endl;
    i = (i+1)%arr.size();
}

当i到达数组末尾元素时，i+arr.length 取模后又为0，又倒回数组头部，所以这个数组是无限循环的。

实现过程

#include <iostream>
#include <stdexcept>
#include <vector>
#include <ostream>

using namespace std;

template <typename T> // 泛型类模板
class CycleArray {
   vector<T> arr;
   int start;
   int end;
   int count;

   void resize(int newSize){
    vector<T> newArr(newSize);
    for(int i =0;i<count;i++)
    {
        newArr[i] = arr[(start+i)%arr.size()];
    }
    arr = std::move(newArr);
    start = 0;
    end = count;
   }
   public:
    CycleArray() : CycleArray(1){}

    explicit CycleArray(int size) : arr(size),start(0),end(0),count(0){}

    void addFirst(const T &val){
        if(isFull())
        {
            resize(arr.size()*2);
        }
        start = (start - 1 + arr.size()) % arr.size();
        arr[start] = val;
        count++;
    }

    void addLast(const T &val){
        if(isFull())
        {
            resize(arr.size()*2);
        }
        arr[end] = val;
        end = (end + 1) % arr.size();
        count++;
    }

    void removeFirst(){
        if(isEmpty())
        {
            throw runtime_error("Array is empty");
        }
        arr[start] = T();
        start = (start + 1) % arr.size();
        count--;
        if(count<arr.size()/4 && count >0)
        {
            resize(arr.size()/2);
        }
    }

    void removeLast(){
        if(isEmpty()){
            throw runtime_error("Array is empty");
        }
        end = (end - 1 + arr.size()) % arr.size();
        arr[end] = T();
        count--;
        if(count<arr.size()/4 && count >0)
        {
            resize(arr.size()/2);
        }
    }

    T getFirst() const{
        if(isEmpty())
        {
            throw runtime_error("Array is empty");
        }

        return arr[start];

    }

    T getLast() const{
        if(isEmpty())
        {
            throw runtime_error("Array is empty");
        }
        return arr[(end - 1 + arr.size()) % arr.size()];
    }

    bool isFull() const{
        return count == arr.size();
    }

    bool isEmpty() const{
        return count == 0;
    }

    int size() const{
        return count;
    }
    void printDetails() const {
    std::cout << "--- 内部调试信息 ---" << std::endl;
    std::cout << "总容量 (capacity): " << arr.size() << std::endl;
    std::cout << "元素数量 (count): " << count << std::endl;
    std::cout << "start 指针: " << start << ", end 指针: " << end << std::endl;

    std::cout << "物理数组内容: [ ";
    for (int i = 0; i < arr.size(); i++) {
        // 标记哪些位置是当前队列中的元素
        bool is_in_queue = false;
        if (count > 0) {
            // 判断 i 是否在 [start, end) 范围内（考虑循环情况）
            if (start < end) {
                if (i >= start && i < end) is_in_queue = true;
            } else { // 跨越边界的情况
                if (i >= start || i < end) is_in_queue = true;
            }
        }

        if (is_in_queue) std::cout << arr[i] << " ";
        else std::cout << "(" << arr[i] << ") "; // 括号表示无效/空闲区域
    }
    std::cout << "]" << std::endl;
}
};