3 月 28 打卡，学习手搓环形数组

实现要注意的关键点

1. 定义为左闭右开 [start, end），因为这样定义，只要让 end 移动以为，就包含一个元素 在 index 0 位置，如果设置成 双开 和双闭合，在处理边界条件很麻烦
2. 关键实现 在于 取模运算 的特性，如果 当前index等于数组大小 就会循环到 index 0的位置，因为余数是0，平常时候 index 都会小于数组大小，所以 取模都会返回index 值，因为商是0 ，通过这个特性来形成环的特性
3. 数组有扩容缩容机制，如果数组满了 扩容2倍，如果数组只用了 数组空间的1/4 缩容一半

▼
python
复制代码
class CycleArray:
    def __init__(self, size=1):
        self.size = size
        self.arr = [None] * self.size
        # start 指向第一个元素
        self.start = 0
        # end 指向最后一个元素，后一位的坐标
        self.end = 0
        self.count = 0

    # 扩容
    def resize(self, new_size):
        # 创建新的数组
        new_arr = [None] * new_size

        # 搬移老的数组数据到新数组
        for i in range(self.count):
            new_arr[i] = self.arr[(self.start + i) % self.size]

        # 从新定义arr, start, end, size
        self.arr = new_arr
        self.start = 0
        self.end = self.count
        self.size = new_size

    # add_first
    def add_first(self, val):
        # 判断 arr 大小够不够 不够扩容为原来的两倍
        if self.is_full():
            self.resize(self.size * 2)

        # 因为左闭，所以 先吧 start 改成 start -1 位置， 插入元素
        self.start = (self.start - 1 + self.size) % self.size
        self.arr[self.start] = val
        self.count += 1

    def add_last(self, val):
        # 判断 arr 大小
        if self.is_full():
            self.resize(self.size * 2)
        # 因为是右开所以先赋值，然后移动 end +1
        self.arr[(self.end)] = val
        self.end = (self.end + 1) % self.size
        self.count += 1

    def remove_first(self):
        # 判断 有无东西可以删除，空的数组不删
        if self.is_empty():
            raise Exception("Array is Empty")
        # 因为左闭，所以先去除，后修改 start，去除头部元素，把 start 位置修改
        self.arr[self.start] = None
        self.start = (self.start + 1 - self.size) % self.size
        # count -1
        self.count -= 1
        # 查看数组使用率 考虑缩减
        if self.count > 0 and self.size//4 == self.count:
            self.resize(self.size//4)

    def remove_last(self):
        #判断是否空数组
        if self.is_empty():
            raise Exception("Array is empty")
        #右开，所以先移动到最后一个坐标，然后删除
        self.end = (self.end -1 + self.size) // 4
        self.arr[self.end] = None
        #count-1
        self.count -=1
        #考虑是否缩容
        if self.count >0 and self.size//4 == self.count:
            self.resize(self.size//4)

    def get_first(self):
        if self.is_empty():
            raise Exception("Array is Empty")
        return self.arr[self.start]

    def get_last(self):
        #判断是否空数组
        if self.is_empty():
            raise Exception("Array is empyt")
        #右闭原则 先移位。后取值
        end = (self.end - 1 - self.size) % self.size
        return self.arr[end]


    #工具函数
    def is_empty(self):
        return self.count == 0

    def is_full(self):
        return self.size == self.count

    def display(self):
        count = self.count
        start = self.start
        for _ in range(count):
            print(self.arr[start], end = ",")
            start = (start + 1 -self.size ) % self.size
            # print(f"start: {start}")

if __name__ == '__main__':
    ca = CycleArray(size=8)
    ca.arr = [3,None,None,None,None,None,1,2]
    ca.count = 3
    ca.start = 6
    ca.end = 1


    ca.add_last("4")
    ca.add_first("0")
    ca.remove_last()
    ca.remove_first()
    ca.display()
    print("")
    print(ca.get_first())
    print(ca.get_last())