JavaScript数据结构与算法之队列原理与用法实例详(2)
下面是完整的JS代码如下：
function Queue() {
this.dataStore = [];
}
Queue.prototype = {
// 向队尾添加一个元素
enqueue: function(element) {
this.dataStore.push(element);
},
// 删除队首的元素
dequeue: function(){
return this.dataStore.shift();
},
// 读取队首的元素
front: function(){
return this.dataStore[0];
},
// 读取队尾的元素
back: function(){
return this.dataStore[this.dataStore.length - 1];
},
// 显示队列内的所有元素
toString: function(){
var retStr = "";
for(var i = 0; i < this.dataStore.length; ++i) {
retStr += this.dataStore[i] + "\n";
}
return retStr;
},
// 判断队列是否为空
empty: function(){
if(this.dataStore.length == 0) {
return true;
}else {
return false;
}
}
};
我们现在可以对以上代码测试下：如下：
var q = new Queue();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
console.log(q.toString()); // a b c
q.dequeue();
console.log(q.toString()); // b c
console.log("Front of queue:" +q.front()); // b
console.log("Back of queue:" +q.back()); // c
二：使用队列对数据进行排序
比如对于 0 ~ 99 的数字进行排序，原理是：先对个位上的数字进行排序一次，然后对十位上的数字再进行排序一次。每个数字根据对应位上的数值被分在不同的盒子里面，然后对于个位上的数字采用除余数的方法，对于10位上的数字采用除法的方法，那么这种排序叫做 “基数排序”. 但是它不是最快的排序方法，但是它描述了一些有趣的队列使用方法。
比如如下数组：
var nums = ["50","12","95","7","90","3","74","81","91","72"];
1. 经过基数排序--个位排序后，数字被分配在不同的盒子里面。（在JS里面，我们可以分配在不同的队列Queue实例类里面）。如下
queues[0] = 50 或者 90 queues[1] = 81 或者 91 queues[2] = 12 或者 72 queues[3] = 3 queues[4] = 74 queues[5] = 95 queues[6] queues[7] = 7 queues[8] queues[9]
根据盒子的顺序，对数字第一次个位排序后结果如下：
nums = [50,90,81,91,12,72,3,74,95,7]
2. 然后根据十位上的数值再将上次排序后的结果分配到不同的盒子中。如下：
queues[5] = 50 queues[9] = 90 queues[8] = 81 queues[9] = 91 queues[1] = 12 queues[7] = 72 queues[0] = 3 queues[7] = 74 queues[9] = 95 queues[0] = 7
最后，将盒子中的数字取出，组成一个新的列表，该列表即为排序好的数字。如下：
即可生成如下：