优先级队列

约 153 字小于 1 分钟

2023-11-23

介绍

大致结构与队列结构类似，但是优先级队列会多出一个优先级，每个元素就不止携带了他的值，还有他的优先级，在插入之后会与其他数据的优先级进行比较，然后放到队列中正确的位置上。

比如多线程操作的时候，有一些线程需要优先处理，就可以用来决定线程处理的次序。

TS 实现

class ProiorityQueueElement {
  #value: any
  #priority: number

  constructor(value: any, priority: number) {
    this.#value = value
    this.#priority = priority
  }

  getValue() {
    return this.#value
  }

  getPriority() {
    return this.#priority
  }
}

class ProiorityQueue {
  #value: ProiorityQueueElement[] = []

  enqueue(value: any, priority: number) {
    const newElement = new ProiorityQueueElement(value, priority)

    if (this.#value.length !== 0) {
      for (let i = 0; i < this.#value.length; i++) {
        if (this.#value[i].getPriority() > newElement.getPriority()) {
          this.#value.splice(i, 0, newElement)
          return newElement
        }
      }
    }

    this.#value.push(newElement)

    return newElement
  }

  dequeue() {
    return this.#value.shift()
  }

  front() {
    return this.#value[0]
  }

  isEmpty() {
    return this.#value.length === 0
  }

  size() {
    return this.#value.length
  }

  toString() {
    return JSON.stringify(this.#value)
  }
}