队列特点:遵循先进先出(FIFO)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。 创建队列
首先,创建一个类来表示一个队列。
function Queue () {}
同样,我们选择数组来存储队列中的元素。
var items = [];
接下来,我们考虑一下为这个队列声明哪些方法:
- enqueue(element):向队列尾部添加一个新的项。
- dequeue():移除队列的第一项,并返回被移除的项。
- front():返回队列中的第一个元素,队列不做任何变动。
- isEmpty():判断队列是否为空。
- size():返回队列长度。
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.size = function () {
return items.length;
};
this.print = function () {
console.log(items.toString());
};
}
嗯,我们已经算是创建一个较为完整的队列了,接下来,我再说说其它的。
优先队列
优先队列元素的添加和移除是基于优先级的。拿医院候诊室举例,医生会优先处理病情比较严重的患者。
function PriorityQueue () {
var items = [];
//每个元素都包含要添加到队列的元素,以及在队列中的优先级
function QueueElement (element, priority) {
this.element = element;
this.priority = priority;
}
this.enqueue = function () {
var queueElement = new QueueElement(element, priority);
//当队列为空,直接添加
if (this.isEmpty()) {
items.push(queueElement);
}else {
var added = false;
//循环比较所添加元素和队列中元素优先级
//当找到比要添加元素优先级更大的项时,就把新元素插入到它之前(priority越小,优先级越高)
//优先级相同,遵循先进先出原则
for (var i = 0; i < items.length; i++) {
if (queueElement.priority < items[i].priority) {
items.splice(i, 0, queueElement);
added = true;
break;
}
}
if (!added) {
items.push(queueElement);
}
}
}
//其他方法和默认的Queue实现相同
}
循环队列——击鼓传花
还有一个修改版的队列实现,那就是循环队列。我们拿击鼓传花这个例子来实现循环队列。 在游戏中,孩子们围成一个圆圈,把花传给旁边的人,某一时刻传花停止,拿着花的孩子结束游戏,重复这个过程,直到剩下一个孩子(胜者)。
function hotPotato (nameList, num) {
var queue = new Queue;
var eliminated = "";
for (var i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i]);//将玩游戏孩子名字加入队列
}
while (queue.size() > 1) {
//从队列开头移除一项,再将其添加到队列末尾
for (var i = 0; i < num; i++) {
queue.enqueue( queue.dequeue() );
}
eliminated = queue.dequeue();
console.log(eliminated + "被淘汰");
}
return queue.dequeue();
}
var names = ["小明", "小花", "小黄", "小易", "小华"];
var winner = hotPotato(names, 5);//可以改变传入数字,模拟不同场景
console.log("胜利者:" + winner);
控制台模拟结果如图: