队列

队列

队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

Queue类的模拟实现

class Queue {
    // 构造函数
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
    // 向队列添加元素
    enqueue(element) {
        this.items[this.count] = element;
        this.count++;
    }
    // 从队列移除元素 
    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }
        const result = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return result;
    }
    // 查看队列头元素
    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.lowestCount];
    }
    // 检查队列是否为空
    isEmpty() {
        return this.count - this.lowestCount === 0;
    }
    // 获取队列的长度
    size() {
        return this.count - this.lowestCount;
    }
    // 清空队列
    clear() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
    // 创建toString方法
    toString() {
        if (this.isEmpty()) {
            return "";
        }
        let objString = `${this.items[this.lowestCount]}`;
        for (let i = this.lowestCount + 1; i < this.count; i++) {
            objString = `${objString}, ${this.items[i]}`;
        }
        return objString;
    }
}

双端队列

双端队列是一种允许我们同时从前端和后端添加和删除元素的特殊队列。

Deque类的模拟实现

class Deque {
    // 构造函数
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {};
    }
    // 向双端队列的前端添加元素
    addFront(element) {
        if (this.isEmpty()) {
            this.addBack(element);
        } else if (this.lowestCount > 0) {
            this.lowestCount--;
            this.items[this.lowestCount] = element;
        } else {
            for (let i = this.count; i > 0; i++) {
                this.items[i] = this.items[i - 1];
            }
            this.count++;
            this.lowestCount = 0;
            this.items[0] = element;
        }
    }
    // 向双端队列的后端添加元素
    addBack(element) {
        this.items[this.count] = element;
        this.count++;
    }
    // 从双端队列的前端移除元素
    removeFront() {
        if (this.isEmpty()) {
            return undefined;
        }
        const result = this.items[this.lowestCount];
        delete this.items[this.lowestCount];
        this.lowestCount++;
        return result;
    }
    // 从双端队列的后端移除元素
    removeBack() {
        if (this.isEmpty()) {
            return undefined;
        }
        this.count--;
        const result = this.items[this.count];
        delete this.items[this.count];
        return result;
    }
    // 查看双端队列前端头元素
    peekFront() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.lowestCount];
    }
    // 查看双端队列后端头元素
    peekBack() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.count - 1];
    }
    // 获取双端队列的大小
    size() {
        return this.count - this.lowestCount;
    }
    // 检查双端队列是否为空
    isEmpty() {
        return this.size() === 0;
    }
    // 清空双端队列
    clear() {
        this.items = {};
        this.count = 0;
        this.lowestCount = 0;
    }
    // 创建toString方法
    toString() {
        if (this.isEmpty()) {
            return "";
        }
        let objString = `${this.items[this.lowestCount]}`;
        for (let i = this.lowestCount + 1; i < this.count; i++) {
            objString = `${objString},${this.items[i]}`;
        }
        return objString;
    }
}

这里就不再演示Queue类和Deque类中方法的使用了，有兴趣的可以自己做个demo测试一下，如果有任何的问题，欢迎评论区留言。

Donate