JavaScript 队列

[Checkson]

简介

队列也是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，先进先出，这点和栈不一样，在栈中，最后入栈的元素反而被优先处理。可以将队列想象成在银行前排队的人群，排在最前面的人第一个办理业务，新来的人只能在后面排队，直到轮到他们为止。

定义

队列是一种先进先出（First-In-First-Out，FIFO）的数据结构（列表的一种表现形式）。队列被用在很多地方，比如提交操作系统执行的一系列进程、打印任务池等，一些仿真系统用队列来模拟银行或杂货店里排队的顾客。

队列（Queue）类实现

完整代码地址，这里我们采用的底层数据结构仍是数组。涉及到的操作大概有：

• 用 enqueue 方法在队列队尾插入新元素，该操作也称为入队。
• 用 dequeue 方法在队列对头删除元素，该操作也称为出队。
• 用 peek 方法读取队头的元素。该操作返回队头元素，但不把它从队列中删除。
• 用 length 方法来记录队列中存储了多少元素。
• 用 clear 方法清空队列种的所有元素。
• 用 toString 方法将队列种的元素输出为字符串形式

1. 构造函数

构造我们可以接收一些可以初始化队列的参数。

function Queue () {
    var args = [].slice.call(arguments);
    this.dataList = args;
}

2. enqueue：入队

JavaScript相对其他编程语言，有一个天然的优势，就是它的数组提供 push 方法，能模仿队列的入队操作。

Queue.prototype.enqueue = function (el) {
    this.dataList.push(el);
}

3. dequeue：出队

JavaScript数组操作除了提供 push 操作，还提供了 shift 方法，来模仿队列的出队操作。

Queue.prototype.dequeue = function () {
    return this.dataList.shift();
}

4. peek：获取队头元素

Queue.prototype.peek = function () {
    return this.dataList[0];
}

5. length：获取队列的元素个数

Queue.prototype.length = function () {
    return this.dataList.length;
}

6. clear：清楚队列种所有元素

Queue.prototype.clear = function () {
    delete this.dataList;
    this.dataList = [];
}

7. toString：将队列转换为字符串

Queue.prototype.toString = function () {
    return this.dataList.join();
}

队列（Queue）类测试

var queue = new Queue('JavaScript', 'HTML', 'CSS');
console.log(queue.toString()); // JavaScript,HTML,CSS
console.log(queue.length());   // 3
queue.enqueue('React');
console.log(queue.toString()); // JavaScript,HTML,CSS,React
console.log(queue.dequeue());  // JavaScript
console.log(queue.peek());        // HTML
queue.clear();
console.log(queue.toString()); // ''

队列（Queue）实战

1. 使用队列对数据进行排序（基数排序）

队列不仅用于执行现实生活中与排队有关的操作，还可以用于对数据进行排序。计算机刚刚出现时，程序是通过穿孔卡输入主机的，每张卡包含一条程序语句。这些穿孔卡装在一个盒子里，经一个机械装置进行排序。我们可以使用一组队列来模拟这一过程。这种排序技术叫做基数排序，参见 Data Structures with C++（Prentice Hall）一书。它不是最快的排序算法，但是它展示了一些有趣的队列使用方法。

对于有限的整型数字，基数排序将数据集扫描 n（n取决于最大位数的数）次。第一次按个位上的数字进行排序，第二次按十位上的数字进行排序，直到队列对比完队列中最高位数的数。每个数字根据对应位上的数值被分在不同的盒子里。假设有如下数字：

91, 46, 85, 15, 92, 35, 31, 22

经过基数排序第一次扫描之后，数字被分配到如下盒子中：

Bin 0:
Bin 1: 91, 31
Bin 2: 92, 22
Bin 3:
Bin 4:
Bin 5: 85, 15, 35
Bin 6: 46
Bin 7:
Bin 8:
Bin 9:

根据盒子的顺序，对数字进行第一次排序的结果如下：

91, 31, 92, 22, 85, 15, 35, 46

然后根据十位上的数值再将上次排序的结果分配到不同的盒子中：

Bin 0:
Bin 1: 15
Bin 2: 22
Bin 3: 31, 35
Bin 4: 46
Bin 5:
Bin 6:
Bin 7:
Bin 8: 85
Bin 9: 91, 92

最后，将盒子中的数字取出，组成一个新的列表，该列表即为排好序的数字：

15, 22, 31, 35, 46, 85, 91, 92

使用队列代表盒子，可以实现这个算法。我们需要九个队列，每个对应一个数字。将所有队列保存在一个数组中，使用取余和除法操作决定个位和十位，或者更高位。算法的剩余部分将数字加入相应的队列，根据个位数值对其重新排序，然后再根据十位上的数值进行排序，直到最高位数值进行排序，结果即为排好序的数字。

示例代码：

function radixSort (nums) {
    // 构建队列数组
    var queues = [];
    for (var i = 0; i < 10; i++) {
        queues[i] = new Queue();
    }
    // 基排序
    var isLoop = true, radix = 10;
    do {
        isLoop = false;
        for (var i = 0, len = nums.length; i < len; i++) {
            var divide = Math.floor(radix / 10),
                temp = Math.floor(nums[i] / divide),
                index = temp % 10;
            if (temp) isLoop = true;
            queues[index].enqueue(nums[i]);
        }
        var j = 0;
        for (var i = 0; i < 10; i++) {
            while (queues[i].length()) {
                nums[j++] = queues[i].dequeue();
            }
        }
        radix *= 10;
    } while (isLoop);
    // 返回基排序结果
    return nums;
}

测试代码：

var nums = [];

for (var i = 0; i < 10; i++) {
    nums[i] = Math.floor(Math.random() * 10000);
}

console.log('排序前：')
console.log(nums.toString());

radixSort(nums);

console.log('排序后：')
console.log(nums.toString());

运行几次测试代码，结果为：

排序前：
5806,7829,7540,3360,9198,7427,4536,5336,1391,4148
排序后：
1391,3360,4148,4536,5336,5806,7427,7540,7829,9198

排序前：
9895,3646,9204,7545,1192,8832,9639,3162,2642,3995
排序后：
1192,2642,3162,3646,3995,7545,8832,9204,9639,9895

可见，基排序的时间复杂度大概为：O(n*m)。其中n是数组长度，m是最大的数的位数。（后面排序算法章节详解）。

2. 优先队列

优先队列和普通队列最大的不同是在于，在出队（dequeue）的时候，优先队列不会遵循先进先出的原则，它会根据队列中元素的权值来判断到底先删除哪个元素。

3. 循环队列

定义，循环队列在JavaScript中应用得很少，是因为JavaScript中的数组是动态的，可以动态增删数组元素，来避免队列溢出的现象。