优先级队列

huan_kong

154字小于1分钟

2023-11-23

介绍

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

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

TS实现

namespace 优先级队列 {
  class element {
    value: any
    priority: number
    constructor(value: any, priority: number) {
      this.value = value
      this.priority = priority
    }
  }

  class proiorityQueue {
    #value: element[] = []

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

      if (this.#value.length !== 0) {
        for (let i = 0; i < this.#value.length; i++) {
          if (this.#value[i].priority > newElement.priority) {
            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)
    }
  }
}