双端、优先级队列

实现双端队列

队列(Queue) 结构，它是一种受限的线性结构，并且限制非常的严格

双端队列在单向队列的基础上解除了一部分限制: 允许在队列的两端添加（入队）和删除（出队）元素

• 因为解除了一部分限制，所以在解决一些特定问题时会更加的方便
• 比如滑动窗口问题: https://leetcode.cn/problems/sliding-window-maximum/description/

继承自之前的队列结构

class ArrayDeque<T> extends ArrayQueue<T> {
  addFront(value: T) {
    this.data.unshift(value)
  }
  removeBack(): T | undefined {
    return this.data.pop()
  }
}

实现优先级队列

优先级队列（Priority Queue）是一种比普通队列更加高效的数据结构

• 它每次出队的元素都是具有最高优先级的，可以理解为元素按照关键字进行排序
• 优先级队列可以用数组、链表等数据结构来实现，但是堆是最常用的实现方式

优先级队列的应用

• 一个现实的例子就是机场登机的顺序
  • 头等舱和商务舱乘客的优先级要高于经济舱乘客
  • 在有些国家，老年人和孕妇(或带小孩的妇女)登机时也享有高于其他乘客的优先级
• 另一个现实中的例子是医院的 (急诊科) 候诊室
  • 医生会优先处理病情比较严重的患者
  • 当然，一般情况下是按照排号的顺序
• 计算机中，我们也可以通过优先级队列来重新排序队列中任务的顺序
  • 比如每个线程处理的任务重要性不同，我们可以通过优先级的大小，来决定该线程在队列中被处理的次序

优先级队列的实现

• 方式一：创建优先级的节点，保存在堆结构中

class PriorityNode<T> {
  priority: number
  value: T
  constructor(value: T, priority: number) {
    this.value = value
    this.priority = priority
  }
  valueOf() {
    return this.priority
  }
}
class PriorityQueue<T> {
  private heap: Heap<PriorityNode<T>> = new Heap()
  enqueue(value: T, priority: number) {
    const newNode = new PriorityNode(value, priority)
    this.heap.insert(newNode)
  }
  dequeue(): T | undefined {
    return this.heap.extract()?.value
  }
  peek(): T | undefined {
    return this.heap.peek()?.value
  }
  isEmpty() {
    return this.heap.isEmpty()
  }
  size() {
    return this.heap.size()
  }
}

• 方式二：实现对应 valueOf 来控制对应节点优先级

class PriorityQueue2<T> {
  private heap: Heap<T> = new Heap()
  enqueue(value: T) {
    this.heap.insert(value)
  }
  dequeue(): T | undefined {
    return this.heap.extract()
  }
  peek(): T | undefined {
    return this.heap.peek()
  }
  isEmpty() {
    return this.heap.isEmpty()
  }
  size() {
    return this.heap.size()
  }
}

class Student {
  name: string
  score: number
  constructor(name: string, score: number) {
    this.name = name
    this.score = score
  }
  valueOf() {
    return this.score
  }
}

• 方式三：使用最普通数组实现

class PriorityQueue3<T> {
  private list: { value: T; priority: number }[] = []
  enqueue(value: T, priority: number) {
    const newElement = { value, priority }
    if (this.isEmpty()) {
      this.list.push(newElement)
    } else {
      const size = this.size()
      for (let i = 0; i < size; i++) {
        if (priority > this.list[i].priority) {
          this.list.splice(i, 0, newElement)
          return
        }
      }
      this.list.push(newElement)
    }
  }
  dequeue() {
    return this.list.shift()
  }
  isEmpty() {
    return this.list.length ? false : true
  }
  size() {
    return this.list.length
  }
}