coolliyong.github.io

队列

维基百科定义：

队列，又称为伫列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为 rear）进行插入操作，在前端（称为 front）进行删除操作。
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

• 举个例子：常见的队列，排队就是队列，先到先得，后来后得（优先队列例外）
• 先进先出（FIFO first in first out）

队列的模拟实现

function Queue() {
  this.list = []
}

Queue.prototype.enqueue = function(element) {
  this.list.push(element)
}

Queue.prototype.dequeue = function() {
  return this.list.shift()
}

Queue.prototype.front = function() {
  return this.list[0]
}

Queue.prototype.isEmpty = function() {
  return this.list.length <= 0
}

Queue.prototype.size = function() {
  return this.list.length
}

Queue.prototype.toString = function() {
  return this.list.join(' ')
}

队列算法题 击鼓传花

有一些人，围成一个圈，循环报数，成为第 N 个的人出列，依次继续，直到剩下最后一个人为胜利

function arithmeticQueue(names = [], num = 3) {
  const q = new Queue()
  names.forEach(v => q.enqueue(v))

  let idx = 0
  while (q.size() > 1) {
    // 出列的人回到后面，为一圈
    if (idx === num) {
      // 删掉第N个人
      q.dequeue()
      idx = 0
    }
    q.enqueue(q.dequeue())
    idx++
  }
  // 最后的赢家
  return q.front()
}

优先队列

维基百科定义：

优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。
普通的队列只有一个 value 值，但是优先队列有一个优先级的概念,是一个有序的队列