JS队列结构详解：FIFO原理、常见操作与优先级队列实现

一、认识队列

受限的线性结构：

此前我们已学习过一种受限的线性结构——栈（Stack）。
这类受限数据结构在解决特定问题时往往能发挥独特作用。
其效果显著且适用场景明确。
接下来，我们将学习另一种受限数据结构：队列（Queue）。

队列（Queue）是一种受限的线性表，遵循先进先出（FIFO, First In First Out）原则。

其受限性体现在：仅允许在表的前端（front）进行删除操作。
而插入操作仅允许在表的后端（rear）进行。

生活中类似队列结构的场景：

生活中存在大量类似队列的场景。
例如电影院、商场或公共厕所的排队现象。
遵循优先排队者优先处理的原则（如买票、结账、使用卫生间）。

二、队列的应用

打印队列：

假设有五份文档需要打印，这些文档将按顺序放入打印队列。
打印机会依次从队列中取出文档，优先处理先入队的文档并进行打印。
此过程持续进行，直到队列中无新文档为止。

线程队列：

在开发中，为实现任务并行处理，通常会开启多个线程。
然而，不能让大量线程同时运行，以免占用过多系统资源。
此时，若需开启线程处理任务，便会使用线程队列。
线程队列会按次序启动线程，并依次处理对应任务。

队列如何实现呢？

接下来我们将研究队列的具体实现方式。

三、队列类的创建

队列的实现与栈类似，主要有两种方案：

基于数组实现。
基于链表实现。

function Queue() {
    //属性
    this.items = []
}

四、队列的常见操作

队列包含哪些常见操作？

enqueue(element)：向队列尾部添加一个（或多个）新项。
dequeue()：移除队列的第一项（即排在最前面的项），并返回被移除的元素。
front()：返回队列中的第一个元素（最先被添加，也将是最先被移除）。此操作不改变队列结构（不移除元素，仅返回信息），与 Stack 类的 peek 方法类似。
isEmpty()：如果队列中不包含任何元素，返回 true；否则返回 false。
size()：返回队列包含的元素个数，功能类似于数组的 length 属性。
toString()：将队列中的内容转换为字符串形式。

现在，我们来实现这些方法。

其实现与栈中方法的实现非常相似，因为我们的队列也是基于数组构建的。

//1.将元素加入到队列中
    Queue.prototype.enqueue = function (element) {
        this.items.push(element)
    }

    //2.从队列中删除前端元素
    Queue.prototype.dequeue = function () {
        return this.items.shift()
    }

    //3.查看前端元素
    Queue.prototype.front = function () {
        return this.items[0]
    }

    //4.查看队列是否为空
    Queue.prototype.isEmpty = function () {
        return this.items.length === 0
    }

    //5.查看队列中元素的个数
    Queue.prototype.size = function () {
        return this.items.length
    }

    //6.toString方法
    Queue.prototype.toString = function () {
        let resultString = ''
        for (let i = 0; i < this.items.length; i++) {
            resultString += this.items[i] + ''
        }
        return resultString
    }

五、击鼓传花

击鼓传花是一个常见的面试算法题，使用队列可以非常便捷地实现最终结果。

原游戏规则：

班级中玩一个游戏。所有学生围成一圈，从某位同学手里开始向旁边的同学传一束花。此时由某人（如班长）击鼓，鼓声停下时，花落在谁手里，谁就出来表演节目。

修改游戏规则：

我们来修改一下这个游戏规则。
几个朋友一起玩一个游戏，围成一圈，开始数数，数到某个指定数字的人自动淘汰。
最后剩下的这个人会获得胜利，请问最后剩下的是原来在哪一个位置上的人？

封装一个基于队列的函数：

参数：所有参与人的姓名列表，基于的淘汰数字。
结果：最终剩下的一人的姓名。

