队列

什么是队列？

只能在队尾插入元素，在队首删除元素
用于存储按顺序排列的数据，先进先出

队列被用在很多地方，比如提交操作系统执行的一系列进程、打印任务池等，一些仿真系统用队列来模拟银行或杂货店里排队的顾客。

队列的操作

向队列中插入新元素
删除队列中的元素
读取队头的元素

一个用数组实现的队列

function Queue() {
        this.dataStore = [];
        this.enqueue = enqueue;
        this.dequeue = dequeue;
        this.front = front;
        this.back = back;
        this.toString = toString;
        this.empty = empty;
}

向队尾添加一个元素

function enqueue(element) {
        this.dataStore.push(element);
}

删除队首的元素

function dequeue() {
        return this.dataStore.shift();
}

读取队首和队尾的元素

     function front() {
        return this.dataStore[0];
}
     function back() {
        return this.dataStore[this.dataStore.length-1];
}

显示队列内的所有元素

function toString() {
        var retStr = "";
        for (var i = 0; i < this.dataStore.length; ++i) {
           retStr += this.dataStore[i] + "\n";
        return retStr;
     }

判断队列是否为空

function empty() {
        if (this.dataStore.length == 0) {
           return true;
        }
        else {
           return false;
} }

队列的应用

使用队列对数据进行排序

对于 0~99 的数字，基数排序将数据集扫描两次。第一次按个位上的数字进行排序，第二次按十位上的数字进行排序。每个数字根据对应位上的数值被分在不同的盒子里。假设有如下数字:

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 distribute(nums, queues, n, digit) { //参数digit表示个位或十位上的值 for (var i = 0; i < n; ++i) {
	if (digit == 1) {
	    queues[nums[i]%10].enqueue(nums[i]);
	} else {
	    queues[Math.floor(nums[i] / 10)].enqueue(nums[i]); }
	} 

}

下面是从队列中收集数字的函数:

function collect(queues, nums) {
        var i = 0;
        for (var digit = 0; digit < 10; ++digit) {
           while (!queues[digit].empty()) {
              nums[i++] = queues[digit].dequeue();
           }
} }

显示数组内容

function dispArray(arr) {
        for (var i = 0; i < arr.length; ++i) {
           putstr(arr[i] + " ");
        }
}

实例化个例子：

var queues = [];

     for (var i = 0; i < 10; ++i) {
        queues[i] = new Queue();
     }

     var nums = [];

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

     console.log("Before radix sort: ");
     dispArray(nums);

     distribute(nums, queues, 10, 1);
     collect(queues, nums);

     distribute(nums, queues, 10, 10);
     collect(queues, nums);

     console.log("\n\nAfter radix sort: ");
     dispArray(nums);

--------------------

     Before radix sort:
     45 72 93 51 21 16 70 41 27 31

     After radix sort:
     16 21 27 31 41 45 51 70 72 93

     Before radix sort:
     76 77 15 84 79 71 69 99 6 54

     After radix sort:
     6 15 54 69 71 76 77 79 84 99