[ JavaScript ] 数据结构与算法 —— 队列

前言

JavaScript是当下最流行的编程语言之一，它可以做很多事情：

• 数据可视化（D3.js，Three.js，Chart.js）;
• 移动端应用(React Native,Weex,AppCan,Flutter,Hybrid App,小程序);
• 服务端(Express.js,Koa2)；
• 桌面应用(Electron,nw.js);
• 游戏,VR，AR(LayaAir,Egret,Turbulenz,PlayCanvas);
• 等等。。。

而且目前大部分编程语言的高级应用都会用到数据结构与算法以及设计模式。

本篇主要有三部分

• 什么是队列
• 队列的实现
• 队列的变种

什么是队列

较官方解释

队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。

队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾 。

注：出队入队是自己加的，不知道是不是这么叫

个人理解

我看有很多文档都是说队列就像买什么东西排队，我认为这个比喻用在标准队列上不恰当。

我觉得标准队列像是一段管道，每次都只能放一个球进去，上边只用来放球（入队），由于地球引力，球会从下边的口出去（出队）。

队列：这段可以放球的管道就是队列

元素：管道里的球

队首：在当前管道里的球最早放进去的那个球的位置，同时也是第一个掉出去的球

队尾：在当前管道里的球最后放进去的那个球的位置，同时也是最后一个掉出去的球

队列的实现

• 添加队列成员
• 删除队列成员
• 返回队首的成员
• 队列是否为空
• 清空队列
• 队列长度
• 返回字符串形式的队列成员

class Queue {
    constructor() {
        this.count = 0; // 整个队列下一成员的位置
        this.lowestCount = 0; // 在第一位的成员位置
        this.items = {}; // 用来存放的队列
    }

    enqueue(element) { 
        // 添加队列成员 进入队列
    }

    dequeue() { 
        // 删除队列成员 离开队列
    }

    peek() { 
        // 返回队首的成员
    }

    isEmpty() { 
        // 判断队列是否为空
    }

    clear() { 
        // 将所有的数据初始化
    }

    size() { 
        // 队列长度 
    }

    toString() {
        // 返回字符串形式的队列成员
    }
}

添加队列成员

enqueue(element) {
    this.items[this.count] = element; // 将元素放入队列
    this.count++; // 将计数器加一
}

删除队列成员

dequeue() {
    if (this.isEmpty()) { // 如果是空 
        return undefined; // 返回未定义 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() { // 判断长度是不是 0 
    return this.size() === 0;
}

清空队列

clear() {
    this.count = 0; // 恢复初始值 
    this.lowestCount = 0;  // 恢复初始值
    this.items = {};  // 重新赋值空对象
}

队列长度

size() { // 队列长度 等于 整个队列下一成员的位置 减去 在第一位的成员位置
    return this.count - this.lowestCount;
}

返回字符串形式的队列成员

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;
}

队列的变种

• 优先队列

类似去医院看病，急诊，会优先一般的门诊

• 循环队列

类似抢凳子游戏，队列首位相连

优先队列

在添加成员时会判断优先级，

class QueueElement (element, priority){ // 队列成员类
    this.element = element; // 存放成员
    this.priority = priority;  // 存放优先级 
} 

enqueue(element, priority){ 
    let queueElement = new QueueElement(element, priority);  // 添加成员
    let added = false;  // 是否已添加到队列
    for (let i = 0; i < this.size(); i++){  // 遍历队列
        if (queueElement.priority < items[i].priority){ // 寻找优先级低的成员，并插入到其之前
        // splice start
            for(let j = this.size(); j > i; j--){
                items[j] = items[j-1];
            }
            items[i] = queueElement;
        // splice end
            added = true;  // 标识符置为真，表示已经添加
            break; // 跳出循环
        } 
    } 
    if (!added){  // 如果没有找到优先级比新添加的成员低的，那么将其添加到队尾
        items.push(queueElement);
    } 
};

循环队列

在操作时每删除一个队列成员就将删除的这个队列成员重新添加到队列中

for (let i = 0; i < number; i++){ 
    queue.enqueue(queue.dequeue());
}