目 录CONTENT

文章目录

队列之-优先级队列

Hello!你好!我是村望~!
2023-01-11 / 0 评论 / 0 点赞 / 862 阅读 / 881 字
温馨提示:
我不想探寻任何东西的意义,我只享受当下思考的快乐~

队列之-优先级队列

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

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

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

// 队列 代码
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 }
  ]
}

*/

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

0

评论区