读【数据结构与算法】之队列
基本实现
队列也是一种列表，他只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，先进先出，而栈是后入先出的。
队列主要有两种操作：向队列中插入新元素以及删除队列中元素。插入操作也叫入队，删除操作也叫出队。入队在队尾插入新元素，而出队则是删除队首的元素。
下边的是简单实现：
/**
* Class Queue
* 队列 Queue
*/
function Queue() {
this._list = []; // 用于存储数据的数组
}
Queue.prototype = {
constructor: Queue,
/**
* 向队尾添加一个新元素
* @param {Any} element 新元素
* @return {Undefined} undefined
*/
enqueue: function enqueue(element) {
this._list.push(element);
},
/**
* 取出队首元素
* @return {Any} 队首元素
*/
dequeue: function dequeue() {
return this._list.shift();
},
/**
* 返回队首元素
* @return {Any} 队首元素
*/
front: function front() {
return this._list[0];
},
/**
* 返回队尾元素
* @return {Any} 队尾元素
*/
back: function back() {
return this._list[this._list.length - 1];
},
/**
* 返回队列的所有的元素
* @return {String} 结果字符串
*/
toString: function toString() {
var ret = '';
for (var i = 0, len = this._list.length; i < len; i++) {
ret += this._list[i] + '\n';
}
return ret;
},
/**
* 判断队列是否为空
* @return {Boolean} 是否为空
*/
empty: function empty() {
return !this._list.length;
}
};
具体运行例子请看demojs实现队列Queue
利用队列可以对数据进行排序
有一种排序叫基数排序，这个排序的大概过程就是：
对于0~99的数字，这种排序将会扫描2次，如果是0~999的数字，将会是3次了。第一次按照个位上的排序，第二次按照十位上的数字排序；如果有更多位的话，以此类推。
每一个位上的数字肯定是0~9的，这里假定有10个队列分别对应，所以，对于每一个数字，每次按照不同位来排的时候，如果该位上的数字是n，那么就往第n个队列中添加他。
然后，在根据队列顺序，将每一个队列的结果按顺序一个一个的排列就好了。
/**
* 根据相应位（个位或十位）上的数值，将数字分配到相应队列函数中
* @param {Array} nums 数字组成数组
* @param {Array} queues 队列组成数组
* @param {Number} n 长度
* @param {Number} digit 个位1或者十位10
* @return {Undefined} undefined
*/
function distribute(nums, queues, n, 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]);
}
}
}
/**
* 从队列中收集数字
* @param {Array} queues 队列数组
* @param {Array} nums 数字数组
* @return {Undefined} undefined
*/
function collect(queues, nums) {
for (var i = 0, digit = 0; digit < 10; digit++) {
while (!queues[digit].empty()) {
nums[i++] = queues[digit].dequeue();
}
}
}
具体运行例子请看demojs利用队列排序