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