单向队列

image.png

queue使用链表是因为deQueue需要对头部元素进行出队列操作，链表对头部操作效率比数组高，数组需要移动

class Queue {
    constructor() {
        this.list = new doublyLinkedList();
    }

    // 清空队列
    clear() {
        this.list.clear();
    }

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

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

    // 入队列 
    // 双向链表从最后添加不需要从头开始找，复杂度：O(1)
    enQueue(ele) {
        this.list.push(ele);
    }

    // 出队列 
    // 双向链表从头部出队列复杂度：O(1)，如果使用数组则需要挪位置
    deQueue() {
        return this.list.remove(0);
    }

    // 获取队列头 复杂度：O(1)
    front() {
        return this.list.get(0);
    }
}

双端队列

双端队列是可以在头部和尾部都进行入队和出队操作。

class DeQueue {
    constructor() {
        this.list = new doublyLinkedList();
    }

    // 清空队列
    clear() {
        this.list.clear();
    }

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

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

    // 队列尾部入队列 复杂度：O(1)
    enQueueRear(ele) {
        this.list.push(ele);
    }

    // 队列头部入队列 复杂度：O(1)
    enQueueFront(ele) {
        this.list.add(ele, 0);
    }

    // 队列尾部出队列 复杂度：O(1)
    deQueueRear() {
        return this.list.remove(this.getSize() - 1);
    }

    // 队列头部出队列 复杂度：O(1)
    deQueueFront() {
        return this.list.remove(0);
    }

    // 获取队列头
    front() {
        return this.list.get(0);
    }

    // 获取队列尾
    rear() {
        return this.list.get(this.getSize() - 1)
    }
}