第8章 高阶队列结构

8.1 双端队列

在2.3小节中，有学习过基础的队列（Queue）结构，它是一种受限的线性结构，并且限制非常的严格。本章会在基础的队列结构上，学习进阶的双端队列（Deque）结构。

8.1.1 双端队列的概念与特性

双端队列在单向队列的基础上解除了一部分限制：允许在队列的两端添加（入队）和删除（出队）元素。从双端队列的每一端（前端或者后端）来看，都有点像栈结构，可以在同一端压入和弹出元素。

双端队列如图8-1所示。

图8-1 双端队列

因为双端队列解除了一部分限制，所以在解决一些特定问题时会更加的方便。比如滑动窗口问题：https://leetcode.cn/problems/sliding-window-maximum/description/。滑动窗口最大值如图8-2所示。

图8-2 滑动窗口最大值

双端队列的概念是易于理解的，接下来用代码来实现。

8.1.2 双端队列的代码实现

双端队列可以基于普通队列结构去实现，只需要在普通队列的基础上做两件事情：

（1）在普通队列中允许出队的一端，同时允许入队。

（2）在普通队列中允许入队的一端，同时允许出队。

所以双端队列需要继承普通队列结构，在原有基础上去添加以上两个步骤即可。普通队列结构的代码如下：

▼
ts
复制代码
interface IList<T> {
  // peek
  peek(): T | undefined
  // 判断是否为空
  isEmpty(): boolean
  // 元素的个数
  size(): number
}


interface IQueue<T> extends IList<T> {
  // 入队方法
  enqueue(element: T): void
  // 出队方法
  dequeue(): T | undefined
}

class ArrayQueue<T> implements IQueue<T> {
  // 内部是通过数组(链表)保存
  protected data: T[] = []

  enqueue(element: T): void {
    this.data.push(element)
  }

  dequeue(): T | undefined {
    return this.data.shift()
  }

  peek(): T | undefined {
    return this.data[0]
  }

  isEmpty(): boolean {
    return this.data.length === 0
  }

  size(): number {
    return this.data.length
  }
}

export default ArrayQueue

双端队列会继承自ArrayQueue。双端队列的初始化搭建如下：

▼
ts
复制代码
class ArrayDeque<T> extends ArrayQueue<T> {
  addFront(element: T): void {}
  removeBack(): T | undefined {
    return undefined
  }
}

export default ArrayDeque

普通队列中的入队方法是enqueue()，出队方法是dequeue()，即数组尾部入队，数组首部出队。PS：因为之前实现普通队列结构的底层是数组，因此双端队列会继承这一特点。除了数组之外，普通队列以及双端队列的底层也可以基于链表来实现。

我们将普通队列中的出队入队方法的逻辑反过来，直接用在addFront()与removeBack()方法上即可。从数组首部入队，数组尾部出队。

▼
ts
复制代码
class ArrayDeque<T> extends ArrayQueue<T> {
  // 从队列头部添加元素
  addFront(element: T): void {
    this.data.unshift(element)
  }
  // 从队列尾部删除元素
  removeBack(): T | undefined {
    return this.data.pop()
  }
}

export default ArrayDeque

完成双端队列的代码编写，需要验证双端队列（Deque）是否能同时正确支持「头部插入」和「尾部删除」，并保证元素顺序符合预期（FIFO/LIFO 混合场景下的正确性），测试代码如下：

▼
ts
复制代码
const deque = new ArrayDeque<string>()
deque.enqueue("aaa")
deque.enqueue("bbb")
deque.enqueue("ccc")
deque.addFront("abc")
deque.addFront("cba")
while (!deque.isEmpty()) {
  console.log(deque.removeBack())
}

8.1.3 双端队列的应用场景

双端队列主要有两类应用。

第一类典型应用是需要同时高效处理“头部”和“尾部”操作的场景。比如滑动窗口问题（取最大值/最小值），会不断从队尾移除无用元素、从队头移除过期元素；又比如任务调度或消息缓冲，紧急任务可以从队头插入，普通任务从队尾进入，同时还能从任一端取出处理。双端队列在这些场景下可以把原本需要多种数据结构配合的逻辑，压缩成一种结构完成。

这一类的典型应用在8.1.1小节介绍概念的时候，有了解过，会在第13章 刷LeetCode题目中，来练习。

第二类应用是在栈和队列之间自由切换的算法设计。双端队列既可以当栈用（只在一端进出），也可以当队列用（一端进、另一端出），还可以混合使用，这在回溯、表达式求值、回文判断、BFS 的 0-1 权重最短路径等算法中非常常见。它的价值不在于“新功能”，而在于用统一的接口，降低算法状态切换和边界处理的复杂度。

