手把手带你实现一个环形数组

自己实现一个CycleArray

• 前面的用环形数组实现的栈和队列就是基于这个环形数组的。

核心原理
环形数组的关键在于，它维护了两个指针 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] 就已经包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦。

/**
 * @author M
 * @version 1.0
 * 环形数组
 */
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 T removeFirst(){
        if(isEmpty()){
            throw new IllegalStateException("Array is empty");
        }
        // 记录被删除元素 用于返回
        T t = arr[start];
        //因为 start 是闭区间，所以先赋值，再右移
        arr[start] = null;
        start = (start - 1) % size;
        count--;
        //如果数组元素数量减少到原来大小的四分之一，则减小数组大小为一一半
        if(count > 0 && count == size / 4){
            resize(size / 2);
        }
        return t;
    }

    //在数组尾部添加元素，时间复杂度O(1)
    public void addLast(T val){
        if(isFull()){
            resize(size * 2);
        }
        //因为end是开区间，所以先赋值，再右移
        arr[end] = val;
        end = (end + 1) % size;
        count++;
    }

    //删除数组尾部元素，时间复杂度O（1）
    public T removeLast(){
        if(isEmpty()){
            throw new IllegalStateException("Array is empty");
        }
        //因为 end 是开区间，所以先左移，再赋值
        end = (end - 1) % size;
        // 记录被删除元素 用于返回
        T t = arr[end];

        arr[end] = null;
        count--;
        //缩容
        if(count > 0 && count == size /4){
            resize(size / 2);
        }
        return t;
    }

    //获取数组头部元素，时间复杂度 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
        //加一个size防止减为负数
        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 这几个方法，并没有提供 我们之前实现的动态数组 的某些方法，比如删除指定索引的元素，获取指定索引的元素，在指定索引插入元素等等。