队列的JavaScript实现

队列的结构特点

队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

队列的js实现

可以用ES5和ES6两种语法实现队列的结构。

ES5

let Queue = function () {
  let items = []
  this.enqueue = function (element) {
    items.push(element)
  }
  this.dequeue = function () {
    return items.shift()
  }
  this.front = function () {
    return items[0]
  }
  this.isEmpty = function () {
    return items.length === 0
  }
  this.size = function () {
    return items.length
  }
  this.print = function () {
    console.log(items.toString())
  }
}

ES6

let Queue = (function () {
  const items = new WeakMap()
  class Queue {
    constructor() {
      items.set(this, [])
    }
    enqueue(element) {
      let q = items.get(this)
      q.push(element)
    }
    dequeue() {
      let q = items.get(this)
      return r = q.shift()
    }
    front() {
      let q = items.get(this)
      return q[0]
    }
    isEmpty() {
      let q = items.get(this)
      return q.length === 0
    }
    size() {
      let q = items.get(this)
      return q.length
    }
    print() {
      let q = items.get(this)
      console.log(q.toString())
    }
  }
  return Queue
})()

关于为什么使用WeakMap和闭包，参考上篇文章[栈的javascript实现和栈的应用
]

优先队列

优先队列指队列里的元素的添加和移除是基于优先级的。下面实现一个最小优先队列，最小优先队列指优先级的值较小的元素放置在队列最前面。反之则是最大优先队列。

function PriorityQueue() {
  let items = []
  function QueueElement(element, priority) {
    this.element = element
    this.priority = priority
  }
  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)
    }
  }
  this.print = function () {
    for (let i = 0; i < items.length; i++) {
      console.log(`${items[i].element} - ${items[i].priority}`)
    }
  }
  // 其他方法和默认的Queue实现相同

}

循环队列-击鼓传花

循环队列可以顾名思义。下面实现一个击鼓传花的游戏。

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()
}

let names = ['小明', '小红', '小刚', '小绿', '小黄', '小强']
let winner = hotPotato(names, 7)
console.log('胜利者是 ' + winner)

JavaScript任务队列

JavaScript语言的一大特点就是单线程，也就是说，同一个时间只能做一件事。单线程就意味着，所有任务需要排队，前一个任务结束，才会执行后一个任务。如果前一个任务耗时很长，后一个任务就不得不一直等着，这显然是不合理的。

于是，设计者把所有任务分成两种，一种是同步任务（synchronous），另一种是异步任务（asynchronous）。

同步任务指的是，在主线程上排队执行的任务，只有前一个任务执行完毕，才能执行后一个任务。

异步任务指的是，不进入主线程、而进入"任务队列"（task queue）的任务，只有"任务队列"通知主线程，某个异步任务可以执行了，该任务才会进入主线程执行。
具体JavaScript事件循环和任务队列介绍请移步javascript事件循环(event loop)与任务队列