8.2 优先级队列

什么是优先级？在生活中，我往往会将面临的事情从重要与紧急两个角度来区分，从而形成以下4种优先度级别：

（1）重要且紧急。

（2）重要且不紧急。

（3）不重要且紧急。

（4）不重要且不紧急。

我会按顺序处理事情，该顺序即是优先级。很多时候，我们的时间往往会被不重要且紧急的事情所占据，从而无法处理对我们未来发展更重要但不紧急的事情。要权衡其中的平衡，不要让不重要且紧急的事情对我们生活做太多次越界，做得越好，我们生活的效率与质量就会越高。

优先级队列就是基于以上思考映射的一种数据结构，让我们开始学习它吧！

8.2.1 优先级队列的概念与特性

优先级队列（Priority Queue）是一种比普通队列更加高效的数据结构。可以把优先级队列（Priority Queue）理解成一种“不完全按先来先走，而是按重要程度走”的队列。和普通队列只关心谁先来不同，优先级队列中的每个元素都会带一个“优先级”，每次出队的永远是当前优先级最高的元素，而不是最早进入的那个。你可以把它想成：排队是存在的，但队伍里的人会根据“重要性”被重新安排位置。

现实中的例子非常直观。比如机场登机，头等舱、商务舱的人即使后到，也会比经济舱的人先登机；又比如医院急诊室，医生会优先处理病情严重的患者，而不是单纯按到达时间顺序。这些场景的共同点是：顺序很重要，但“重要性”比“先后”更重要，这正是优先级队列要解决的问题。

在计算机中，优先级队列常用于任务调度。例如操作系统或线程池里，不同任务的重要性不同：系统关键任务、实时任务要比普通后台任务更早被处理。通过给任务设置优先级，优先级队列就可以自动帮我们把更重要的任务排到前面执行，而程序员不需要手动维护复杂的排序逻辑。

至于实现方式，优先级队列可以用数组、链表等结构来做，但最常用的是“堆（Heap）”。堆并不是把所有元素完全排好序，而是保证“最大（或最小）的元素总是在队头”，这样入队和出队都能在较高效率下完成。对初学者来说，可以先记住一句话：优先级队列 = 带权重的队列，而堆是实现它的最佳工具。

8.2.2 基于堆的优先级队列实现

优先级队列的实现方式一：创建优先级的节点，保存在堆结构中。

这种实现方式的核心思想是：把“元素本身”和“它的优先级”绑定在一起，作为一个节点存进堆中。每个节点通常包含两部分信息：value（真正要处理的数据）和 priority（优先级大小）。然后用堆（通常是最大堆或最小堆）来存放这些节点，堆的比较规则不是看 value，而是只根据 priority 来决定节点在堆中的位置。

当元素入队时，就把一个“带优先级的节点”插入堆中，堆会通过上浮操作自动调整结构，保证优先级最高的节点始终在堆顶；当元素出队时，直接取出堆顶节点即可，这个节点就是当前优先级最高的元素。这样一来，入队和出队的时间复杂度都能保持在 O(log n)，既保证了顺序正确，又具备很高的执行效率。这也是实际工程中实现优先级队列最常见、最稳定的一种方式。

接下来，我们来封装优先级节点，然后再将节点存放进堆里面。

▼
ts
复制代码
class PriorityNode<T> {
  priority: number
  value: T
  constructor(value: T, priority: number) {
    this.priority = priority
    this.value = value
  }
  // 方便比较大小
  valueOf() {
    return this.priority
  }
}
// 创建的优先级节点实例
const p1 = new PriorityNode<string>("abc", 100)
const p2 = new PriorityNode<string>("cba", 10)
const p3 = new PriorityNode<string>("nba", 1000)
const p4 = new PriorityNode<string>("mba", 10000)

接下来我们需要一个堆结构，然后将创建的优先级节点实例放入堆结构内。堆结构代码如下所示：

▼
ts
复制代码
export default class Heap<T> {
  // 属性
  private data: T[] = []
  private length: number = 0
  private isMax: boolean

  constructor(arr: T[] = [], isMax = true) {
    this.isMax = isMax
    if (arr.length === 0) return
    this.buildHeap(arr)
  }

  // 私有工具方法
  private swap(i: number, j: number) {
    const temp = this.data[i]
    this.data[i] = this.data[j]
    this.data[j] = temp
  }

