关闭

Js队列的实现与应用

时间: 2019-06-29阅读: 591标签: 算法

队列与栈不同,它遵从先进先出(FIFO——First In First Out)原则,新添加的元素排在队列的尾部,元素只能从队列头部移除。

function Queue() {
    let items = [];

    // 向队列添加元素(一个或多个)
    this.enqueue = function (element) {
        if (element instanceof Array) items = items.concat(element);
        else items.push(element);
    };

    // 从队列移除元素
    this.dequeue = function () {
        return items.shift();
    };

    // 返回队列中的第一个元素
    this.front = function () {
        return items[0];
    };

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

    // 返回队列的长度
    this.size = function () {
        return items.length;
    };

    // 清空队列
    this.clear = function () {
        items = [];
    };

    // 打印队列内的所有元素
    this.print = function () {
        console.log(items.toString());
    };
}

与栈的实现方式类似,唯一不同的是从队列移除元素时取的是队列头部的元素(最先添加的),而栈则是取的顶部元素(最后添加的)。下面是一些测试用例及返回结果:

let queue = new Queue();
console.log(queue.isEmpty()); // true

queue.enqueue('John');
queue.enqueue(['Jack', 'Camila']);
queue.print(); // John,Jack,Camila
console.log(queue.size()); // 3
console.log(queue.isEmpty()); // false
console.log(queue.front()); // John

console.log(queue.dequeue()); // John
queue.print(); // Jack,Camila

queue.clear();
queue.print(); // 

注意,我们允许批量向队列中添加元素,为此我们需要判断enqueue方法的参数类型,如果参数是数组,则用concat()函数连接两个数组,如果参数不是数组,则直接用push()函数将元素添加到队列中。

与栈的实现方式一样,这里我们也同样给出用ES6的WeakMap类来实现的队列版本。

let Queue = (function () {
    const items = new WeakMap();

    class Queue {
        constructor() {
            items.set(this, []);
        }

        enqueue (element) {
            let q = items.get(this);
            if (element instanceof Array) items.set(this, q.concat(element));
            else q.push(element);
        };

        dequeue () {
            let q = items.get(this);
            return q.shift();
        };

        front () {
            return items.get(this)[0];
        };

        isEmpty () {
            return items.get(this).length === 0;
        };

        size () {
            return items.get(this).length;
        };

        clear () {
            items.set(this, []);
        };

        print () {
            console.log(items.get(this).toString());
        };
    }

    return Queue;
})();

优先队列

所谓优先队列,顾名思义,就是说插入到队列中的元素可以根据优先级设置先后顺序。优先级越高位置越靠前,优先级越低位置越靠后。假设优先级用数字来表示,如果数字越小表示的优先级越高,形成的队列就称之为最小优先队列,反之则称之为最大优先队列。下面是实现的代码

function PriorityQueue() {
    let items = [];

    // 向队列添加元素(一个或多个)
    // 参数obj的数据格式:{element, priority}
    this.enqueue = function (obj) {
        if (obj instanceof Array) {
            for (let i = 0, ci; ci = obj[i]; i++) {
                this.enqueue(ci);
            }
        }
        else {
            let added = false;
            for (let i = 0, ci; ci = items[i]; i++) {
                // 最小优先级,即将priority值小的元素插入到队列的前面
                if (obj.priority < ci.priority) {
                    items.splice(i, 0, obj);
                    added = true;
                    break;
                }
            }

            // 如果元素没有插入到队列中,则默认加到队列的尾部
            if (!added) items.push(obj);
        }
    };

    // 从队列移除元素
    this.dequeue = function () {
        return items.shift();
    };

    // 返回队列中的第一个元素
    this.front = function () {
        return items[0];
    };

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

    // 返回队列的长度
    this.size = function () {
        return items.length;
    };

    // 清空队列
    this.clear = function () {
        items = [];
    };

    // 打印队列内的所有元素
    this.print = function () {
        items.forEach(function (item) {
            console.log(`${item.element} - ${item.priority}`);
        });
    };
}

可以看到,唯一有区别的只有enqueue方法。我们规定所有添加到优先队列的元素都必须满足{element, priority}这种jsON格式,以保证队列中的每一个元素都有一个priority属性来表示优先级。如果要添加的元素的优先级和队列中已有元素的优先级相同,仍然遵循队列的先进先出原则。如果队列中所有元素的优先级比要添加的元素的优先级都高,则将元素添加到队列的末尾。我们将print()方法也做了一些调整,以方便查看输出结果。

let queue = new PriorityQueue();
console.log(queue.isEmpty()); // true

