队列
队列是遵循FIFO(First In First Out,先进先出)的一组有序的项。在计算机科学中，最常见的是打印队列，比如我需要打印五份文档，就先打开每个文档，再点击打印按钮，则每一个文档都会被发送到打印队列。第一个发送到打印队列的文档会首先打印，依次类推，直到打印完所有五篇文档。此外，需要说明一下的是，在linux中，FIFO是一种特殊的文件类型，也即是我们熟知的”管道“，它主要的目的在于解决多个程序访问同一个文件造成的错误问题，使用ls命令时，该类文件的第一个属性为p。详细请看附录的man fifo图。
A queue is an example of a linear data structure, or more abstractly a sequential collection. Queues provide services in computer science, transport, and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later.
js当中是怎样定义队列的呢？实质上可以利用数组的一些特性，封装成一个队列类来实现。请看：
function Queue() {//声明这个队列类的属性和方法
var items = [];
this.enqueue = function(element){//入列
items.push(element);
};
this.dequeue = function(){//出列，shift() 方法用于把数组的第一个元素从其中删除并返回第一个元素的值。
return items.shift();
};
this.front = function(){
return items[0];
};
this.isEmpty = function(){
return items.length == 0;
};
this.clear = function(){
items = [];
};
this.size = function(){
return items.length;
};
this.print = function(){
console.log(items.toString());
};
}
Quene和Stack很像，唯一的不同就是dequeue方法和front方法，这是FIFO和LIFO的设计原则不一致导致的。具体是怎样的所谓“最先入列的元素同时最先出列”呢？来看几个栗子吧：
var queue = new Queue();
console.log(queue.isEmpty());
queue.enqueue("John");
queue.enqueue("Jack");
queue.print();
queue.enqueue("Camila");
queue.print();
console.log(queue.size());
console.log(queue.isEmpty());
queue.dequeue();
queue.dequeue();
queue.print();
从下面的运行结果应该可以看出，队列的这个特性。
当然这里说的队列是默认队列，下面说说其他的队列。
优先队列（最小优先队列）
数据结构某种意义上是为了抽象我们的现实生活而服务的。优先队列相当于在普通队列的基础上增加了一个优先级的属性，这就好比坐飞机的时候，头等舱的乘客的优先级高于经济舱的乘客的优先级一样。
In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it.
function PriorityQueue() {
var items = [];
function QueueElement (element, priority){
this.element = element;
this.priority = priority;
}
this.enqueue = function(element, priority){
var queueElement = new QueueElement(element, priority);
if (this.isEmpty()){
items.push(queueElement);
} else {
var added = false;
for (var i=0; i<items.length; i++){
if (queueElement.priority < items[i].priority){
items.splice(i,0,queueElement);
added = true;
break;
}
}
if (!added){//进入这里就说明优先级的数值最大，其优先级也最低，
//注意这里描述的是最小优先队列，即1
//的优先级最大，其他的随着priority值的增大，对应的优先级其实是越小的。
items.push(queueElement);
}
}
};//The splice method modifies arrayObj by removing the specified
//number of elements from position
//start and inserting new elements.
//The deleted elements are returned as a new Array object.
this.dequeue = function(){
return items.shift();
};
this.front = function(){
return items[0];
};
this.isEmpty = function(){
return items.length == 0;
};
this.size = function(){
return items.length;
};
this. print = function(){
for (var i=0; i<items.length; i++){
console.log(items[i].element + ' - ' + items[i].priority);
}
};
}
var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jack", 1);
priorityQueue.enqueue("Camila", 1);
priorityQueue.enqueue("Maxwell", 2);
priorityQueue.enqueue("Ana", 3);
priorityQueue.print();
运行结果如下：
注意上面代码中的splice函数的使用方式。第一个参数指定即将开始处理的数组索引。第二个参数为正数的时候就删除相应个数的元素，在原来的基础之上添加第三个参数以及其后的任意多个元素；当第二个参数是0的时候则不删除任何的元素，而只在原来的基础之上添加第三个参数以及其后的任意多个元素，请看下面的栗子：
var arr = new Array("4", "11", "2", "10", "3", "1");
arr.splice(2, 2, "21", "31");
document.write(arr);// Output: 4,11,21,31,3,1
循环队列
利用前面已经定义过的队列，稍作修改，就实现一个新版本的队列——循环队列（Circular Queue）。
Circular queue is a linear data structure. It follows FIFO principle. In circular queue the last node is connected back to the first node to make a circle. Circular linked list follow the First In First Out principle. Elements are added at the rear end and the elements are deleted at front end of the queue.
循环队列好比是一个环，front和end是相连的，按照特定的次序（逆时针或者顺时针）进行遍历，接下来的代码模拟了一个hot potato游戏的逻辑，它揭示了循环队列的内涵。代码如下：
function hotPotato (nameList, num){
var queue = new Queue();
for (var i=0; i<nameList.length; i++){
queue.enqueue(nameList[i]);
}
var eliminated = '';
while (queue.size() > 1){
for (var i=0; i<num; i++){
queue.enqueue(queue.dequeue());//循环num次，将检索出来的那个元素放到最末尾（end）
}
eliminated = queue.dequeue();
//循环一次之后就把这一轮循环结束时的front元素给删除（kick out)
//此时队列的成员会逐渐减少。
console.log(eliminated + ' was eliminated from the Hot Potato game.');
}
return queue.dequeue();
}
var names = ['John','Jack','Camila','Ingrid','Carl'];
var winner = hotPotato(names, 7);
console.log('The winner is: ' + winner);//剩者为王
运行结果如下：
附录
man fifo
