队列
队列（Queue），和栈一样，也是一种对数据的"存"和"取"有严格要求的[线性存储结构]
它是一种受限的线性表，先进先出FIFO(First In First Out)
- 受限之处在于它只允许在表的前端进行删除操作
- 而在表的后端进行插入操作
栈和队列不要混淆，栈结构是一端封口，特点是"先进后出"；而队列的两端全是开口，特点是"先进先出"
js实现
// js 实现队列
function Queue() {
// 队列属性
this.items = [];
// 向队列尾部添加新的项
Queue.prototype.enqueue = function(element) {
this.items.push(element);
};
// 移除队列的第一项，并返回被移除的元素
Queue.prototype.dequeue = function() {
return 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;
};
}
// 测试队列
var queue = new Queue();
queue.enqueue("aaa");
queue.enqueue("bbb");
queue.enqueue("ccc");
queue.enqueue("ddd");
console.log(queue.toString()); // aaa bbb ccc ddd
queue.dequeue();
console.log(queue.toString()); // bbb ccc ddd
console.log(queue.isEmpty()); // false
console.log(queue.size()); //3
应用 实现击鼓传花
规则： 几个朋友围成一圈，依次报数，当到某个数字时，淘汰对应的人。 剩下的人继续从淘汰的下一位开始重新报数。 知道只剩余1人时结束。
// 击鼓传花
// list 所有人 num 第几个数字淘汰
function passGame(list, num) {
// 创建队列
var queue = new Queue();
// 把list中的人加入到队列中
for (var i = 0; i < list.length; i++) {
queue.enqueue(list[i]);
}
// 开始报数
// 循环条件 剩余人数大于1
while (queue.size() > 1) {
// 从0开始 到 淘汰数字前 的所有人 重新加入队列
for (var i = 0; i < num - 1; i++) {
queue.enqueue(queue.dequeue());
}
// 对应的淘汰数字的人，直接淘汰
queue.dequeue();
}
// 获取最后的胜利的人
var endName = queue.front();
console.log('胜利者', endName);
// 返回 剩下的胜利者是原来列表第几
return list.indexOf(endName);
}
var list = ['zs', 'ls', 'ww', 'zl', 'leilei']
console.log(passGame(list, 3)) //最后胜利 zl 第3
优先级队列
优先队列不再遵循先入先出的原则，而是分为两种情况：
最大优先队列，无论入队顺序，当前最大的元素优先出队。
最小优先队列，无论入队顺序，当前最小的元素优先出队。
优先级队列中的元素并非依照被推入队列的顺序排列。而是自动依照元素的权值排列。权值最高者排在最前面。
优先级队列要考虑的问题
- 每个元素不再只是一个暑假，而且包含数据的优先级
- 在添加方式中，根据优先级放入正确的位置。
比如现实中的例子：
急诊科会考虑病情严重的患者，而不是排号的顺序
js实现优先级队列
// 优先级队列
function PriorityQueue() {
// 封装属性
this.items = [];
// PriorityQueue 中创建一个内部类， 用来保存元素的优先级
// 传入元素 和 优先级
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}
// 实现插入方法
PriorityQueue.prototype.enqueue = function(element, priority) {
// 创建 QueueElement对象
var queueElement = new QueueElement(element, priority);
// 判断队列是否为空, 为空直接放入队列
if (this.items.length === 0) {
this.items.push(queueElement);
} else {
// 否则 遍历比较队列中的每一项的优先级，
// 当前传入元素的优先级小于队列中的某一项时，插入，并终止遍历
var flag = false; // 标志 是否插入
for (var i = 0; i < this.items.length; i++) {
if (queueElement.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElement);
flag = true;
break;
}
}
if (!flag) {
this.items.push(queueElement);
}
}
};
// 移除队列的第一项，并返回被移除的元素
PriorityQueue.prototype.dequeue = function() {
return this.items.shift();
};
// 返回队列第一个元素
PriorityQueue.prototype.front = function() {
return this.items[0].element;
};
// 队列是否为空
PriorityQueue.prototype.isEmpty = function() {
return this.items.length === 0;
};
// 返回队列的元素个数
PriorityQueue.prototype.size = function() {
return this.items.length;
};
// 将队列转换为字符串形式
PriorityQueue.prototype.toString = function() {
var str = "";
for (var i = 0; i < this.items.length; i++) {
str += this.items[i].element + " ";
}
return str;
};
}
// 测试代码
var pq = new PriorityQueue()
pq.enqueue('aaa-100', 100)
pq.enqueue('bbb-10', 10)
pq.enqueue('ccc-50', 50)
pq.enqueue('ddd-30', 30)
console.log(pq.toString()); // bbb-10 ddd-30 ccc-50 aaa-100
pq.dequeue()
console.log(pq.toString()); //ddd-30 ccc-50 aaa-100
console.log(pq.isEmpty()); // false
console.log(pq.size()); // 3
网友评论