数据结构基础-队列篇

那日…天朗气清，惠风和畅，面试老哥让我实现一个任务优先级队列。

嘛，其实挺简单的东西，愣是让我整复杂了。因为一开始老哥的问法是“setTimeout根据其中的回调delay时长来设置优先级，时间越长的优先级越高，并且最后调用的时候按照优先级高到低依次被调用”。我第一反应其实是Event Loop，宏任务本身就有一个维护异步的机制。但是这似乎没办法使它们有序回调触发，思考了一会我估计是我理解错了，面试老哥也换了种描述。大意就是简单实现一个任务优先级队列，使其中高优先级的先被调用，于是我大致给了下面这样的代码：

class PriorityQueue {
    constructor() {
        this.taskQueue = [];
    }
    addTask(fn, delay) {
        let taskDTO = {
            fn: fn,
            priority: delay,
        };
        this.taskQueue.push(taskDTO);
        this.taskQueue.sort((a, b) => a.priority - b.priority);
    }
    runTask() {
        let curTask = this.taskQueue.pop();
        curTask.fn();
    }
}

这个方案自然是能跑的，但是也是极蠢的，相当于每次添加任务都需要去排序一次，众所周知，Array.prototype.sort这个方法在不同数量级分别会采用直插和快排的排序方案。如果使用sort排序，那么其实每一次排序前，我们的既得队列已然是有序的了，完全没必要再次去进行排序动作，尤其是当数量级上去以后会造成大量冗余的运算。真正的处理方式应当是插入。在插入的过程中判断优先级，使队列整体有序。

这个问题，套用生活中的“插队”就特别好理解（不过不知道为什么当时会纠结一个中间值的问题）所以没有采用这个方案。现在复盘一下，先看一张生活中的排队图：

那我们大致有以下的判断逻辑：

1. 队列中无任务，插入第一个任务；
2. 来了新任务，进行优先级比较。从队列首部到尾部检视（循环）是否存在任务优先级比插入任务低的；
3. 不存在，弟弟老老实实排队去，插入到队列尾部；
4. 存在，则找到第一个比其优先级低的，插到这个任务前。当时我就脑抽在这里，因为本身插入的这个逻辑就是构建一个有序队列，所以找到第一个小的插入后，整体依旧是有序的。

改写一下：

class PriorityQueue {
    constructor() {
        this.taskQueue = [];
    }
    addTask(fn, delay) {
        let taskDTO = {
            fn: fn,
            priority: delay,
        };
        if (this.taskQueue.length === 0) {
            this.taskQueue.push(taskDTO);
        } else {
            let i = 0; 
            for (;i < this.taskQueue.length; i++) {
                if (this.taskQueue[i].priority < taskDTO.priority) {
                    this.taskQueue.splice(i, 0, taskDTO);
                    break;
                }
            }
            if (i === this.taskQueue.length) {
                this.taskQueue.push(taskDTO);
            }
        }
    }
    runTask() {
        let curTask = this.taskQueue.shift();
        curTask.fn();
    }
}

简单测试一下：

先声明三个输出函数：

实例化优先级队列实例并添加任务：

执行：

就是这么基础…