内容大纲

优先级队列

huan_kong

154字小于1分钟

2023-11-23

介绍

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

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

TS实现

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)
  }
}