【数据结构】线性数据结构——队列

1. 队列的定义

队列（Queue）是一种线性数据结构，遵循 先进先出（FIFO，First In First Out） 的原则。元素总是从 队尾（Rear）插入，从队头（Front） 移除。类似于排队的场景：最先进入队列的人最先离开。

2. 队列的特点

• 先进先出： 第一个进入队列的元素最先被移除。

• 受限操作： 插入操作只能在队尾进行。删除操作只能在队头进行。

• 动态变化： 队列可以使用固定大小的数组实现，也可以使用链表实现动态扩展。

3. 队列的基本操作

以C++ 的 STL（标准模板库）提供的 std::queue 类模板为例，以下是队列的常见基本操作：

• push(value)：将元素 value 添加到队尾。

• pop()：移除队头元素。

• front()：返回队头元素。

• back()：返回队尾元素。

• empty()：检查队列是否为空。

• size()：返回队列中元素的个数。

4. 队列的实现方式

队列可以通过数组或链表实现。

(1) 数组实现队列： 使用一个数组和两个指针（front 和 rear）表示队头和队尾。

(2) 链表实现队列： 使用链表节点表示每个队列元素，链表的头部为队头，尾部为队尾。优点是支持动态扩展，不受固定大小限制。

4. 队列的分类

• 普通队列（Queue）： 遵循先进先出的规则。

• 双端队列（Deque）： 允许在队头和队尾两端同时进行入队（插入）和出队（删除）操作。
  

• 优先队列（Priority Queue）： 优先队列（Priority Queue）是一种特殊类型的队列，其中每个元素都具有优先级。优先级最高的元素会先被处理，而不是按照元素插入的顺序。优先队列可以看作是一个根据优先级排序的队列，通常使用 堆（heap） 作为底层数据结构。
  
  在 C++ 中，std::priority_queue 默认使用最大堆 （Max-Heap） 实现，使得优先队列中的最大元素（具有最高优先级）位于队头。如果需要最小堆（Min-Heap）行为，可以自定义比较函数。优先队列广泛应用于：

  a. 任务调度： 根据任务的优先级来调度任务执行。
  b. Dijkstra 算法： 在图的最短路径问题中，优先队列用于管理待处理的节点。
  c. Huffman 编码： 在数据压缩算法中，优先队列用于构建霍夫曼树。

• 循环队列（Circular Queue）： 循环队列（Circular Queue）是通过将队列的尾部与头部相连来优化空间使用的一种队列。普通队列在出队时，空间不会被及时回收，导致队列的数组前部分空闲空间无法利用，造成空间浪费。循环队列通过让队列达到最大容量后重新使用之前出队的空间，使得队列在逻辑上是“循环”的。