  private compare(i: number, j: number): boolean {
    if (this.isMax) {
      return this.data[i] >= this.data[j]
    } else {
      return this.data[i] <= this.data[j]
    }
  }

  // 方法
  /** 插入操作 */
  insert(value: T) {
    // 1.将元素放到数组的尾部
    this.data.push(value)
    this.length++

    // 2.维护最大堆的特性(最后位置的元素需要进行上滤操作)
    this.heapify_up()
  }

  private heapify_up() {
    let index = this.length - 1
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2)
      if (this.compare(parentIndex, index)) {
        break
      }
      this.swap(index, parentIndex)
      index = parentIndex
    }
  }

  /** 提取操作 */
  extract(): T | undefined {
    // 1.判断元素的个数为0或者1的情况
    if (this.length === 0) return undefined
    if (this.length === 1) {
      this.length--
      return this.data.pop()!
    }

    // 2.提取并且需要返回的最大值
    const topValue = this.data[0]
    this.data[0] = this.data.pop()!
    this.length--

    // 3.维护最大堆的特性: 下滤操作
    this.heapify_down(0)

    return topValue
  }

  private heapify_down(start: number) {
    // 3.1.定义索引位置
    let index = start

    while (2 * index + 1 < this.length) {
      // 3.2.找到左右子节点
      let leftChildIndex = 2 * index + 1
      let rightChildIndex = leftChildIndex + 1

      // 3.3.找到左右子节点较大的值
      let largerIndex = leftChildIndex
      if (rightChildIndex < this.length && this.compare(rightChildIndex, leftChildIndex)) {
        largerIndex = rightChildIndex
      }

      // 3.4.较大的值和index位置进行比较
      if (this.compare(index, largerIndex)) {
        break
      }

      // 3.5.交换位置
      this.swap(index, largerIndex)
      index = largerIndex
    }
  }


  /** 其他方法 */
  peek(): T | undefined {
    return this.data[0]
  }

  size() {
    return this.length
  }

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

  buildHeap(arr: T[]) {
    // 1.使用arr的值: 数组/长度
    this.data = arr
    this.length = arr.length

    // 2.从第一个非叶子节点, 开始进行下滤操作
    const start = Math.floor((this.length - 1) / 2)
    for (let i = start; i >= 0; i--) {
      this.heapify_down(i)
    }
  }
}

堆结构的学习位于第9章，可先学习第9章再来回顾用堆实现的优先级队列。

将二叉堆作为优先级队列的底层存储，优先级队列的初始化搭建如下：

▼
ts
复制代码
import Heap from '二叉堆'
// 优先级队列
class PriorityQueue<T> {
  private heap: Heap<PriorityNode<T>> = new Heap()
}

const pQueue = new PriorityQueue<string>()

完成初始化搭建，来实现优先级队列应该有的方法，从enqueue()方法开始，该方法的作用为：将优先级节点插入堆结构中。

但将优先级节点插入堆结构中，又有两种方式：

优先级节点插入优先级队列的考量一是先实例化优先级节点，将优先级节点通过优先级队列的实例方法将其插入到优先级队列实例中。

▼
ts
复制代码
class PriorityNode<T> {
  priority: number
  value: T
  constructor(value: T, priority: number) {
    this.priority = priority
    this.value = value
  }
  valueOf() {
    return this.priority
  }
}

class PriorityQueue<T> {
  private heap: Heap<PriorityNode<T>> = new Heap()
  enqueue(node: PriorityNode<T>) {
    this.heap.insert(node)
  }
}

// 创建的优先级节点实例
const p1 = new PriorityNode<string>("abc", 100)
const p2 = new PriorityNode<string>("cba", 10)
const p3 = new PriorityNode<string>("nba", 1000)
const p4 = new PriorityNode<string>("mba", 10000)
// 创建基于堆结构实现的优先级队列
const priorityQueue = new PriorityQueue<string>()
// 往优先级队列中，插入优先级节点
priorityQueue.enqueue(p1)
priorityQueue.enqueue(p2)
priorityQueue.enqueue(p3)
priorityQueue.enqueue(p4)

优先级节点插入优先级队列的方式一，从代码层面简洁明了。但创建优先级节点实例是否要和往优先级队列中插入优先级节点区分开，是一个很有意思的话题。这件事情背后的考量是：耦合度是否要再高一些？是否要将创建优先级节点实例与往优先级队列中插入优先级节点合并在一起？

