环形数组

定义环形数组为左闭右开，即[start, end) start指向当前数组首个元素 end指向当前数组末尾元素的下一个位置

如下为实现环形数组代码

class CycleArray:
    def __init__(self, size = 1):
        self.size = size
        self.array = [None] * size
        self.start = 0
        self.end = 0
        self.count = 0

    def resize(self, newSize):
        newArray = [None] * newSize
        for i in range(self.count):
            newArray[i] = self.array[i]
        self.array = newArray
        self.size = newSize
        self.start = 0
        self.end = self.count

    def addFirst(self, val):
        if self.count == self.size:
            self.resize(self.size * 2)
        self.start = (self.start - 1 + self.size) % self.size
        self.array[self.start] = val
        self.count += 1
    
    def addLast(self, val):
        if self.count == self.size:
            self.resize(self.size * 2)
        self.array[self.count] = val
        self.end = (self.end + 1) % self.size
        self.count += 1

    def removeFirst(self):
        if self.count == 0:
            raise Exception("Array Empty")
        self.array[self.start] = None
        self.start = (self.start + 1) % self.size
        self.count -= 1
        if self.count <= self.size // 4:
            self.resize(self.size // 2)

    def removeLast(self):
        if self.count == 0:
            raise Exception("Array Empty")
        self.end = (self.end - 1 + self.size) % self.size
        self.array[self.end] = None
        self.count -= 1
        if self.count <= self.size // 4:
            self.resize(self.size // 2)

    def getFirst(self):
        if self.size == 0:
            raise Exception("Array Empty")
        return self.array[self.start]

    def getLast(self):
        if self.size == 0:
            raise Exception("Array Empty")
        return self.array[(self.end - 1 + self.size) % self.size]

环形数组可以实现动态数组的所有操作，并且不同于动态数组O(N) 的时间复杂度，环形数组能够以 O(1) 的时间复杂度添加头部元素，那么为什么标准库中的动态数组容器底层实现为什么没有用环形数组技巧呢？

如果用环形数组，增删查改的的所有操作都会涉及 % 求模运算，这个操作是比较消耗性能的。尤其像数组的 get 方法，调用频率会非常非常高，如果每次调用都多一步 % 运算，加起来的性能损耗远大于环形数组带来的收益，因为数组很少在头部增删元素。如果你非要在头部增删，应该使用更合适的其他数据结构。 所以一般只会在双端队列这种场景下使用环形数组，标准的动态数组并没有使用这个技巧。不是不能用，而是算总账不划算。–出自labuladong的算法笔记