队列之-优先级队列

普通的队列具有先进先出的特性，元素追加在队尾，如果删除的话，从队头删除。

而在优先队列中，队列中的数据被赋予了优先级。当访问元素时，优先级最高的会先被删除。所以说优先队列是最高级数据先出。

那么实现优先级队列，我们就基于之前的队列实现就可以了！

// 队列 代码
export interface Iqueue<T> {
  items: T[]; // 顺序队列 底层一样基于数组实现！
  enQueue(ele: T): T[]; // 入队
  deQueue(): T; // 出队
  toString(): string; // 队列字符串化
  size(): number; // 队列长度
  front(): T; // 排在队伍最前面的元素
}

export default class Queue<T> implements Iqueue<T> {
  items: T[] = [];

  enQueue(ele: T): T[] {
    this.items.unshift(ele);
    return this.items;
  }
  deQueue(): T {
    return this.items.pop() as T;
  }
  size(): number {
    return this.items.length;
  }
  toString(): string {
    return this.items.toString();
  }
  front(): T {
    return this.items[0];
  }
}

那么根据优先级队列的特点~ 我们只需要在插入元素的时候，对元素的优先级进行判断就可以了！其他的操作是和普通的队列一样的，你把优先级高的放到队列的最前方！那么出队列的时候，按照普通的队列出就行了！一样是按照优先级进出的！

这里我们定义一个优先级元素的类！用于创建优先级元素实例！

当使用优先级队列的时候，优先级队列只能推入优先级元素

interface IPriorityElement<T> {
  /**
   *  队列元素数据
   */
  data: T;
  /**
   * 队列元素优先级 规定是一个数字 数字越小， 优先级越高
   */
  priority: number;
}

export class PriorityElement<T> implements IPriorityElement<T> {
  data: T;
  priority: number;

  constructor(data: T, priority: number) {
    this.data = data;
    this.priority = priority;
  }
}

然后我们实现优先级队列的类，除了插入队列 enQueue 的方法外，大部分都方法都与普通队列相同，我们就只需要继承普通的队列类，然后重写 enQueue 方法就可以了！

export default class PriorityQueue<T> extends Queue<PriorityElement<T>> {
  enQueue(ele: PriorityElement<T>): PriorityElement<T>[] {
    // 如果队列为空，直接放入！
    if (this.size() === 0) {
      this.items.push(ele);
      return this.items;
    }
    let lessThanFlag = false; // 2.代表是否能在原队列中找到一个比自己小的！
    
    for (let i = 0; i < this.size(); i++) {
      if (this.items[i].priority <= ele.priority) {
        // 2.1 如果找到了 优先级比插入元素更小的比如 x！[...,x...] 那么就把新的ele放在x前面！ [...ele,x,...]
        this.items.splice(i, 0, ele);
        // 2.2 然后修改标识符变量，表示队列中能找到一个优先级比新进来的元素更高的！
        lessThanFlag = true;
        // 2.3 这里我们就可以跳出循环了！
        break;
      }
    }
    // 3.如果上面循环结束没有找到，比自己Priority小的，那么证明新进来的元素优先级是最高的，直接放在队首~
    if (!lessThanFlag) {
      this.items.push(ele);
    }
    return this.items;
  }
}

测试一下：

const n0 = new PriorityElement(1, 4);
const n1 = new PriorityElement(1, 9);
const n2 = new PriorityElement(2, 2);
const n3 = new PriorityElement(2, 5);
const n4 = new PriorityElement(3, 3);
// [4]
const pe = new PriorityQueue<number>();

pe.enQueue(n0);
pe.enQueue(n1);
pe.enQueue(n2);
pe.enQueue(n3);
pe.enQueue(n4);
console.log(pe); 

/*

PriorityQueue {
  items: [
    PriorityElement { data: 1, priority: 9 },
    PriorityElement { data: 2, priority: 5 },
    PriorityElement { data: 1, priority: 4 },
    PriorityElement { data: 3, priority: 3 },
    PriorityElement { data: 2, priority: 2 }
  ]
}

*/

这样就完成了我们的优先级队列了！