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

在计算机科学中，**队列（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; // 更新rear
        return 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; // 更新rear
        delete 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; // 更新 rear
        if (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; // 更新 front
        if (rear == front) tag = 0; // 如果 front 追上 rear，则队列空，tag 置为 0
        return res;
    }
};

总结

推荐选择依据：

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

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