队列

基本概念

队列是一种先进先出（FIFO，First In First Out）的数据结构。只用 push 和 shift 完成增删的“数组”。

很好理解，就跟银行排队一样，先排的人先办业务。

JS实现队列

Class Queue {
    constructor() {
        this.queue = []    
    }
    enqueue(item) {
        this.queue.push(item)    
    }
    dequeue() {
        return this.queue.shift()    
    }
    head() {
        return  this.queue[0] 
    }
    isEmpty(){
        return this.size() === 0    
    }
    size(){
        return this.queue.length    
    }
}

优先队列

优先队列是默认队列的变种，它的元素的添加和移除是基于优先级的。一个现实的例子就是医院的（急诊科）候诊室。医生会优先处理病情比较严重的患者。

实现一个优先队列，有两种选择：

• 设置优先级，然后在正确的位置添加元素；
• 用默认入列操作添加元素，按照优先级移除它们。

class QueueItem {
  constructor(item, priority) {
    this.item = item
    this.priority = priority
  }
}

class PriorityQueue {
  constructor() {
    this.queue = []
  }

  enqueue(item, priority) {
    const qItem = new QueueItem(item, priority)
    if (this.isEmpty()) {
      this.queue.push(qItem)
    } else {
      let added = false
      for (let i = 0; i < this.queue.length; i++) {
        if (priority < this.queue[i].priority) {
          this.queue.splice(i, 0, qItem) //在index:i的位置插入
          added = true
          break
        }
      }
      if (!added) {
        this.queue.push(qItem)
      }
    }
  }

  dequeue() {
    return this.queue.shift()
  }

  head() {
    return this.queue[0]
  }

  isEmpty() {
    return this.size() === 0
  }

  size() {
    return this.queue.length
  }

  print() {
    return this.queue.map(q => q.item)
  }
}

var queue = new PriorityQueue()
console.log(queue.isEmpty()) // 输出 true
queue.enqueue('a', 4)           // 添加元素 a
queue.enqueue('b', 2)           // 添加元素 b
queue.enqueue('c', 1)           // 添加元素 c
queue.enqueue('d', 1)           // 添加元素 d
console.log(queue.print())        // 输出 ['c','d','b','a']

循环队列

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。

但是使用循环队列，我们能使用这些空间去存储新的值。

因为单链队列在出队操作的时候需要 O(n) 的时间复杂度，所以引入了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度。

典型的应用就是击鼓传花与约瑟夫环问题。

class Queue {
  constructor() {
    this.queue = []
  }

  enqueue(item) {
    this.queue.push(item)
  }

  dequeue() {
    return this.queue.shift()
  }

  head() {
    return this.queue[0]
  }

  isEmpty() {
    return this.size() === 0
  }

  size() {
    return this.queue.length
  }
}

function flowerDrumTransfer(nodeList, counter) {
  const queue = new Queue()
  for (let i = 0; i < nodeList.length; i++) {
    queue.enqueue(nodeList[i])
  }

  let target = ''
  while (queue.size() > 1) {
    for (let j = 0; j < counter; j++) {
      queue.enqueue(queue.dequeue())
    }
    target = queue.dequeue() //该轮中被淘汰出局的
  }
  return queue.dequeue()
}

const arr = ['a', 'b', 'c', 'd', 'e']
const winner = flowerDrumTransfer(arr, 7)
console.log(winner)