数据结构与算法-队列
# 数据结构与算法-队列
# 认识队列
队列(Queue)，它是一种运算受限的线性表
- 特点是先进先出
FIFO (First In First Out) - 受限之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作
如下图所示
生活中也常见队列结构，如排队，比如在电影院，商场，厕所排队。优先排队的人，优先处理。
程序中的队列应用
- 打印队列:
- 有五份文档需要打印，这些文档会按照次序放入到打印队列中
- 打印机会依次从队列中取出文档，优先放入的文档，优先被取出，并且对该文档进行打印
- 以此类推，直到队列中不再有新的文档
- 线程队列:
- 在进行多线程开发时，我们不可能无限制的开启新的线程
- 这个时候，如果有需要开启线程处理任务的情况，我们就会使用线程队列
- 线程队列会依照次序来启动线程，并且处理对应的任务
# 队列的实现
队列的实现和栈一样，有两种方法，基于数组实现和基于链表实现。基于链表实现的效率会更高。
我们线基于数组来实现队列，对数组做一层包装，让它外层具有队列的特性，内部本质上还是数组。
队列中常见的方法可总结如下：
enqueue(element)：向队列尾部添加一个（或多个）新的项。dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）。isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。size()：返回队列包含的元素个数，与数组的length属性类似。toString()：将队列结构的内容以字符串形式返回。
代码如下：
/**
* 队列 基于数组
*/
module.exports = class Queue {
constructor () {
// 队列中所有元素存储
this.items = []
}
// 从队列尾部添加一个新元素到队列中
enqueue (element) {
this.items.push(element)
}
// 从队列头部移除一个元素 返回移除元素
dequeue () {
return this.items.shift()
}
// 查看队列前端的第一个元素
front () {
return this.items[0]
}
// 查看队列是否为空
isEmpty () {
return this.items.length === 0
}
// 查看队列中元素个数
size () {
return this.items.length
}
// 以字符串形式返回队列内元素数据
toString() {
let result = ''
for (let item of this.items) {
result += item + ' '
}
return result
}
}
测试：
const queue = new Queue()
// enqueue
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.enqueue('d')
console.log('enqueue', queue.items) // enqueue [ 'a', 'b', 'c', 'd' ]
// dequeue
console.log('dequeue', queue.dequeue()) // dequeue a
console.log('dequeue', queue.dequeue()) // dequeue b
console.log(queue.items) // [ 'c', 'd' ]
// front
console.log('front', queue.front()) // front c
// isEmpty
console.log('isEmpty', queue.isEmpty()) // isEmpty false
// size
console.log('size', queue.size()) // size 2
// toString
console.log('toString', queue.toString()) // toString c d
# 练习 — 击鼓传花
游戏规则:
- 班级中玩一个游戏, 所有学生围成一圈, 从某位同学手里开始向旁边的同学传一束花。
- 这个时候某个人(比如班长)，在击鼓，鼓声停下的一颗，花落在谁手里，谁就出来表演节目。
修改游戏规则：
- 几个朋友一起玩一个游戏，围成一圈，从1开始数数，数到某个数字的人自动淘汰。
- 最后剩下的这个人会获得胜利，请问最后剩下的是原来在哪一个位置上的人？
分析：传入一组数据集合和设定的数字 number，循环遍历数组内元素，遍历到的元素为指定数字 number 时将该元素删除，直至数组剩下一个元素。
代码实现如下：
const Queue = require('../../lib/Queue')
/**
* 数到num的人被淘汰，最终剩下的一人获胜
* @param {*} nameList
* @param {*} num
* @returns
*/
function game (nameList, num) {
const queue = new Queue()
// 将所有人放入队列
for (let i = 0; i < nameList.length; i++) {
queue.enqueue(nameList[i])
}
while (queue.size() > 1) {
for (let i = 1; i < num; i++) { // 从1开始数
// 小于num 即 没有数到num的人从队列中取出再放入队列
queue.enqueue(queue.dequeue())
}
// 此时数num的人在队列最前端 将数num的人，从队列中移除
queue.dequeue()
}
return nameList.indexOf(queue.front())
}
// 数到8的人被淘汰
console.log(game(['John', 'Jack', 'Camila', 'Ingrid', 'Carl'], 8)) // 0 即 John获胜
上面的过程如下图所示
# 优先级队列
优先级队列的特点：
- 普通的队列插入一个元素，数据会被放在后端。并且需要前面所有的元素都处理完成后才会处理前面的数据。
- 但是优先级队列，在插入一个元素的时候会考虑该数据的优先级，即和其他数据优先级进行比较
- 比较完成后，可以得出这个元素正确的队列中的位置。其他处理方式，和队列的处理方式一样。
- 也就是说，如果我们要实现优先级队列，最主要是要修改添加方法。当然，还需要以某种方式来保存元素的优先级
优先级队列应用也非常广泛
生活中的一个例子是机场登机的顺序，头等舱和商务舱乘客的优先级要高于经济舱乘客。
另一个现实中的例子是医院的（急诊科）候诊室，医生会优先处理病情比较严重的患者。通常，护士会鉴别分类，根据患者病情的严重程度放号。
计算机中，我们也可以通过优先级队列来重新排序队列中任务的顺序，比如每个线程处理的任务重要性不同，我们可以通过优先级的大小，来决定该线程在队列中被处理的次序。
# 优先级队列实现
实现优先级队列相对队列主要有两方面需要考虑：
- 封装元素和优先级放在一起
- 添加元素时，将当前的优先级和队列中已经存在的元素优先级进行比较，以获得自己正确的位置。
我们这里认为，数字越小，优先级越高。实现如下：
// 优先队列内部的元素类
class QueueElement {
constructor(element, priority) {
this.element = element;
this.priority = priority;
}
}
/**
* 优先队列 基于数组
*/
module.exports = class PriorityQueue {
constructor () {
// 队列中所有元素存储
this.items = []
}
// 从队列尾部添加一个新元素到队列中
enqueue (element, priority) {
const queueElement = new QueueElement(element, priority)
if (!this.items.length) {
this.items.push(queueElement)
} else {
let added = false
for (let i = 0; i < this.items.length; i++) {
// priority越小则优先级越高
if (queueElement.priority < this.items[i].priority) {
// 插入到下一优先级最前面 即 同一优先级的末尾
this.items.splice(i, 0, queueElement)
added = true
break
}
}
if (!added) {
// 遍历完所有的元素, 优先级都大于新插入的元素时, 插入到最后
this.items.push(queueElement)
}
}
}
// 从队列头部移除一个元素 返回移除元素
dequeue () {
return this.items.shift()
}
// 查看队列前端的第一个元素
front () {
return this.items[0]
}
// 查看队列是否为空
isEmpty () {
return this.items.length === 0
}
// 查看队列中元素个数
size () {
return this.items.length
}
// 以字符串形式返回队列内元素数据
toString() {
let result = '';
for (let item of this.items) {
result += item.element + '-' + item.priority + ' ';
}
return result;
}
}
封装了一个QueueElement, 将element和priority封装在一起。
在插入新的元素时，有如下情况下考虑:
- 根据新的元素先创建一个新的QueueElement对象。
- 如果元素是第一个被加进来的，那么直接加入数组中即可。
- 如果是后面加进来的元素，需要和前面加进来的元素依次对比优先级。
- 一旦优先级，大于某个元素，就将该元素插入到元素这个元素的位置。其他元素会依次向后移动。同一优先级的，后添加的在最后。
- 如果遍历了所有的元素，没有找到某个元素被这个新元素的优先级低，直接放在最后即可。
测试如下：
const priorityQueue = new PriorityQueue();
// enqueue
priorityQueue.enqueue('A', 10);
priorityQueue.enqueue('B', 15);
priorityQueue.enqueue('C', 11);
priorityQueue.enqueue('D', 20);
priorityQueue.enqueue('E', 18);
priorityQueue.enqueue('F', 10);
console.log('enqueue', priorityQueue.items);
// enqueue [
// QueueElement { element: 'A', priority: 10 },
// QueueElement { element: 'F', priority: 10 },
// QueueElement { element: 'C', priority: 11 },
// QueueElement { element: 'B', priority: 15 },
// QueueElement { element: 'E', priority: 18 },
// QueueElement { element: 'D', priority: 20 }
// ]
// dequeue
console.log('dequeue', priorityQueue.dequeue()) // dequeue QueueElement { element: 'A', priority: 10 }
console.log('dequeue', priorityQueue.dequeue()) // dequeue QueueElement { element: 'F', priority: 10 }
console.log('dequeue', priorityQueue.items);
// dequeue [
// QueueElement { element: 'C', priority: 11 },
// QueueElement { element: 'B', priority: 15 },
// QueueElement { element: 'E', priority: 18 },
// QueueElement { element: 'D', priority: 20 }
// ]
// isEmpty
console.log('isEmpty', priorityQueue.isEmpty()); // isEmpty false
// size
console.log('size', priorityQueue.size()); // size 4
// toString
console.log('toString', priorityQueue.toString()); // toString C-11 B-15 E-18 D-20
编辑 (opens new window)
上次更新: 2021/12/16, 17:17:31