队列，和栈有点类似，但是又不太一样，队列遵循 先进先出 的原则。
一、模拟实现队列
首先，为队列声明一些方法：
-
enqueue(element)：向队列尾部添加一个或者多个新的项。 -
dequeue()：移除队列的第一(即排在队列最前面的)项，并返回被移除的元素。 -
front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何改动。 -
isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。 -
size()：返回队列中的元素个数，和数组的length属性类似。
然后，尝试实现这些方法：
function Fun() {
const items = [];
// 1. 元素入队列
this.enqueue = function(element) {
items.push(element);
};
// 2. 元素出队列
this.dequeue = function() {
return items.shift();
};
// 3. 查看队列顶部元素
this.front = function() {
return items[0];
};
// 4. 判断队列是否为空
this.isEmpty = function() {
return items.length === 0;
};
// 5. 查看整个队列长度
this.size = function() {
return items.length;
};
// 6. 查看整个队列
this.print = function() {
console.log(items);
}
};
let fun = new Fun();
fun.enqueue('1'); // [ '1' ]
fun.enqueue('2'); // [ '1', '2' ]
fun.dequeue(); // [ '2' ]
fun.dequeue(); // [ ]
fun.print(); // []
最后，推荐几个案例可以进一步了解队列：
二、优先队列
示例：
function PriorityQueue() {
// 1. 定义空数组
const items = [];
// 2. 定义队列
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}
// 3. 实现入队列方式
this.enqueue = function(element, priority) {
let queueElement = new QueueElement(element, priority);
let added = false;
for (let 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);
}
};
// 4. 实现队列打印
this.print = function() {
items.forEach((ele) => {
console.log(`${ele.element} ${ele.priority}`);
})
};
// 5. 其他方法和默认的Queue实现相同
}
const priorityQueue = new PriorityQueue();
priorityQueue.enqueue('zhangsan', 1);
priorityQueue.enqueue('JavaScript', 2);
priorityQueue.enqueue('张三', 1)
priorityQueue.print();
// zhangsan 1
// 张三 1
// JavaScript 2
三、击鼓传花
示例：
/**
* @name 队列模拟
*/
function Queue() {
const items = [];
// 1. 元素入队列
this.enqueue = function(element) {
items.push(element);
};
// 2. 元素出队列
this.dequeue = function() {
return items.shift();
};
// 3. 查看队列顶部元素
this.front = function() {
return items[0];
};
// 4. 判断队列是否为空
this.isEmpty = function() {
return items.length === 0;
};
// 5. 查看整个队列长度
this.size = function() {
return items.length;
};
// 6. 查看整个队列
this.print = function() {
console.log(items);
}
};
/**
* @name 击鼓传花
* @param {*} nameList 人名
* @param {*} num 淘汰的位置
*/
function hotPotato(nameList, num) {
let queue = new Queue();
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i]);
}
let eliminated = '';
while (queue.size() > 1) {
for (let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue());
}
eliminated = queue.dequeue();
console.log('淘汰了：' + eliminated);
}
return queue.dequeue();
}
const names = ['name1', 'name2', 'name3', 'name4', 'name5'];
const winner = hotPotato(names, 7);
console.log('赢家是：' + winner);
// 淘汰了：name3
// 淘汰了：name2
// 淘汰了：name5
// 淘汰了：name4
// 赢家是：name1
在这次游戏中，淘汰顺序是：
- name3
- name2
- name5
- name4
最后剩下 name1，退出循环，我们将其推出栈（此时栈为空）。
当然，这里我们固定了传递进来的数字为 7，如果我们通过随机来指定一个，那么应该是：
// 随机式击鼓传花
// ...主体代码如上
const names = ['name1', 'name2', 'name3', 'name4', 'name5'];
const winner = hotPotato(names, Math.floor(Math.random() * 10 + 1));
console.log('赢家是：' + winner);
// 淘汰了：name1
// 淘汰了：name4
// 淘汰了：name2
// 淘汰了：name3
// 赢家是：name5
// 现在淘汰的位置不固定了
不折腾的前端，和咸鱼有什么区别！ ------冷枫1211
