队列

队列

队列数据结构

队列是遵循FIFO (First In First Out, 先进先出, 也称先来先服务) 原则的一组有序的项. 队列在尾部添加新元素, 并从顶部移除元素. 最新添加的元素必须排在队列的末尾.

现实中,最常见的队列的例子就是排队:

在计算机科学中, 一个常见的例子就是打印队列.

创建队列

创建一个类来表示一个队列.

function Queue() {
  // 这里是属性和方法
}

首先需要一个用于存储队列中元素的数据结构. 可以使用数组, 就像上一章Stack类中那种使用.

let items = []

队列方法

• enqueue(element(s)) : 向队列尾部添加一个(或多个)新的项
• dequeue() : 移除队列的第一(即排在队列最前面的)项目, 并返回被移除的元素
• front() : 返回队列中第一个元素 -- 最先被添加,也将是最先被移除的元素. 队列不做任何变动(不移除元素,只返回元素信息 -- 与 Stack 类的 peek 方法类似)
• isEmpty() : 如果队列不包含任何元素, 返回 true, 否则返回 false.
• size(): 返回队列包含的元素个数, 与数组的length属性类似

向队列添加元素

enqueue 方法负责向队列添加新元素. 新的项只能添加到队列末尾

this.enqueue = function (element) {
  items.push(element)
}

从队列移除元素

dequeue 方法负责从队列移除项. 由于队列遵循先进先出原则, 最先添加的项也是最先被移除的. shift 方法会从数组中移除存储在索引0(第一个位置)的元素

this.dequeue = function () {
  return items.shift()
}

查看队列头元素

front 方法返回队列最前面的项(数组的索引为0)

this.front = function () {
  return items[0]
}

检查队列是否为空

isEmpty 方法. 如果队列为空, 返回 true, 否则返回 false

this.isEmpty = function () {
  return items.length == 0
}

size 方法获取队列的元素个数

this.size = function () {
  return items.length
}

打印队列元素

print 方法实现打印

this.print = function () {
  console.log(items.toString())
}

使用

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.print = function () {
    console.log(items.toString())
  }
}

// use Queue 
let queue = new Queue()
console.log(queue.isEmpty()) // true

// add item
queue.enqueue('John')
queue.enqueue('Jack')
queue.enqueue('Camila')

queue.print() // John,Jack,Camila

console.log(queue.size()) // 3
console.log(queue.isEmpty()) // false

queue.dequeue()
queue.print() // Jack,Camila
queue.dequeue()
queue.print() // Camila

用 ES6 语法实现 Queue 类

用 WeakMap 保存私有属性 itmes, 用外层函数(闭包)来封装Queue类

let Queue2 = (function () {
  const items = new WeakMap()

  class Queue2 {
    constructor() {
      items.set(this, [])
    }
    enqueue(element) {
      let q = items.get(this)
      q.push(element)
    }
    dequeue() {
      let q = items.get(this)
      let r = q.shift()
      return r
    }
    front() {
      return items.get(this)[0]
    }
    isEmpty() {
      return items.get(this).length == 0
    }
    size() {
      return items.get(this).length
    }
    print() {
      console.log(items.get(this).toString())
    }
  }
  return Queue2
})()


// use Queue2 
let queue = new Queue2()
console.log(queue.isEmpty()) // true

// add item
queue.enqueue('John')
queue.enqueue('Jack')
queue.enqueue('Camila')

queue.print() // John,Jack,Camila

console.log(queue.size()) // 3
console.log(queue.isEmpty()) // false

queue.dequeue()
queue.print() // Jack,Camila
queue.dequeue()
queue.print() // Camila

优先队列

队列应用修改版一, 优先队列. 元素的添加和移除是基于优先级的.一个现实的例子就是机场登机的顺序.头等舱和商务舱登机的优先级要高于经济舱.在有些国家,老年人和孕妇登机时也享有高于其他乘客的优先级.

另一个现实例子是医院的(急诊室)候诊室. 医生会优先处理病情比较严重的患者. 通常, 护士会鉴别分类, 根据患者病情的严重程度放号.

实现一个优先队列, 有两种选项: 设置优先级, 然后在正确的位置添加元素; 或用入列操作添加元素, 然后按照优先级移除他们. 在这个示例中, 我们将会在正确的位置添加元素, 因此可以对它们使用默认的出列操作:

