javascript数据结构之队列

队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。这就跟排队买包子一样，你先来就先买，后来就排队等待，这个就很有纪律性，不会出现有人插队的坏现象了。

首先说一下队列的常用操作：

Queue()     // 创建一个空的队列对象
enqueue()   // 入队操作，将元素放置队尾
dequeue()   // 出队操作，将队首的元素移除队列并返回
front()     // 返回队首元素，不对队列做操作
isEmpty()   // 判断队列是否为空
size()      // 返回队列内元素的个数
clear()     // 清空队列

使用javascript模拟队列的实现：

function Queue () {
  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.clear = function () {
    // 移除队列里所有的元素
    items = []
  }
  this.print = function () {
    console.log(items.toString())
  }
  this.toString = function () {
    return items.toString()
  }
}

简单的队列就实现了，那么来说说优先队列，在开始说了，这是一个有纪律的队列，但是呢，也是会有特殊情况的，比如说在医院排队看病，这时来了个快要生的孕妇，总不能让人家也跟在后面排队吧，这时孕妇就有了优先权，可以更快的处理。那么怎么用javascript来实现呢，首先得给加入队列的元素一个标志，标志这个元素的优先级：

function QueueElement (element, key) {
    this.element = element
    this.key = key
}

在加入队列时也要给一个标志，根据标志插入到队列中：

this.enqueue = function (element, key) {
    let queueElement = new QueueElement(element, key)
    if (this.isEmpty()) {
      items.push(queueElement)
    } else {
      let added = false
      for (let i = 0; i < items.length; i++) {
        if (items[i].key > key) {
          items.splice(i, 0, queueElement)
          added = true
          break
        }
      }
      if (!added) {
        items.push(queueElement)
      }
    }
  }

其他的都与普通队列一样，具体代码如下：

function PriorityQueue () {
  let items = []
  function QueueElement (element, key) {
    this.element = element
    this.key = key
  }
  this.enqueue = function (element, key) {
    let queueElement = new QueueElement(element, key)
    if (this.isEmpty()) {
      items.push(queueElement)
    } else {
      let added = false
      for (let i = 0; i < items.length; i++) {
        if (items[i].key > key) {
          items.splice(i, 0, queueElement)
          added = true
          break
        }
      }
      if (!added) {
        items.push(queueElement)
      }
    }
  }
  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.clear = function () {
    // 移除队列里所有的元素
    items = []
  }
  this.print = function () {
    console.log(items.toString())
  }
  this.toString = function () {
    return items.toString()
  }
}

一道小题

击鼓传花游戏，在这个游戏中，孩子们围成一个圆圈，把花尽快的传递给旁边的人。某一时刻传花停止，这个时候花落在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩下一个孩子。

解答：

function hotPotato (nameList) {
  let childrenQueue = new Queue()
  for(let i = 0; i < nameList.length; i++) {
    childrenQueue.enqueue(nameList[i])
  }
  while (childrenQueue.size() > 1) {
    let ring = Math.round(Math.random() * childrenQueue.size() * 2 + childrenQueue.size())
    for(let i = 0; i < ring; i++) {
      let out = childrenQueue.dequeue()
      childrenQueue.enqueue(out)
      // 将出队的元素再放入队尾，构成循环队列
      let ring = Math.round(Math.random() * childrenQueue.size() * 2 + childrenQueue.size())
      // 随机淘汰参赛者
    }
    console.log(childrenQueue.dequeue() + ' is out')
    // childrenQueue.dequeue()
  }
  console.log(childrenQueue.dequeue() + ' is winner')
}

hotPotato(['lili', 'aki', 'xiao', 'long', 'yuw', 'ray', 'wiess'])