5.JavaScript 数据结构与算法（五）优先队列

[webVueBlog]

场景

生活中类似优先队列的场景：

• 优先排队的人，优先处理。 (买票、结账、WC)。
• 排队中，有紧急情况（特殊情况）的人可优先处理。

优先队列

优先级队列主要考虑的问题：

• 每个元素不再只是一个数据，还包含优先级。
• 在添加元素过程中，根据优先级放入到正确位置。

优先队列的实现

代码实现

class QueueElement {
 constructor(element, priority) {
 this.element = element
 this.priority = priority
 }
}

// 优先队列类
export class PriorityQueue extends Queue {
 constructor() {
 super();
 }
 
 // enqueue(element, priority) 入队，将元素按优先级加入到队列中
 enqueue(element, priority) {
 // 根据传入的元素，创建 QueueElement 对象
 const queueElement = new QueueElement(element, priority);
 // 判断队列是否为空
 if (this.isEmpty()) {
 // 如果为空，不用判断优先级，直接添加
 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() 出队
 dequeue() {
 return super.dequeue()
 }
 front() {
 return super.front()
 }
 isEmpty() {
 return super.isEmpty()
 }
 size() {
 return super.size()
 }
 toString() {
 let result = ''
 for (let item of this.items) {
 result += item.element + '-' + item.priority + ' '
 }
 return result
 }
}