(js描述的)数据结构[队列结构]（3）
一.队列结构的特点：
1.基于数组来实现，的一种受限的线性结构。
2.只允许在表头进行删除操作，在表尾进行插入操作。
3.先进先出（FIFO）
二.队列的一些应用：
1.按一定顺序打印文档，执行输出后的结果。
2.多线程的实际执行顺序，就如队列结构相似。
三.队列的封装：
function Queue() {
this.items = []
//向队尾添加一个元素
Queue.prototype.enqueue = function (element) {
this.items.push(element)
}
//从队头删除一个元素
Queue.prototype.dequeue = function () {
this.items.shift()
}
//返回队列中第一个元素
Queue.prototype.front = function() {
return this.items[0]
}
//检查队列是否为空
Queue.prototype.isEmpty = function () {
return this.items.length == 0
}
//返回队列的长度
Queue.prototype.size = function () {
return this.items.length
}
//返回队列的字符串形式
Queue.prototype.toString = function () {
var str = ''
for (var i=0; i< this.items.length; i++) {
str += this.items[i] + ' '
}
return str
}
}
四.队列应用的一些实例：
一.击鼓传花：
1.规则： 几个人按一定顺序轮流数数，数到给定数字者淘汰，
最后留下的一人为胜利者。需要得到最后的人名字及在原来数组中的索引序号？
function passGame(nameList, num) {
var queue = new Queue()
for (var i = 0; i< nameList.length ; i++) {
queue.enqueue(nameList[i])
}
while (queue.size() > 1) {
for (var i = 0; i< num - 1; i++) {
queue.enqueue(queue.dequeue())
}
queue.dequeue()
}
var endName = queue.dequeue()
var index = nameList.indexOf(endName)
return {index: endName}
}
五.优先级队列
1.插入的位置根据优先级而定，所以传入的数据必须携带哦优先级，其他操作与普通队列一样。（使用了内部类来增加带有优先级数据的封装性）。
function PriorityQueue() {
function PriorityElement(element, priority) {
this.element = element;
this.priority = priority;
}
this.items = [];
PriorityQueue.prototype.enqueue = function(element, priority) {
var priorityElement = new PriorityElement(element, priority);
if (this.items.length === 0) {
this.items.push(priorityElement);
} else {
var flag = false;
for (var i = 0; i < this.items.length; i++) {
if (priorityElement.priority <= this.items[i].priority) {
this.items.splice(i, 0, priorityElement);
flag = true;
}
}
if (!flag) {
this.items.push(priorityElement);
}
}
}