//击鼓传花
function paseGame(nameList, num) {
    //创建一个队列
    let queue = new Queue()

    //将所有人依次加入队列
    for (let i = 0; i < nameList.length; i++) {
        queue.enqueue(nameList[i])
    }

    //开始数数字
    while (queue.size() > 1) {
        //不是num的时候吗，重新加入到队列的末尾
        //num数字之前的人重新放入到队列的末尾
        for (let i = 0; i < num - 1; i++) {
            queue.enqueue(queue.dequeue())
        }
        //num对应的这个人直接从队列中删除 
        queue.dequeue()
    }
    //获取剩下的结果
    let endName = queue.front()
    console.log(endName);
    return nameList.indexOf(endName)
}

paseGame(['lisi', 'zhangsan', 'fgbfd', 'tom', 'jack', 'lisa', 'ez', 'laoshu', 'jikdf', 'dsada', 'poru', 'fjds'], 6)//fgbfd

六、优先级队列

优先级队列的特点：

我们知道，普通队列插入元素时，数据会被放在后端，且需要前面所有元素都处理完成后才会处理前面的数据。
但是优先级队列在插入元素时会考虑该数据的优先级。
并将其与其他数据优先级进行比较。
比较完成后，可以得出这个元素在队列中的正确位置。
其他处理方式，与基本队列的处理方式一样。

优先级队列主要考虑的问题：

每个元素不再只是一个数据，而且包含数据的优先级。
在添加方式中，根据优先级放入正确的位置。

优先级队列的应用：

1. 一个现实的例子就是机场登机的顺序。

头等舱和商务舱乘客的优先级要高于经济舱乘客。
在有些国家，老年人和孕妇（或带小孩的妇女）登机时也享有高于其他乘客的优先级。

2. 另一个现实中的例子是医院的（急诊科）候诊室。

医生会优先处理病情比较严重的患者。
当然，一般情况下是按照排号的顺序。

3. 计算机中，我们也可以通过优先级队列来重新排序队列中任务的顺序。

比如每个线程处理的任务重要性不同，我们可以通过优先级的大小，来决定该线程在队列中被处理的次序。

七、优先级队列的实现

实现优先级队列相对普通队列主要有两方面需要考虑：

1) 封装元素和优先级放在一起（可以封装一个新的构造函数）。

2) 添加元素时，将新插入元素的优先级和队列中已经存在的元素优先级进行比较，以获得自己正确的位置。

//封装优先级队列
function PriorityQueue() {
    //在PriorityQueue重新创建了一个类
    function QueueElemnt(element, priority) {
        this.element = element
        this.priority = priority
    }

    //封装属性
    this.items = []

    //1.实现插入方法
    PriorityQueue.prototype.enqueue = function (element, priority) {
        //创建QueueElement对象
        let queueElemnt = new QueueElemnt(element, priority)

        //判断队列是否为空
        if (this.items.length === 0) {
            this.items.push(queueElemnt)
        } else {
            let added = false
            for (let i = 0; i < this.items.length; i++) {
                if (queueElemnt.priority < this.items[i].priority) {
                    this.items.splice(i, 0, queueElemnt)
                    added = true
                    break
                }
            }
            if (!added) {
                this.items.push(queueElemnt)
            }
        }
    }

    //2.从队列中删除前端元素
    PriorityQueue.prototype.dequeue = function () {
        return this.items.shift()
    }

    //3.查看前端元素
    PriorityQueue.prototype.front = function () {
        return this.items[0]
    }

    //4.查看队列是否为空
    PriorityQueue.prototype.isEmpty = function () {
        return this.items.length === 0
    }

    //5.查看队列中元素的个数
    PriorityQueue.prototype.size = function () {
        return this.items.length
    }

    //6.toString方法
    PriorityQueue.prototype.toString = function () {
        let resultString = ''
        for (let i = 0; i < this.items.length; i++) {
            resultString += this.items[i] + ''
        }
        return resultString
    }
}

// 测试代码
let pq = new PriorityQueue()
pq.enqueue('abc', 111)
pq.enqueue('cba', 151)
pq.enqueue('nba', 66)
pq.enqueue('wba', 856)
console.log(pq);

到此这篇关于 JS 数据结构之队列结构详解的文章就介绍到这了，更多相关 JS 队列结构内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！

JavaScript 队列数据结构详解：从基础实现到优先级队列