- 定义
队列是遵循FIFO（First In First Out，先进先出）原则的一组有序的项。
在现实中，最常见的队列的例子就是排队：
来自《javascript数据结构与算法》
- 创建队列
- 声明类并声明一个数组用于存储队列中元素的数据结构。
function Queue() {
var items = [];
//这里是属性和方法
}
- 实现enqueue()方法，向队列尾部添加数个新的项。
this.enqueue = function(element) {
//用push方法，将元素添加到数组末尾
items.push(element);
};
- 实现dequeue()方法，移除队的第一项（队首），并返回被移除的元素。
this.dequeue = function() {
//shift方法，移除数组中的第一项（索引为0）的元素
return items.shift();
};
- front()方法，返回队列中的第一个元素，不改变队列。
this.front = function() {
return items.shift();
};
- isEmpty()方法，如果队列中不包含任何元素，返回true，否则返回false。
this.isEmpty = function() {
return items.length == 0;
};
- clear()方法，清空队列元素
this.clear = function() {
items = [];
};
- size()方法，返回队列包含的元素个数。
this.size = function(){
return items.lenght;
};
- 完整代码如下
function Queue() {
var items = [];
this.enqueue = function(element) {
items.push(element);
};
this.dequeue = function() {
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());
}
}
var queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.print(); // "1,2"
- 优先队列
现实生活中也有优先队列，如头等舱>商务舱>经济舱，接下来我们用代码实现下优先队列。
function PriorityQueue() {
//声明一个items用于保存元素
var items = [];
//创建一个QueueElement类，用于保存元素和其在队列中的优先级(priority越小，优先级越高)
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;
//反之就循环队列里面的每一个元素，比较优先级，如果priority小(优先级越高)的话，就用splice()方法放在该元素的前面
for(var i=0; i<items.length; i++) {
if(queueElement.priority < items[i].priority) {
items.splice(i,0,queueElement);
added = true;
break;
}
}
//如果添加的元素的priority比队列中的每一个元素都要大的话，就把它添加到队列的最后面
if(!added) {
items.push(queueElement);
}
}
};
this.isEmpty = function() {
return items.length === 0;
};
this.print = function() {
console.log(items);
};
}
var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("one",1);
priorityQueue.enqueue("two",2);
priorityQueue.enqueue("zero",0);
priorityQueue.enqueue("four",4);
priorityQueue.print(); // "0,1,2,4"
- 循环队列
循环队列的一个例子就是击鼓传花游戏（HotPotato）。在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩一个孩子（胜者）。
function hotPotato(nameList,num) {
var queue = new Queue();
//将传入的nameList遍历，将每一项添加到队列中
for(var i=0; i<nameList; i++) {
queue.enqueue(nameList[i]);
}
var eliminated = '';
//如果队列里的size大于1，就一直循环下去
while(queue.size() > 1) {
//将第一项放到最后一项，循环给定的num
for(var i=0; i<num; i++) {
queue.enqueue(queue.dequeue);
}
//传递次数达到了给定的数值，（移除第一项）
eliminated = queue.dequeue();
console.log(eliminated + '淘汰')；
}
//返回队列中仅有的最后一项
return queue.dequeue();
}
var names = ['a','b','c','d','e'];
var winner = hotPotato(names,7);
console.log('胜利者' + winner);
参考学习 ：
《javascript数据结构与算法学习》
《数据结构与算法javascript描述》
