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

栏目: JavaScript · 发布时间: 6年前

内容简介:队列和栈非常类似,但是使用了不同的原则,而非后进先出,是先进先出。队列遵循FIFO(先进先出,也称先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的的末尾。队列示意图如下:

队列和栈非常类似,但是使用了不同的原则,而非后进先出,是先进先出。

1.队列数据结构

队列遵循FIFO(先进先出,也称先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的的末尾。队列示意图如下:

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

2.创建队列

// 创建一个类表示队列
function Queue() {
    // 使用数组作为存储队列的数据结构
    let items = [];
    // 下面声明队列一些可用的方法
    // 1.enqueue(elements) 向队尾添加一个或多个项
    this.enqueue = function(element) {
        items.push(element);
    }
    // 2.dequeue() 从队列移除元素 FIFO
    this.dequeue = function() {
        return item.shift();
    }
    // 3.front() 查看队列头元素
    this.front = function() {
        return items[0];
    }
    // 4.isEmpty() size() 检查队列是否为空
    this.isEmpty = function() {
        return items.length === 0;
    }
    this.size = function() {
        return items.length;
    }
    // 5.打印队列元素
    this.print = function() {
        console.log(items.toString())
    } 
}

使用Queue类

let queue = new Queue();
console.log(queue.isEmpty()); // true
// 添加元素
queue.enqueue('june');
queue.enqueue('jack');

queue.print(); // 'june,jack'
console.log(queue.size()); // 2
// 删除元素
queue.dequeue();
queue.dequeue();
queue.print(); // ''

3.优先队列

实现一个有限队列,有两种选择:设置优先级,然后在正确的位置添加元素;或者用入列操作添加元素,然后按照他们的优先级移除他们。

function PriorityQueue() {
    let items = [];
    // 设置添加元素的类
    function QueueElement(element, priority) {
        this.element = element;
        this.priority = priority;
    }
    // 优先级添加
    this.enqueue = function(element, priority) {
        let queueElement = new QueueElement(element, priority);
        
        let added = false;
        // 遍原队列中的元素,如果新添加元素的优先级的值(优先级大,priority值小)小于当前遍历原始的优先级的值(即新添加元素优先级大于当前遍历元素的优先级),则在其前面添加新的元素
        for(let i=0; i<items.length; i++) {
            if(queueElement.priority < items[i].priority) {
                items.splice(i, 0, queueElement);
                added = true;
                break;
            }
        }
        if(!added) {
            items.push(queueElement);
        }
    }
    // 打印
    this.print = function() {
        for(let i=0; i<items.length; i++) {
            console.log(`${items[i].element}-${items[i].priority}`)
        }
    }
    // 其他方法和默认的Queue实现方式相同
}

4.队列的应用——击鼓传花:rose:(循环队列)

// nameList-参与的人 num-每轮传:rose:次数
function hotPotato(nameList, num) {
    let queue = new Queue();
    // 初始化队列
    for(let i=0; i<nameList.length; i++) {
        queue.enqueue(nameList);
    }
    // 
    let eliminated = '';
    // 进行循环队列的入队和出队
    while(queue.size() > 1) {
        for(let i=0; i<num; i++) {
            queue.enqueue(queue.dequeue);
        }
        // 传花停止-淘汰队列第一个
        eliminated = queue.dequeue();
        console.log(eliminated + '在击鼓传花:rose:中被淘汰。')
    }
    // 最后一个出队列的为胜者:rose:
    return queue.dequeue();
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

大数据架构商业之路

大数据架构商业之路

黄申 / 机械工业出版社 / 2016-5-1 / 69.00元

目前大数据技术已经日趋成熟,但是业界发现与大数据相关的产品设计和研发仍然非常困难,技术、产品和商业的结合度还远远不够。这主要是因为大数据涉及范围广、技术含量高、更新换代快,门槛也比其他大多数IT行业更高。人们要么使用昂贵的商业解决方案,要么花费巨大的精力摸索。本书通过一个虚拟的互联网O2O创业故事,来逐步展开介绍创业各个阶段可能遇到的大数据课题、业务需求,以及相对应的技术方案,甚至是实践解析;让读......一起来看看 《大数据架构商业之路》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

URL 编码/解码
URL 编码/解码

URL 编码/解码