queue.enqueue({element: 'John', priority: 2});
queue.enqueue([{element: 'Jack', priority: 1}, {element: 'Camila', priority: 1}]);
queue.print(); // Jack,Camila,John
由于John的优先级比其它两个低,所以它被排在了最后面。虽然Jack和Camila的优先级相同,但是Jack是在Camila之前先插入到队列中的,所以Jack排在了Camila之前,这也符合了我们的预期。


循环队列

我们用一个小游戏“击鼓传花”来说明循环队列在实际中的应用。

function hotPotato(nameList, num) {
    let queue = new Queue();

    for (let i = 0, ci; ci = nameList[i]; i++) {
        queue.enqueue(ci);
    }

    let eliminated = '';
    while(queue.size() > 1) {
        for (let i = 0; i < num; i ++) {
            queue.enqueue(queue.dequeue());
        }
        eliminated = queue.dequeue();
        console.log(`${eliminated} has been eliminated.`);
    }

    return queue.dequeue();
}

let names = ['John', 'Jack', 'Camila', 'Ingrid', "Carl"];
let winner = hotPotato(names, 7);
console.log(`The winner is: ${winner}`);
在这个游戏中,我们传入由五个名字组成的数组,用来表示参加游戏的五个人,数字7表示每一轮要传递的次数。在每一个过程中,我们从队列头部取出一个元素加到队列的尾部,当次数用完的时候,将队列头部的元素取出来,作为这一轮中被淘汰的人。让我们来看一下具体的执行过程,一开始队列中的顺序是John, Jack, Camila, Ingrid, Carl,然后传递7次:

  1. Jack, Camila, Ingrid, Carl, John

  2. Camila, Ingrid, Carl, John, Jack

  3. Ingrid, Carl, John, Jack, Camila

  4. Carl, John, Jack, Camila, Ingrid

  5. John, Jack, Camila, Ingrid, Carl

  6. Jack, Camila, Ingrid, Carl, John

  7. Camila, Ingrid, Carl, John, Jack

之后从队列中取出的是Camila。反复执行上述过程,直到队列中的元素只剩一个,这个就是最后的赢家!

下面是完整的执行结果:

Camila has been eliminated.
Jack has been eliminated.
Carl has been eliminated.
Ingrid has been eliminated.
The winner is: John
站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/4403

关闭

js中常用的基础算法

今天给大家分享一下js中常用的基础算法,废话不多说,直接上代码;两个数字调换顺序;对象排序,安装对象中的id排序对象的位置;冒泡排序 ;随机出现不同的数字;字符串大小写互换

PageRank算法的定义与来源、以及PageRank算法原理

PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。

动态规划解题思路

算法能力就是程序员的内力,内力强者对编程利剑的把控能力就更强。动态规划就是,通过递推的方式,由最基本的答案推导出更复杂答案的方法,直到找到最终问题的解。

现在算法是新锐前端框架成功的重要因素

随着前端MVVM的流行,小型框架现在越来越难存活了!react, angular等打着大公司旗号的框架占了半壁江山,而avalon以其良好兼容性在国内份额不断上升。前端也与后端一样,遵循马太效应,强者愈强,弱者愈弱。最后只剩下两种框架

Js算法:计算两数之和

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和

js算法_奇偶分割数组

分割一个整数数组,使得奇数在前偶数在后。 比如:给定 [1, 2, 3, 4],返回 [1, 3, 2, 4]。思路分析:排序好的数组:找到奇数进行操作。乱序的数组:使用sort方法进行排序+提取奇数

js算法-查找斐波纳契数列中第N个数

所谓的斐波纳契数列是指前2个数是 0 和 1 ,第 i 个数是第 i-1 个数和第i-2 个数的和。下面我们来用js获取菲波那契数列的第N个数为多少:递归、闭包+缓存、直接计算出该数列的值得数组,然后再从数组中取值 、直接使用数学表达式

js实现统计一个字符串中出现最多的字母的方法总汇

给出一个字符串,统计出现次数最多的字母。方法一为 String.prototype.charAt:先遍历字符串中所有字母,统计字母以及对应显示的次数,最后是进行比较获取次数最大的字母。方法二 String.prototype.split:逻辑和方法一相同,只不过是通过 split 直接把字符串先拆成数组。

数据结构与算法之绪论

什么是数据结构?简单来说可以解释为:程序设计=数据结构+算法;主要是用来研究数据结构的关系,数据元素之间存在的一种或多种特定关系的集合;

为什么我认为数据结构与算法对前端开发很重要?

一个具有层级结构的数据,实现这个功能非常容易,因为这个结构和组件的结构是一致的,递归遍历就可以了。但是,由于后端通常采用的是关系型数据库,所以返回的数据通常会是这个样子:前端这边想要将数据转换一下其实也不难,因为要合并重复项

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!