队列遵循先进先出原则——如同排队
4.1 创建队列
function Queue() {
// 使用数据结构为数组来存储队列中的元素
var items = [];
/*
队列可用方法
enqueue(ele): 向队尾添加一个新的项
dequeue(): 移除队列的第一项，并返回被移除的元素
front(): 返回队列中的第一项
isEmpty(): 如果队列不含任何元素返回true,否则false
size(): 返回队列包含的元素个数
*/
this.enqueue = function (ele) {
items.push(ele);
};
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 () {
console.log(items.toString());
}
}
使用Queue类
var queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue('John');
queue.enqueue('Jack');
queue.enqueue('Camel');
queue.print(); // ['John', 'Jack', 'Camel']
console.log(queue.size()); // 3
console.log(queue.isEmpty()); // false
queue.dequeue();
queue.dequeue();
queue.print(); // ['Camel']
4.2 优先队列
function PriorityQueue() {
var items = [];
this.isEmpty = function () {
return items.length === 0;
};
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}
this.enqueue = function (element, priority) {
var queue = new QueueElement(element, priority);
if (this.isEmpty()) {
items.push(queue);
} else {
var added = false;
for (var i = 0; i < items.length; i++) {
if (queue.priority < items[i].priority) {
items.splice(i, 0, queue); // 优先级小的会被插入到队列前面
added = true;
break;
}
}
if (!added) {
items.push(queue);
}
}
};
this.print = function() {
console.log(items);
};
}
var queue = new PriorityQueue();
queue.enqueue('John', 2);
queue.enqueue('Backham', 1);
queue.enqueue('Jack', 1);
queue.print();
4.3 循环队列——击鼓传花
function hotPotato(list, num) {
var queue = new Queue();
for (var i = 0; i < list.length; i++) {
queue.enqueue(list[i]);
}
var player = '';
while (queue.size() > 1) {
for (var i = 0; i < num; i++) {
queue.enqueue(queue.dequeue());
}
player = queue.dequeue();
console.log(player + '在击鼓传花游戏中被淘汰！')
}
return player;
}
var names = ['周杰伦', '陈奕迅', '王力宏', '蔡依林', 'TFBoys', '容祖儿', '韩红', '郑爽'];
var winner = hotPotato(names, 4);
console.log('胜利者是' + winner);
