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

Yi_Zhi_Yu 发布于2019-08-23 15:05 / 2302人阅读

摘要：而且目前大部分编程语言的高级应用都会用到数据结构与算法以及设计模式。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

前言

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

GPU云服务器云服务器算法与数据结构数据结构与算法数据结构与算法教程数据结构与算法答案

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101492.html

学习JavaScript数据结构与算法（一）：栈与队列

摘要：之数组操作接下来就是数据结构的第一部分，栈。以字符串显示栈中所有内容方法的实现说明需要往栈中添加新元素，元素位置在队列的末尾。的前端乐园原文链接寒假前端学习学习数据结构与算法，栈与队列本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据结构与算法（三）：集合第...

Flink_China 2019-08-19 17:23 评论0 收藏0
JavaScript的数据结构与算法（二） —— 队列

摘要：简介队列遵循的是先进先出的原则的一组有序的项。队列从尾部添加新元素，并从顶部移除元素，最新添加的元素必须排列在队列的末尾。它的想法来自于生活中排队的策略。队列不做任何变动。简介队列遵循的是FIFO（先进先出）的原则的一组有序的项。队列从尾部添加新元素，并从顶部移除元素，最新添加的元素必须排列在队列的末尾。它的想法来自于生活中排队的策略。顾客在付款结账的时候，按照到来的先后顺序排...

xingqiba 2019-08-21 17:12 评论0 收藏0
JavaScript数据结构与算法——队列

摘要：队列数据结构队列遵循先进先出，也称先来先服务原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的的末尾。队列和栈非常类似，但是使用了不同的原则，而非后进先出，是先进先出。 1.队列数据结构队列遵循FIFO（先进先出，也称先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的的末尾。队列示意图如下： s...

silenceboy 2019-08-23 15:12 评论0 收藏0
《JavaScript数据结构与算法》笔记——第4章队列

摘要：队列遵循原则的一组有序的项向队列尾部添加一个项移除队列的第一项返回队列中第一项，对队列本身不做修改判断队列是否为空返回队列包含的元素个数优先队列根据优先级添加项最小优先队列移除队列的第一项返回队列中第一项，对队列本身不做修改判断队列是否队列遵循FIFO（First In First Out）原则的一组有序的项 let Queue = (function () { let it...

callmewhy 2019-08-26 13:28 评论0 收藏0
学习数据结构与算法之栈与队列

摘要：于是翻出了机房里的这本学习数据结构与算法开始学习程序员的基础知识。这本书用了我最熟悉的来实现各种数据结构和算法，而且书很薄，可以说是一本不错的入门教程。队列在头部删除元素，尾部添加元素。本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算...

pingan8787 2019-08-20 18:37 评论0 收藏0