队列是一种列表，但是它只能够在队尾插入元素，在队首删除元素。队列用于存储按照顺序排列的数据，先进先出。而栈则是后入栈的元素反而被优先处理。
实际中一般被应用在进程池、排队操作上面。
1. 队列的操作
和上一章的栈类似，队列也应该具有入队、出队、清空队列这几个基本操作。
基本结构如下：
function Queue(){
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.isEmpty = isEmpty; this.clear = clear;}
2.一个用数组实现的队列
入队操作：
function enqueue(elem){
this.dataStore.push(elem);
}
出队操作(弹出数组头部元素)：
function dequeue(){
return this.dataStore.shft();
}
返回队首和队尾元素：
function front(){
return this.dataStore[0]
}
function back(){
return this.dataStore[this.dataStore.length-1];
}
判断队列是否为空：
function empty(){
if(this.dataStore.length>0){
return true;
}else{
return false;
}
}
清空队列操作和其他操作一致，返回长度直接return this.dataStore.length即可。
3.方块舞的舞伴分配问题
首先我们要有舞池中的舞者Dancer:
function Dancer(name, sex){
this.name = name;
this.sex = sex;
}
然后我们再将舞者添加进入到队列中：
var maleQueue = new Queue();var femaleQueue = new Queue();
femaleQueue.enqueue(new Dancer('Herry', 'F')); femaleQueue.enqueue(new Dancer('Kerry', 'F'));
maleQueue.enqueue(new Dancer('Jimmy', 'M')); maleQueue.enqueue(new Dancer('Lisa', 'M')); maleQueue.enqueue(new Dancer('Lima', 'M'));
匹配舞者：
function dance(males, females){
console.info("The dancer partners are: \n");
var person;
while(!males.empty() && !females.empty()){
person = males.dequeue();
console.info("The Male is " + person.name);
person = females.dequeue();
console.info("The Female is " + person.name);
}
console.info('\n');
while(!males.empty()){
person = males.dequeue();
console.info(person.name + " is waiting!");
}
while(!females.empty()){
person = females.dequeue();
console.info(person.name + " is waiting!");
}
}
测试：
dance(femaleQueue, maleQueue);
4.对数据进行排序
使用队列排序并非是效率最高的排序算法，只能说是一个种比较有趣的方式，
我们在排序时，根据不同的位数进行排序：
比如有一组数字：
82,13,33,98,93,12, 5,88,3
我们先对其个位数进行一次排序：
0:
1:
2: 82, 12
3: 13, 33, 93, 3
4:
5: 5
6:
7:
8: 98, 88
9:
将其中的数字依次取出，可得到：
98,88,5,13,33,93,3,82,12
然后根据十位数字进行排序
0:
1:13,12
2:
3:33
4:
5:
6:
7:
8: 88, 82
9: 98, 93
取出数据：
98,93,88,82,33,13,12
再加上没剩余的个位数字：
98,93,88,82,33,13,12,5,3
实现：
首先我们要实现把一组数根据不同的位数分配到0~9十个队列中去
/**
* nums ----- 要排序的数组
* queues ----- 存放 0~9 十位数的队列数组
* n ----- 对nums中的前n个数进行排序
* digit ----- 对对应排序的位数
*/
function distribute(nums, queues, n, digit){
// 队列下标
var index = 0;
// 遍历整个n个数
for(var i=0;i<n;i++){
// 如果求个位数
if(digit == 1){
// 不能被10整除的部分为对应队列的下标
index = nums[i] % 10;
// 将当前数据加入队列
queues[index].enqueue(nums[i]);
}else{
// 获取能被10整除的部分为对应队列的下标
index = Math.floor(nums[i]/10);
// 将当前数据加入队列
queues[index].enqueue(nums[i]);
}
}
}
每次进行分配后，我们都要进行一次出队操作，放到新的数组中去：
/**
* queues ----- 存放 0~9 十位数的队列数组
* nums ----- 存放结果的数组
**/
function collect(queues, nums){
// 数组下标
var i = 0;
// 遍历所有10组队列
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++){
console.info(arr[i] + " ");
}
}
测试：
// 初始化一个队列数组，用于存放所有0~9十个数字的队列
var queues = [];
for(var i=0; i<10; i++){
queues[i] = new Queue();
}
// 初始化存放最后结果的数组
var nums = [];
// 随机生成十个 1~99的整数
for(var i=0;i<10;i++){
nums[i] = Math.floor(Math.floor(Math.random() * 101));
}
console.info("Before radix sort:");
dispArray(nums);
// 根据个位数排序加入队列中
distribute(nums, queues, 10, 1);
// 将第一次排序完的队列中的数存放到新数组中去
collect(queues, nums)
// 根据十位数排序加入队列中
distribute(nums, queues, 10, 10);
// 将第二次排序完的队列中的数存放到新数组中去
collect(queues, nums);
console.info('\n\n After radix sort:');
dispArray(nums);
5.优先队列
我们知道普通情况下队列采取先进先出的方式进行出队操作，但是这种方式不能满足一些特殊情况，例如如果我们有排队时，会有vip成员，这样就需要我们去重写dequeue除对操作了
我们可以在队列中的对象上添加一个code属性，表明该变量的优先级：
function Customer(name, code){
this.name = name;
this.code = code; this.toString = function(){ console.info(this.name+":"+this.code); };}
var ord1 = new Customer('Jimmery', 1);
var ord2 = new Customer('Kate', 1);
var ord3 = new Customer('Lame', 1);
var vip1 = new Customer('Andy', 2);
var vip2 = new Customer('Dave', 2);
var cusQueues = new Queue();
cusQueues.push(ord1);
cusQueues.push(vip1);
cusQueues.push(ord2);
cusQueues.push(vip2);
cusQueues.push(ord3);
这样我们做出队操作时，就要进行对优先级的比较：
var dequeue = function(){
// 获取当前第一个元素的优先级
var prio = this.dataStore[0].code;
// 获取初始化下标
var index = 0;
for(var i=1; i<this.dataStore.length; i++){
// 优先级值越大优先级越高
if(this.dataStore[i].code>prio){
// 记录下优先级最高元素的下标
index = i;
}
}
return this.dataStore.splice(index, 1);
}
现在我们进行测试，进行出队操作：
while(!cusQueues.empty()){
var cus = cusQueues.dequeue();
console.info(cus.toString());
}