队列

队列是一种先进先出（First-In-First-Out，FIFO）的数据结构。可以联想一下小朋友排队打疫苗， 排在前头的先打， 排在后边的后打。打完疫苗的朋友就可以回家了（出队），刚到的朋友需要排队（入队）。

1. 实现队列

class Queue {
  constructor(store = []) {
    this.store = store
  }
  // 入队
  enqueue(...args) {
    this.store.push(...args)
  }
  // 出队
  dequeue() {
    return this.store.shift()
  }
  // 队首元素
  head() {
    return this.store[0]
  }
  // 队尾元素
  tail() {
    return this.store[this.size() - 1]
  }
  // 元素个数
  size() {
    return this.store.length
  }
  // 元素是否为空
  isEmpty() {
    return this.size() === 0
  }
  // 清空
  clear() {
    this.store = []
  }
}

2.1 优先队列

优先队列元素的添加和移除是基于优先级的。元素入队时不是依次入队， 而是根据优先级进行排序入队， 优先级高的元素永远排在优先级低的元素之前，并且比优先级低的元素先出队。这个可以联想登机时分为头等舱、经济舱的场景， 头等舱的乘客享有优先登机的服务。

/**
 * 元素类， 每个元素包含优先级和元素值
 */
class QueueElement {
  constructor(element, priority) {
    this.element = element
    this.priority = priority
  }
}
/**
 * 优先队列， 只需要重写父类的入队函数即可
 * 别的方法可以直接继承自 Queue
 */
class PriorQueue extends Queue {
  constructor(store) {
    super(store)
  }
  /**
   * 入队
   * 1. 若队列为空， 则直接入队
   * 2. 否则， 查找队列中优先级比入队元素优先级低的元素
   *  2.1 若存在， 则入队位置为该元素的索引， 该索引后边的元素依次向后移动一个位置
   *  2.2 若不存在， 则入队元素的优先级最低， 入队位置为队列末尾
   */
  enqueue(element, priority) {
    const insertedElement = new QueueElement(element, priority)
    if (this.isEmpty()) {
      this.store.push(insertedElement)
    } else {
      let isEnqueue = false
      for (let i = 0; i < this.size(); i++) {
        const currentElement = this.store[i]
        if (insertedElement.priority < currentElement.priority) {
          this.store.splice(i, 0, insertedElement)
          isEnqueue = true
          return
        }
      }
      // 若未找到优先级比入队元素大的元素, 说明入队元素的优先级最低
      if (!isEnqueue) {
        this.store.push(insertedElement)
      }

    }
  }
}

// 简单测试
const qp = new PriorQueue([
  new QueueElement('zeus', 1),
  new QueueElement('zeus', 2),
])
qp.enqueue('luna', 4)
qp.enqueue('coco', 5)
qp.enqueue('snk', 20)
qp.enqueue('loa', 4)
qp.enqueue('sv', 9)
qp.enqueue('am', 4)
qp.enqueue('es', 8)
qp.enqueue('sk', 9)
qp.enqueue('qop', 8)
console.log(qp);

console.log(qp.dequeue())
console.log(qp);

2.2 实现优先队列（设定优先级用自然数表示， 数字越小，则优先级越高）

有限队列入队时， 有几种情况：

1. 如果优先队列为空队列， 则直接入队
2. 否则的话将元素插入到第一个比其优先级低的元素前面

队列应用1, 循环队列， 击鼓传花

// 击鼓传花
const runPassFlower = nameList => {
  // 击鼓函数, 生成一个小于 10 的随机整数 N
  // 表示传递 N 次后， 击鼓一次
  const hitDrum = ()=> {
    return Math.floor(Math.random() * 10)
  }

  const q = new Queue(nameList)
  while (q.size() > 1) {
    const drumPlot = hitDrum()
    for(let i = 0; i< drumPlot; i++) {
      q.enqueue(q.dequeue())
    }
    const loser = q.dequeue()
    console.log(`${loser} \出局了`)
  }

  return q.head()

}

const nameList = ['张三','李四','王五','赵六','周七','吴八','郑九','钱十','萧十一','郭十二','管十三',]
console.log(`~~~~ ${runPassFlower(nameList)} 胜出！ ~~~~`)