【数据结构】队列实现剖析：掌握队列的底层实现

在计算机科学中，**队列（Queue）**是一种常见的数据结构，它遵循先进先出（FIFO，First In First Out）的原则。队列的应用非常广泛，例如任务调度、资源管理、进程通信等。本篇文章旨在为计算机专业的初学者详细讲解队列的多种实现方式，并通过 C++ 的代码示例让读者更好地理解和掌握这些概念和底层原理及优缺点。

本篇文章需要读者具有队列的基本知识，文内会简略介绍，若不清楚什么是队列，可参考以下文章：

• 【计算机科学】深入理解队列：有序的数据之道
• 【数据结构】快慢指针探秘：理解链表与数组中的环结构

全文共计4020字，耗时5天缝缝补补完成，若能够让你学到新知识，你可以给我点个👍或者关注。

队列的作用

队列的主要作用是按照顺序存储和管理数据，其常见应用包括：

1. 任务调度： 队列可用于管理任务执行的先后顺序，例如操作系统中的进程调度。
2. 数据缓冲： 在流式数据处理中，队列用于暂存数据。
3. 广度优先搜索（BFS）： 在图或树的遍历中，队列是关键的数据结构。

我们会在后期的内容中带来队列应用的实战内容。

队列的基本操作

一个队列通常包含以下几个操作：

• enqueue（入队）： 将元素加入队列尾部。
• dequeue（出队）： 从队列头部移除并返回元素。
• isEmpty（判空）： 判断队列是否为空。
• isFull（判满，可选）： 判断队列是否已满（通常适用于基于数组的实现）。

若对队列的概念还是比较模糊，强烈再去复习一下队列的基本知识

• 【计算机科学】深入理解队列：有序的数据之道

队列的多种手动实现方式

---

1. 基于纯数组的简单实现

这种实现方式是队列的最基础版本，直接用一个固定大小的数组来存储队列元素，按照先进先出的顺序操作。队列的front和rear指针分别指向队头和队尾，所有元素插入到队尾，从队头取出。

特点

• 优点：

  1. 实现简单，逻辑清晰，适合入门学习队列概念。
  2. 内存分配静态化，不依赖额外数据结构，直接在数组上操作。

• 缺点：

  1. 空间浪费问题： 由于数组不循环，当rear到达数组末尾时，即使front前面有空余空间，队列也会被认为已满。
  2. 大小固定： 必须在初始化时确定数组的大小，缺乏灵活性。

手动实现时的注意事项

1. 边界判断： 要确保在插入时判断队列是否已满，在删除时判断队列是否为空，否则可能会导致数组越界或错误访问。
2. 队列空判断： 通常通过front == rear判断队列为空。
3. 队列满判断： 当rear == maxSize时，需要提示队列已满。
4. 动态调整难度： 该实现不支持动态扩展数组大小，需要手动扩展时增加实现难度。

