队列介绍

• 队列是一种线性数据结构，它通过两个主要操作（即入队和出队）来模拟现实世界的队列。

• 队列是一个有序列表，可以用数组或是链表来实现。遵循先进先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

• 优先级队列：每个元素都具有一定的优先级。并且可比较，优先级队列中元素的优先级决定了从优先级队列中移除元素的顺序。

• 索引优先级队列：在优先级队列上支持快速更新和删除键值对。适用于快速更新队列状态

• 使用场景

  • 任何等待线都可模拟队列，例如电影院/银行排队
  • 跟踪最近添加的元素
  • Web 服务器请求管理，先到先得
  • 广度优先搜索 (BFS) 图遍历

• 优先级队列使用场景

  • Dijkstra 最短路径算法的某些实现。
  • 任何时候您需要动态获取下一个最佳或下一个最差元素。
  • 用于 Huffman 编码（通常用于无损数据压缩）。
  • 最佳优先搜索 (BFS) 算法（例如 A*）使用 PQs 连续抓取下一个最有希望的节点。
  • 用于最小生成树 (MST) 算法。

• 算法复杂度
  enqueue O(1)
  dequeue O(1)
  peeking O(1)
  contains O(n)
  removal O(n)
  isEmpty O(1)
  contains、removal可能都需要扫描整个链表