es6-algorithm 之 Queue和应用

Queue的概念

我们知道队列是一种常用的先进先出（FIFO）的有序集合。队列的实际应用其实非常广泛。比如排队，event loop里的事件队列，优先队列，循环队列，操作系统中也大量运用队列。废话不多说，看看实现。

Queue队列的实现

首先创建Queue, Queue一般有 enqueue(队列尾部插入一条数据)，dequeue（删除队列第一条数据，也就是最先进来的那条）， front(获取队列第一条数据)，size (队列的长度)，isEmpty（判断队列是否空），print（打印整个队列信息）等方法。基本结构如下。

const Queue = (() => {
  const wp = new WeakMap()
  class Queue {
    constructor () {
      wp.set(this, [])
    }

    enqueue (ele) {
      wp.get(this).push(ele)
    }
    dequeue () {
      return wp.get(this).shift()
    }
    front () {
      return wp.get(this)[0]
    }
    isEmpty () {
      return wp.get(this).length === 0
    }
    size () {
      return wp.get(this).length
    }
    print () {
      return wp.get(this).toString()
    }
  }

  return Queue
})()

具体使用如下：

let q = new Queue()

q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)

q.dequeue()

console.log(q.print())

结果应该是： 2，3，4

循环队列-击鼓传花游戏

游戏规则就是，n个孩子围成一个圆圈，把花尽快的传给旁边的人。某个时刻传花截至，这个时候花在谁手上，谁就退出圆圈结束游戏。重复这个过程，直到只剩下一个孩子（胜者）。
利用上面创建的Queue class，实现如下:

function flower (arr, num) {
  let que = new Queue()

  for (let i = 0; i < arr.length; i++) {
    que.enqueue(arr[i])
  }
  let name = ''
  while (que.size() > 1) {
    for (let i = 0; i < num; i++) {
      que.enqueue(que.dequeue())
    }
    name = que.dequeue()
    console.log(name + '  get out')
  }
  console.log(que.dequeue() + '  win')
}
let arr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']

flower(arr, 8)

最后h胜出，结果如下：

i  get out
a  get out
c  get out
f  get out
d  get out
e  get out
b  get out
g  get out
h  win

以上..