数据结构入门：线性数据结构之队列详解

数据结构入门：线性数据结构之队列详解

引用

CSDN

1.

https://m.blog.csdn.net/qq_45791939/article/details/144813896

队列是一种常见的线性数据结构，遵循先进先出（FIFO）的原则。本文将从队列的定义、特点、基本操作、实现方式和分类等多个维度对队列进行详细的介绍，帮助读者全面理解这一重要的数据结构。

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

5. 队列的分类

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

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

• 优先队列（Priority Queue）：优先队列（Priority Queue）是一种特殊类型的队列，其中每个元素都具有优先级。优先级最高的元素会先被处理，而不是按照元素插入的顺序。优先队列可以看作是一个根据优先级排序的队列，通常使用堆（heap）作为底层数据结构。

在 C++ 中，std::priority_queue 默认使用最大堆（Max-Heap）实现，使得优先队列中的最大元素（具有最高优先级）位于队头。如果需要最小堆（Min-Heap）行为，可以自定义比较函数。优先队列广泛应用于：

a. 任务调度：根据任务的优先级来调度任务执行。

b. Dijkstra 算法：在图的最短路径问题中，优先队列用于管理待处理的节点。

c. Huffman 编码：在数据压缩算法中，优先队列用于构建霍夫曼树。

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