4.JavaScript 数据结构与算法（四）队列 #4
Description
队列（Queue）是一种运算受限的线性表，特点：先进先出。(FIFO：First In First Out)
受限之处：
- 只允许在表的前端（front）进行删除操作。
- 只允许在表的后端（rear）进行插入操作。
队列在程序中的应用
- 打印队列：计算机打印多个文件的时候，需要排队打印。
- 线程队列：当开启多线程时，当新开启的线程所需的资源不足时就先放入线程队列，等待 CPU 处理。
队列常见的操作
enqueue(element)向队列尾部添加一个（或多个）新的项。dequeue()移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。front()返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与 Map 类的 peek 方法非常类似）。isEmpty()如果队列中不包含任何元素，返回 true，否则返回 false。size()返回队列包含的元素个数，与数组的 length 属性类似。toString()将队列中的内容，转成字符串形式。
代码实现
class Queue {
constructor() {
this.items = [];
}
enqueue(item) {
this.items.push(item)
}
dequeue() {
return this.items.shift()
}
front() {
return this.items[0]
}
isEmpty() {
return this.item.length === 0
}
// size() 查看队列中元素的个数
size() {
return this.items.length
}
// toString() 将队列中的元素以字符串形式返回
toString() {
let result = ''
for (let item of this.items) {
result += item + ' '
}
return result
}
}击鼓传花
分析：传入一组数据集合和设定的数字 number，循环遍历数组内元素，遍历到的元素为指定数字 number 时将该元素删除，直至数组剩下一个元素。
function queueGame(nameList, number) {
const queue = new Queue();
for (const name of nameList) {
queue.enqueue(name)
}
while (queue.size() > 1) {
for (let i = 0; i < number - 1; i++) {
queue.enqueue(queue.dequeue());
}
queue.dequeue();
}
const endName = queue.front()
return nameList.indexOf(endName)
}Reactions are currently unavailable