function PriorityQueue() {
  let items = []
  function QueueElement(element, priority) { // {1}
    this.element = element
    this.priority = priority
  }

  this.enqueue = function(element, priority) {
    let queueElement = new QueueElement(element, priority)

    let added = false
    for (let i = 0; i < items.length; i++) {
      if (queueElement.priority < items[i].priority) { // {2}
        items.splice(i, 0, queueElement); // {3}
        added = true
        break
      }
    }
    if (!added) {
      items.push(queueElement)
    }
  }

  this.print = function() {
    for (let i = 0; i < items.length; i++) {
      console.log(`${items[i].element} - 
      ${items[i].priority}`)
    }
    console.log(JSON.stringify(items))
  }

  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
  }
}

默认 Queue 类和 PriorityQueue 类实现上的区别是, 要向 PrioriryQueue 添加元素,需要创建一个特殊的元素(行{1}). 这个元素包含了要添加到队列的元素(它可以是任意类型)及其在队列中的优先级.

如果队列为空, 可以直接将元素入列(行{2}). 否则, 就需要比较该元素与其他元素的优先级. 当找到一个比要添加的元素的 priority 值更大(优先级更低)的项时, 就把新元素插入到它之前(根据这个逻辑, 对于其他优先级相同, 但是先添加到队列的元素, 同样遵循先进先出的原则). 要做到这一点, 可以使用 array 类的 splice 方法. 一旦找到 priority 值更大的元素, 就插入新元素(行{3})并终止队列循环(行{4}). 这样, 队列也就根据优先级排序了.

如果要添加元素的 priority 值大于任何已有的元素, 就把它添加到队列的末尾就行了(行{5}):

let priorityQueue = new PriorityQueue()
priorityQueue.enqueue('John', 2)
priorityQueue.print() // [{"element":"John","priority":2}]
priorityQueue.enqueue('Jack', 1)
priorityQueue.print() // [{"element":"Jack","priority":1},{"element":"John","priority":2}]
priorityQueue.enqueue('Camila', 1)
priorityQueue.print() // [{"element":"Jack","priority":1},{"element":"Camila","priority":1},{"element":"John","priority":2}]

这里实现的是优先队列为最小优先队列, 因为优先级的值较小的元素放置在队列最前面(1代表优先级更高的优先级). 最大优先队列与之相反, 把优先级的值较大的元素放置在队列最前面.

循环队列 -- 击鼓传花

循环队列的一个例子就是击鼓传花游戏(Hot Potato). 在这个游戏中, 孩子们围成一圈, 把花尽快地传递给旁边的人. 某一时刻传花停止, 这个时候花在谁手里, 谁就退出圆圈结束游侠. 重复这个过程, 直到只剩一个孩子(胜者).

下面示例, 模拟击鼓传花游戏:

function hotPotato (nameList, num) {
  let queue = new Queue() // {1}
  for (let i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i]) // {2}
  }

  let eliminated = ''
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue()) // {3}
    }
    eliminated = queue.dequeue() // {4}
    console.log(eliminated + ' 在击鼓传花游戏中被淘汰. ')
  }
  return queue.dequeue() // {5}
}

let names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl']
let winner = hotPotato(names, 7)
console.log('The winner is: ' + winner)

实现一个模拟的击鼓传花游戏, 要用到 Queue 类(行{1}). 会得到一份名单, 把里面的名字全部都加入到队列(行{2}). 给定一个数字, 然后迭代队列. 从队列开头移除一项, 再将其添加到队列末尾(行{3}), 模拟击鼓传花(如果你把花传递给旁边的人, 你被淘汰的威胁就立刻解除了). 一旦传递次数达到指定的数字, 拿个着花的那个人就被淘汰了(从队列中移除-行{4}).最后只剩下一个人的时候,这个人就是胜者(行{5}).

以上算法的输出如下:

Camila在击鼓传花游戏中被淘汰.
Jack在击鼓传花游戏中被淘汰.
Carl在击鼓传花游戏中被淘汰.
Ingrid在击鼓传花游戏中被淘汰.
胜利者: John

可以改变传入 hotPotato 函数的数字,模拟不同的场景

JavaScript 任务队列

当我们在浏览器中打开标签的时候,就会创建一个任务队列. 这是因为每个标签都是单线程处理的所有的任务, 它被称为事件循环. 浏览器要负责多个任务, 如渲染HTML, 执行 JavaScript 代码, 处理用户交互(用户输入, 鼠标点击等). 执行和处理异步请求.