NodeJS 事件循环

一.认识队列

队列(Queue)

• 它是一种运算受限的线性表,先进先出(FIFO First In First Out)
• 队列是一种受限的线性结构
• 受限之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作

生活中类似于栈的结构的事情有很多， 比如在电影院, 商场, 甚至是厕所排队.

这张图完美的演绎了队列结构

程序中怎么实现的呢?

1. 在进行多线程开发时, 我们不可能无限制的开启新的线程.
2. 这个时候, 如果有需要开启线程处理任务的情况, 我们就会使用线程队列.
3. 线程队列会依照次序来启动线程, 并且处理对应的任务.

   二.队列结构实现(js版)

   我们先来创建一个队列的类, 用于封装队列相关的操作

// 封装队列 先进后去
function Queue() {
    //属性
    this.items = []
    // 方法
    // 1 将元素加入队列
    Queue.prototype.enqueue = function (element) {
        this.items.push(element)
    }
    // 2 从队列中删除前段元素
    Queue.prototype.dequeue = function (element) {
        return this.items.shift()
    }
    // 3 查看前端元素
    Queue.prototype.front = function (element) {
        return this.items[0]
    }
    // 4 查看队列是否为空
    Queue.prototype.isEmpty = function (element) {
        return this.items.length === 0
    }
    // 5 查看列队中元素的个数
    Queue.prototype.size = function (element) {
        return this.items.length
    }
    // 6 toString 方法
    Queue.prototype.toString = function (element) {
        var resultString = ''
        for (let i = 0; i < this.items.length; i++) {
            resultString += this.items[i]
        }
        return resultString
    }
}
// 使用队列
var queue = new Queue()

队列的操作

• 列队常见有哪些操作呢?

  • enqueue(element)：向队列尾部添加一个（或多个）新的项。
  • dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
  • front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）。
  • isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。
  • size()：返回队列包含的元素个数，与数组的length属性类似。

    三.优先级队列

    什么是优先级队列

    优先级队列的特点:

• 在普通的队列插入一个元素, 数据会被放在后端. 并且需要前面所有的元素都处理完成后才会处理前面的数据.

• 但是优先级队列, 在插入一个元素的时候会考虑该数据的优先级.(和其他数据优先级进行比较)
• 比较完成后, 可以得出这个元素正确的队列中的位置. 其他处理方式, 和队列的处理方式一样.
• 也就是说, 如果我们要实现优先级队列, 最主要是要修改添加方法. (当然, 还需要以某种方式来保存元素的优先级)

优先级队列应用也非常广泛

• 另一个现实中的例子是医院的（急诊科）候诊室。
  • 医生会优先处理病情比较严重的患者。
• 计算机中, 我们也可以通过优先级队列来重新排序队列中任务的顺序
  • 比如每个线程处理的任务重要性不同, 我们可以通过优先级的大小, 来决定该线程在队列中被处理的次序.

    四.优先级队列结构实现(js版)

    我们来封装一个优先级队列函数

// 优先级队列
function PriorQueue() {
    // 封装属性
    this.items = []
    // 二次继承
    function QueueElement(element, proiorty) {
        this.element = element
        this.proiorty = proiorty
    }
    PriorQueue.prototype.enqueue = function (element, proiorty) {
        // 创建QueueElement对象
        var queueElement = new QueueElement(element, proiorty)
        if (this.items.length === 0) {
            this.items.push(queueElement)
        } else {
            var add = false
            for (let i = 0; i < this.items.length; i++) {
                if (queueElement.proiorty < this.items[i].proiorty) {
                    this.items.splice(i, 0, queueElement)
                    add = true
                }
            }
            if (!add) {
                this.items.push(queueElement)
            }
        }
    }
    PriorQueue.prototype.toString = function (element) {
        var resultString = ''
        for (let i = 0; i < this.items.length; i++) {
            resultString += this.items[i].element + this.items[i].proiorty
        }
        return resultString
    }
}
// 使用
var pd = new PriorQueue()

参考

• 算法一看就懂队列
•