在是否合并的问题上，我认为是可以合并的。因为PriorityQueue类是优先级队列，优先级队列的底层二叉堆虽然接受任何类型的元素节点。但优先级队列不是，优先级队列只能接受优先级节点，如果有一天，往优先级队列中插入了不符合规定的节点，例如没有priority属性，那优先级队列就会失去了"优先"的特性。优先级节点和优先级队列应该是强绑定的。

所以，我认为优先级队列的enqueue()方法应该延伸出第二种考量（考量二）：用户只需要往enqueue()方法中，传入数据value和优先度priority两个参数，enqueue()方法的内部将数据与优先度组装成优先级节点，然后将优先级节点插入到优先级队列中。

▼
ts
复制代码
class PriorityNode<T> {
  priority: number
  value: T
  constructor(value: T, priority: number) {
    this.priority = priority
    this.value = value
  }
  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)
  }
}

// 往优先级队列中添加元素
const priorityQueue = new PriorityQueue<string>()
priorityQueue.enqueue("abc", 100)
priorityQueue.enqueue("cba", 10)
priorityQueue.enqueue("nba", 1000)

完成enqueue()方法后，我们来编写dequeue()、peek()、isEmpty()，size()这四个方法，都类似于之前所实现的方法逻辑。完整代码如下：

▼
ts
复制代码
class PriorityNode<T> {
  priority: number
  value: T
  constructor(value: T, priority: number) {
    this.priority = priority
    this.value = value
  }
  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()
  }
}

测试示例如下：

▼
ts
复制代码
const pQueue = new PriorityQueue<string>()
pQueue.enqueue("why", 98)
pQueue.enqueue("kobe", 90)
pQueue.enqueue("james", 105)
// 取出数据
while (!pQueue.isEmpty()) {
  console.log(pQueue.dequeue())
}

最后，我们来快速解释一下刚才编写的四个方法：

（1）dequeue()：从优先级队列中取出并删除当前优先级最高的元素。调用堆的 extract() 取出堆顶的 PriorityNode，再返回其中的 value，堆结构会在内部自动完成下滤以保持堆性质。

（2）peek()：查看当前优先级最高的元素，但不移除它。直接访问堆顶元素 heap.peek()，只读取其中的 value，不触发任何结构调整。

（3）isEmpty()：判断优先级队列是否为空。将判断交给底层堆，实质是检查堆中元素个数是否为 0。

（4）size()：获取当前优先级队列中元素的数量。直接返回底层堆维护的 length，不涉及任何堆操作。

这些方法大多是通过堆结构内部的方法所实现，因此并不困难，不在额外讲解。

8.2.3 基于自定义比较的优先级队列实现

在8.2.2小节中，我们通过堆结构来实现了优先级队列。即通过传递数据+优先度，来决定哪些数据更重要。但如果是自定义的数据，例如一份学生表，表里包含每个学生的姓名与成绩信息，我希望通过学生的成绩来区分。如果照着原有优先级队列肯定也可以实现，只需要将学生成绩复制一份到优先级部分。

▼
ts
复制代码
class Student {
  constructor(public name: string, public score: number) { }
}
// 成绩 98
const student1 = new Student("XiaoYu", 98)
const pQueue = new PriorityQueue<Student>()
// 将student1的成绩98复制一份给优先级
pQueue.enqueue(student1, 98)

将学生成绩复制一份到优先级部分，并不是不可以。但每个学生的成绩都复制一份到优先级中，如果学生非常多呢？那这种做法是值得去优化的。如果不是学生表，是其他类型的，更复杂的表，想手动复制会更加麻烦。

因此，通过自定义数据的自我比较来实现优先级队列就显得尤为重要。这需要利用到Object.prototype.valueOf()方法将优先级交给对象自己，而不需要通过优先级节点。

valueOf() 的作用是：当对象参与大小比较、算术运算或需要被转换为原始值时，告诉 JavaScript“应该用什么数值来代表这个对象”；通过重写 valueOf()，可以让自定义对象在比较时自动按某个关键字段（如分数、权重、优先级）进行比较，从而在不复制额外数据的情况下，自然地融入排序、堆和优先级队列等通用算法中。

▼
ts
复制代码
class PriorityQueue<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
  }
}

// 自定义比较
const pQueue = new PriorityQueue<Student>()
// 在插入到堆的时候，会通过 this.core 自动排序 this.core代表了对象本身参与运算
pQueue.enqueue(new Student("why", 99))
pQueue.enqueue(new Student("kobe", 89))
pQueue.enqueue(new Student("james", 95))
pQueue.enqueue(new Student("curry", 88))

while (!pQueue.isEmpty()) {
  console.log(pQueue.dequeue())
}