#include <iostream>
using namespace std;struct Queue {
private:int *arr;int front, rear, maxSize;
public:Queue(int size) {maxSize = size;arr = new int[size];front = rear = 0;}~Queue() {delete[] arr;}bool isEmpty() {return front == rear;}bool isFull() {return rear == maxSize; // 队列满的条件}void enqueue(int x) {if (isFull()) {cout << "Queue is full!" << endl;return;}arr[rear++] = x;}int dequeue() {if (isEmpty()) {cout << "Queue is empty!" << endl;return -1;}return arr[front++];}
};

---

2. 基于数组的循环队列

循环队列是对纯数组实现的改进，通过将数组逻辑上看作是环形结构，解决了纯数组实现中空间浪费的问题。

特点

• 优点：

  1. 高效利用内存： 通过循环的方式重新利用之前已释放的空间，提高数组的空间利用率。
  2. 操作简单： 只需要在插入和删除操作中使用模运算即可实现循环。

• 缺点：

  1. 逻辑复杂度增加： 需要通过模运算来控制数组的循环，需要仔细处理front和rear的关系。
  2. 固定大小： 和纯数组一样，循环队列的大小也是固定的，无法动态扩展。

手动实现时的注意事项

1. 队列满和空的判断：
   • 无标志位实现： 通常通过(rear + 1) % maxSize == front判断队列已满，rear == front判断队列为空。需要注意，这种实现中，队列最多只能使用maxSize - 1个空间。
   • 带标志位实现： 引入tag标志位后，可以清楚区分队列满和空的状态（rear == front 时，配合tag判断队列状态）。
2. 模运算的正确性： 循环队列依赖模运算控制指针，确保数组不会越界。
3. 初始化边界条件： 在队列为空或刚初始化时，front和rear应该相等。
4. 特殊情况的处理： 需要处理rear追上front的情况，以及空队列状态下访问的错误提示。

#include <iostream>
using namespace std;struct Queue {
private:int *arr;int front, rear, maxSize;
public:Queue(int size) {maxSize = size;arr = new int[size];front = rear = 0;}~Queue() {delete[] arr;}bool isEmpty() {return front == rear;}bool isFull() {return (rear + 1) % maxSize == front; // 循环条件}void enqueue(int x) {if (isFull()) {cout << "Queue is full!" << endl;return;}arr[rear] = x;rear = (rear + 1) % maxSize;}int dequeue() {if (isEmpty()) {cout << "Queue is empty!" << endl;return -1;}int res = arr[front];front = (front + 1) % maxSize;return res;}
};

---

3. 基于链表的队列

基于链表的队列是动态存储的实现方式，不依赖固定大小的数组，通过链表的动态特性解决了内存限制问题。

特点

• 优点：

  1. 灵活性强： 队列大小不固定，可以根据需求动态分配和释放内存。
  2. 无队列满的情况： 只要系统内存允许，就可以插入任意多的元素。

• 缺点：

  1. 复杂性增加： 需要维护链表的动态分配和释放逻辑，代码实现比数组队列复杂。
  2. 内存开销： 每个节点需要额外的指针存储，整体占用内存比数组略高。

手动实现时的注意事项

1. 链表初始化： 确保front和rear指针正确初始化为空。
2. 边界条件： 在插入第一个元素时，需要同时更新front和rear指针。
3. 内存管理： 每次插入时动态分配内存，删除时释放内存，避免内存泄漏。
4. 空队列判断： 当front == nullptr时，队列为空。
5. 队列尾处理： 当删除最后一个元素后，需要将rear指针置为空。

#include <iostream>
using namespace std;struct Node {int value;Node *next;Node(int v) : value(v), next(nullptr) {}
};struct Queue {
private:Node *front, *rear;
public:Queue() {front = rear = nullptr;}~Queue() {while (front != nullptr) {Node *temp = front;front = front->next;delete temp;}}bool isEmpty() {return front == nullptr;}void enqueue(int x) {Node *newNode = new Node(x);if (isEmpty()) {front = rear = newNode;} else {rear->next = newNode;rear = newNode;}}int dequeue() {if (isEmpty()) {cout << "Queue is empty!" << endl;return -1;}int res = front->value;Node *temp = front;front = front->next;delete temp;if (!front) rear = nullptr; // 更新rearreturn res;}
};

---

4. 基于带头节点的链表队列

在链表实现的基础上，加入一个不存储数据的头节点，用来简化操作逻辑。

特点

• 优点：

  1. 边界处理简化： 由于头节点始终存在，可以统一插入和删除操作的逻辑，不需要处理链表为空时的特殊情况。
  2. 灵活性： 与普通链表队列一样，支持动态扩展，内存利用高。

• 缺点：

  1. 稍微增加内存占用： 需要额外的头节点，占用少量额外内存。
  2. 实现复杂度增加： 需要手动维护头节点和尾节点的指针。

手动实现时的注意事项

1. 头节点初始化： 确保头节点的next指针初始化为空，头节点本身可以设置一个哨兵值。
2. 插入操作： 在队列为空时，需要同时更新front->next和rear。
3. 删除操作： 从front->next开始删除节点，当删除最后一个节点后，需要将rear置为空。
4. 内存管理： 同样需要确保每次操作后，正确释放删除节点的内存。

#include <iostream>
using namespace std;struct Node {int value;Node *next;Node(int v) : value(v), next(nullptr) {}
};struct Queue {
private:Node *front, *rear;
public:Queue() {front = new Node(-1); // 带头节点rear = nullptr;}~Queue() {while (front != nullptr) {Node *temp = front;front = front->next;delete temp;}}bool isEmpty() {return rear == nullptr;}void enqueue(int x) {Node *newNode = new Node(x);if (isEmpty()) {front->next = newNode;rear = newNode;} else {rear->next = newNode;rear = newNode;}}int dequeue() {if (isEmpty()) {cout << "Queue is empty!" << endl;return -1;}Node *temp = front->next;int res = temp->value;front->next = temp->next;if (!front->next) rear = nullptr; // 更新reardelete temp;return res;}
};

5. 基于数组的循环队列（无额外标志位实现）

循环数组队列（无标志位）的实现是一种改进版的队列，数组逻辑上被看作环形。它通过模运算实现“循环”效果，从而提高了数组的空间利用率。

特点

• 优点：

  1. 空间利用率高： 不会像纯数组实现那样浪费数组前端的可用空间。
  2. 实现较为简单： 通过模运算控制指针即可实现循环，逻辑清晰。

• 缺点：

  1. 浪费一个存储单元： 为了区分队列空和满的情况，最多只能使用maxSize - 1个存储单元。
  2. 固定大小： 和所有数组实现一样，大小固定，无法动态扩展。

手动实现时的注意事项

1. 边界条件： 通过(rear + 1) % maxSize == front判断队列已满，通过rear == front判断队列为空。
2. 模运算正确性： 插入和删除时需要使用模运算来实现循环效果，避免指针越界。
3. 初始化： 队列初始化时，front和rear均指向数组的起始位置，队列为空。
4. 大小限制： 实际可用空间为maxSize - 1，需要特别注意数组容量的计算和使用。

代码

#include <iostream>
using namespace std;struct Queue {
private:int *arr;int front, rear, maxSize;
public:Queue(int size) {maxSize = size;arr = new int[size];front = rear = 0;}    ~Queue() {delete[] arr;}bool isFull() {return (rear + 1) % maxSize == front; // 判断队列满}bool isEmpty() {return front == rear; // 判断队列空}void enqueue(int x) {if (isFull()) {cout << "Queue is full." << endl;return;}arr[rear] = x; // 在队尾插入rear = (rear + 1) % maxSize; // 更新 rear，模运算实现循环}int dequeue() {if (isEmpty()) {cout << "Queue is empty." << endl;return -1; }int res = arr[front]; // 取出队头元素front = (front + 1) % maxSize; // 更新 front，模运算实现循环return res;}
};

---

6. 基于数组的循环队列（带标志位实现）

循环数组队列（带标志位）的实现是在无标志位版本的基础上引入一个tag标志位，来明确区分队列空和满的情况。这种实现避免了浪费一个存储单元的问题。

特点

• 优点：

  1. 空间利用率最高： 不会像无标志位版本那样浪费一个存储单元，可以使用整个数组存储数据。
  2. 状态区分清晰： 通过tag标志位清楚地表示当前队列是空还是满。

• 缺点：

  1. 实现稍复杂： 相比无标志位版本，多了tag标志位的更新逻辑。
  2. 固定大小： 依然受数组大小限制，无法动态扩展。

手动实现时的注意事项

1. 标志位的维护：
   • 在enqueue时，如果插入后rear == front，需要将tag置为1，表示队列满。
   • 在dequeue时，如果删除后rear == front，需要将tag置为0，表示队列空。
2. 边界条件：
   • 队列空的判断条件：front == rear && tag == 0。
   • 队列满的判断条件：front == rear && tag == 1。
3. 初始化： front和rear指针初始化为0，tag初始化为0，表示队列为空。
4. 模运算： 和无标志位版本类似，通过模运算实现循环效果。

代码

#include <iostream>
using namespace std;struct Queue {
private:int *arr;int front, rear, maxSize, tag;
public:Queue(int size) {maxSize = size;arr = new int[size];front = rear = 0;tag = 0; // 初始状态为空}~Queue() {delete[] arr;}bool isEmpty() {return front == rear && tag == 0; // 队列空：front == rear 且 tag 为 0}bool isFull() {return front == rear && tag == 1; // 队列满：front == rear 且 tag 为 1}void enqueue(int x) {if (isFull()) {cout << "Queue is full." << endl;return;}arr[rear] = x; // 在队尾插入rear = (rear + 1) % maxSize; // 更新 rearif (rear == front) tag = 1; // 如果 rear 追上 front，则队列满，tag 置为 1}int dequeue() {if (isEmpty()) {cout << "Queue is empty." << endl;return -1;}int res = arr[front]; // 取出队头元素front = (front + 1) % maxSize; // 更新 frontif (rear == front) tag = 0; // 如果 front 追上 rear，则队列空，tag 置为 0return res;}
};

总结

实现方式	优点	缺点	适用场景
纯数组队列	1. 实现简单，适合入门学习。2. 适合小规模的简单场景。	1. 空间利用率低，出队后前部空间不可复用。2. 数组固定大小，无法动态扩展。	小型队列，数据量较少且操作较简单的场景。
循环数组队列（无标志位）	1. 空间利用率高，支持循环操作。2. 实现逻辑相对清晰，易于理解。	1. 浪费一个存储单元，最大可用容量为maxSize - 1。2. 边界条件复杂，容易出错。	小型队列，数据量适中且对空间利用有一定要求。
循环数组队列（带标志位）	1. 空间利用率最高，无存储浪费。2. 状态明确，通过标志位区分队列空与满的状态。	1. 实现稍复杂，需要维护标志位的逻辑。2. 数组固定大小，仍无法动态扩展。	数据量较大且对空间利用率有高要求的场景。
链表队列（无头节点）	1. 动态分配空间，无需固定大小，支持数据量变化。2. 空间利用率高，无浪费。	1. 实现稍复杂，需要手动管理内存。2. 操作链表时，可能存在额外的时间和内存开销。	数据量不确定或需要动态调整大小的场景。
链表队列（带头节点）	1. 动态分配空间，支持大小变化。2. 带头节点的设计简化了插入和删除操作逻辑。	1. 实现复杂度高，需要维护链表和头节点。2. 内存利用率高，但链表操作较慢。	数据动态变化且需要更高鲁棒性的场景。
链表队列（带尾指针）	1. 通过尾指针优化入队操作，性能更高。2. 动态空间分配，适应数据量变化。	1. 内存分配和释放较复杂，容易出现内存泄漏问题。2. 指针操作复杂度较高，需小心处理边界。	数据量较大，需频繁插入删除的场景。

推荐选择依据：

1. 如果你是初学者或实现简单队列，纯数组队列是一个不错的起点。
2. 如果需要循环结构并注重空间利用率，选择循环数组队列（无标志位）**或**循环数组队列（带标志位），根据是否需要完整利用空间来决定。
3. 如果需要动态扩展且操作数据频繁，链表队列是最佳选择，根据是否需要头节点或尾指针进一步优化。

理解每种实现的原理和优缺点是学习数据结构的重要步骤。希望本文能够帮助你掌握队列的基本概念及实现方式，同时，若本文帮助到了你，你可以给我点个赞和关注，以支持我继续创作。