4.JavaScript 数据结构与算法（四）队列

[webVueBlog]

队列（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)
}