单向循环队列

可以使用数组来实现队列，并且各项接口也可以优化到 O(1) 的时间复杂度--这就是循环队列

// 环形队列 使用动态数组来实现队列 实现复杂度O(1)
const DEFAULT_CAPATICY = 10;
class CircleQueue {
    constructor(capaticy = DEFAULT_CAPATICY) {
        this.elements = new Array(capaticy);
        this.size = 0;
        // 头部指针
        this.front = 0;
    }

    // 清空队列
    clear() {
        this.elements = new Array(DEFAULT_CAPATICY);
        this.size = 0;
        this.front = 0;
    }

    // 判断队列是否为空
    isEmpty() {
        return this.size === 0;
    }

    // 获取队列size
    getSize() {
        return this.size;
    }

    // 入队列 入队列时不需要置front位置 复杂度O(1) 因为是循环的，所以不需要挪位置，使用front头部指针来定位
    enQueue(ele) {
        this.expandCapacity(this.size + 1);

        // 入队列是从最后入队列，不需要重置front的位置，就是没有元素的时候，只要在删除的时候重置front即可。
        this.elements[this.getRealIndex(this.size)] = ele;
        this.size++
    }

    // 出队列 复杂度 O(1)
    deQueue() {
        // 缓存头部元素
        let old = this.elements[this.front];
        // 删除头部元素
        this.elements[this.front] = null;
        // 重置头部指针到下一位
        this.front = this.getRealIndex(1);
        this.size--;
        return old;
    }

    // 获取队列头 复杂度 O(1)
    getFront() {
        return this.elements[this.front];
    }

    // 获取真正的index下标，因为循环下标会有差异
    getRealIndex(index) {
        let real = this.front + index;
        let capaticy = this.elements.length;
        return real % capaticy;
    }

    // 扩容 -- 如果已使用的容量已经大于等于容量需要扩容
    expandCapacity(capaticy) {
        let oldCapaticy = this.elements.length;
        if (capaticy <= oldCapaticy) return false;

        let newCapaticy = oldCapaticy + (oldCapaticy >> 1);
        let elements = new Array(newCapaticy);

        for (let i = 0; i < this.size; i++) {
            elements[i] = this.elements[this.getRealIndex(i)];
        }
        this.elements = elements;
        this.front = 0;
        console.log(`${oldCapaticy} -->扩容为--> ${newCapaticy}`);
    }

    toString() {
        return this.elements;
    }
}

循环双端队列

可以进行两端添加、删除操作的循环队列

// 双端环形队列
const DEFAULT_CAPATICY = 10;
class CircleDeQueue {
    constructor(capaticy = DEFAULT_CAPATICY) {
        this.elements = new Array(capaticy);
        this.size = 0;
        this.front = 0;
    }

    // 清空队列
    clear() {
        this.elements = new Array(DEFAULT_CAPATICY);
        this.size = 0;
        this.front = 0;
    }

    // 判断队列是否为空
    isEmpty() {
        return this.size === 0;
    }

    // 获取队列size
    getSize() {
        return this.size;
    }

    // 从头部插入元素 复杂度O(1)
    enQueueFront(ele) {
        this.expandCapacity(this.size + 1);

        // 获取头部前一个元素的下标 重置给头部指针front，再赋值
        this.elements[this.front = this.getRealIndex(-1)] = ele;
        this.size++
    }

    // 从尾部插入元素 复杂度 O(1)
    enQueueRear(ele) {
        this.expandCapacity(this.size + 1);

        // 获取尾部下一个插入位置的下标，再赋值，此时由于头部没有变化，所以不需要改变头部指针front，就是没有元素，front仍然是0或者之前的front位置，还是对的
        this.elements[this.getRealIndex(this.size)] = ele;
        this.size++
    }

    // 从头部出队列 复杂度 O(1)
    deQueueFront() {
        // 获取头部元素
        let old = this.elements[this.front];
        // 删除头部元素
        this.elements[this.front] = null;
        // 重置头部指针为下一个元素
        this.front = this.getRealIndex(1);
        this.size--;
        return old;
    }

    // 从尾部出队列， 复杂度 O(1)
    deQueueRear() {
        // 获取最后一个元素
        let realIndex = this.getRealIndex(this.size - 1);
        let old = this.elements[realIndex];
        // 删除最后一个元素，此时不需要更新头部指针，因为头部没有改变，就是如果剩一个元素时，删除后front仍然是之前的front位置，下次插入仍然插入在这个头部位置。
        this.elements[realIndex] = null;
        this.size--;
        return old;
    }

    // 获取队列头 复杂度 O(1)
    getFront() {
        return this.elements[this.front];
    }
    // 获取队列尾 复杂度 O(1)
    getRear() {
        return this.elements[this.getRealIndex(this.size - 1)]
    }

    // 获取真实的下标，支持负数
    getRealIndex(index) {
        let real = this.front + index;
        let capaticy = this.elements.length;
        return (real < 0 ? capaticy + real : real) % capaticy;
    }

    // 扩容 -- 如果已使用的容量已经大于等于容量需要扩容
    expandCapacity(capaticy) {
        let oldCapaticy = this.elements.length;
        if (capaticy <= oldCapaticy) return false;

        let newCapaticy = oldCapaticy + (oldCapaticy >> 1);
        let elements = new Array(newCapaticy);

        for (let i = 0; i < this.size; i++) {
            elements[i] = this.elements[this.getRealIndex(i)];
        }
        this.elements = elements;
        this.front = 0;
        console.log(`${oldCapaticy} -->扩容为--> ${newCapaticy}`);
    }

    toString() {
        return this.elements;
    }
}