优先级队列（PriorityQueue）

1. 是什么?

优先队列也是一种抽象数据类型。与普通队列比较，优先队列中的每个元素都有优先级，而优先级高的将会先出队，而优先级相同的则按照其在优先队列中的顺序依次出队

2. 优先级队列的应用场景

• js 中的异步队列分为宏任务与微任务, 微任务的优先级总是高于宏任务

3. 优先级队列的实现

基于数组实现

封装示例

// 用于生成队列元素
class Ele {
  constructor(data, priority) {
    this.data = data;
    this.priority = priority;
  }
}

// 优先级队列
class PriorityQueue {
  constructor(priQueue = []) {
    this.source = priQueue;
  }

  get size() {
    return this.source.length;
  }

  get isEmpty() {
    return this.size <= 0;
  }

  get front() {
    let ele = this.source[0];
    return ele && ele.data;
  }

  // 插入元素
  enqueue(data, priovity) {
    let ele = new Ele(data, priovity);
    let inserted = false;
    this.source.forEach((item, index) => {
      if (ele.priority < item.priority) {
        this.source.splice(index, 0, ele);
        inserted = true;
      }
    });

    if (!inserted) {
      this.source.push(ele);
      inserted = true;
    }
  }

  // 取出元素
  dequeue() {
    let ele = this.source.shift();
    return ele.data;
  }
}

使用示例

/* **************使用************** */

let proocityQueue = new PriorityQueue();

proocityQueue.enqueue("A", 4);
proocityQueue.enqueue("C", 1);
proocityQueue.enqueue("S", 9);
proocityQueue.enqueue("E", 4);

console.log(proocityQueue);
/* 
PriorityQueue {
  source: [
    Ele { data: 'C', priority: 1 },
    Ele { data: 'A', priority: 4 },
    Ele { data: 'E', priority: 4 },
    Ele { data: 'S', priority: 9 }
  ]
}

*/

console.log(proocityQueue.front); // C
console.log(proocityQueue.size); // 4
console.log(proocityQueue.isEmpty); // false
console.log(proocityQueue.dequeue()); // C
console.log(proocityQueue);
/* 
PriorityQueue {
  source: [
    Ele { data: 'A', priority: 4 },
    Ele { data: 'E', priority: 4 },
    Ele { data: 'S', priority: 9 }
  ]
}
*/