C++ 实现队列深入讲解 - 摩柯技术社区

队列的基本概念

队列（Queue）是一种特殊的线性数据结构，它遵循先进先出（First In First Out，FIFO）的原则。可以将队列想象成日常生活中的排队场景，比如在银行排队办理业务，先到的人先办理，后到的人则排在队尾等待。在队列中，新元素总是添加到队列的末尾（称为入队操作，enqueue），而从队列中取出元素时，总是从队列的头部取出（称为出队操作，dequeue）。

队列有两个重要的端点：队头（front）和队尾（rear）。队头是最先进入队列的元素所在的位置，也是出队操作发生的位置；队尾则是新元素进入队列的位置，即入队操作发生的位置。

C++ 标准库中的队列

在 C++ 标准库中，提供了 std::queue 容器适配器来实现队列。容器适配器是一种基于其他容器（如 std::deque、std::list）构建的容器，它提供了特定的数据结构接口。std::queue 通常默认基于 std::deque 实现，当然也可以指定其他序列容器作为其底层实现。

下面是一个简单使用 std::queue 的示例代码：

#include <iostream>
#include <queue>

int main() {
    // 创建一个队列，存储 int 类型数据
    std::queue<int> q;

    // 入队操作
    q.push(10);
    q.push(20);
    q.push(30);

    // 检查队列是否为空
    if (!q.empty()) {
        // 输出队头元素
        std::cout << "队头元素: " << q.front() << std::endl;

        // 出队操作
        q.pop();

        // 再次输出队头元素
        std::cout << "出队后队头元素: " << q.front() << std::endl;
    }

    // 输出队列大小
    std::cout << "队列大小: " << q.size() << std::endl;

    return 0;
}

在上述代码中：

std::queue<int> q; 创建了一个存储 int 类型数据的队列 q。
q.push(10); 等语句进行入队操作，将元素添加到队列末尾。
q.empty() 用于检查队列是否为空。
q.front() 获取队头元素，但不会将其从队列中移除。
q.pop() 执行出队操作，移除队头元素。
q.size() 返回队列中元素的个数。

基于数组实现队列

虽然 C++ 标准库提供了 std::queue，但了解如何自己实现队列有助于深入理解其工作原理。首先，我们来看基于数组的队列实现。

基于数组实现队列时，需要考虑以下几个方面：

数组的大小：确定队列能够容纳的最大元素个数。
队头和队尾的位置：使用两个变量分别记录队头和队尾在数组中的位置。
入队和出队操作：实现入队时将元素添加到队尾，出队时移除队头元素，并更新队头和队尾的位置。

下面是一个简单的基于数组实现队列的代码示例：

#include <iostream>
#include <stdexcept>

class ArrayQueue {
private:
    int *queueArray;
    int capacity;
    int frontIndex;
    int rearIndex;
    int currentSize;

public:
    ArrayQueue(int size) : capacity(size), frontIndex(0), rearIndex(0), currentSize(0) {
        queueArray = new int[capacity];
    }

    ~ArrayQueue() {
        delete[] queueArray;
    }

    // 入队操作
    void enqueue(int value) {
        if (isFull()) {
            throw std::overflow_error("队列已满");
        }
        queueArray[rearIndex] = value;
        rearIndex = (rearIndex + 1) % capacity;
        currentSize++;
    }

    // 出队操作
    int dequeue() {
        if (isEmpty()) {
            throw std::underflow_error("队列为空");
        }
        int dequeuedValue = queueArray[frontIndex];
        frontIndex = (frontIndex + 1) % capacity;
        currentSize--;
        return dequeuedValue;
    }

    // 获取队头元素
    int front() const {
        if (isEmpty()) {
            throw std::underflow_error("队列为空");
        }
        return queueArray[frontIndex];
    }

    // 检查队列是否为空
    bool isEmpty() const {
        return currentSize == 0;
    }

    // 检查队列是否已满
    bool isFull() const {
        return currentSize == capacity;
    }

    // 获取队列大小
    int size() const {
        return currentSize;
    }
};

int main() {
    ArrayQueue q(5);
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    std::cout << "队头元素: " << q.front() << std::endl;
    std::cout << "出队元素: " << q.dequeue() << std::endl;
    std::cout << "队头元素: " << q.front() << std::endl;

    return 0;
}

在上述代码中：

ArrayQueue 类包含一个动态分配的整数数组 queueArray，用于存储队列元素。
capacity 表示队列的最大容量，frontIndex 和 rearIndex 分别记录队头和队尾的位置，currentSize 记录当前队列中元素的个数。
构造函数 ArrayQueue(int size) 初始化队列的容量，并分配数组空间。
析构函数 ~ArrayQueue() 释放分配的数组内存。
enqueue(int value) 方法将元素添加到队列末尾，如果队列已满则抛出 std::overflow_error 异常。
dequeue() 方法移除并返回队头元素，如果队列为空则抛出 std::underflow_error 异常。
front() 方法返回队头元素，但不进行移除操作。
isEmpty() 和 isFull() 方法分别用于检查队列是否为空和已满。
size() 方法返回当前队列中元素的个数。

循环队列

上述基于数组的队列实现存在一个问题，即当队尾指针 rearIndex 移动到数组末尾后，如果前面有空闲位置，也无法再利用这些位置添加新元素，导致数组空间的浪费。循环队列（Circular Queue）则解决了这个问题。

循环队列通过将数组视为一个环形结构，当队尾指针到达数组末尾时，可以重新回到数组开头，继续利用前面的空闲位置。

下面是循环队列的实现代码：

#include <iostream>
#include <stdexcept>

class CircularQueue {
private:
    int *queueArray;
    int capacity;
    int frontIndex;
    int rearIndex;

public:
    CircularQueue(int size) : capacity(size), frontIndex(0), rearIndex(0) {
        queueArray = new int[capacity];
    }

    ~CircularQueue() {
        delete[] queueArray;
    }

    // 入队操作
    void enqueue(int value) {
        if (isFull()) {
            throw std::overflow_error("队列已满");
        }
        queueArray[rearIndex] = value;
        rearIndex = (rearIndex + 1) % capacity;
    }

    // 出队操作
    int dequeue() {
        if (isEmpty()) {
            throw std::underflow_error("队列为空");
        }
        int dequeuedValue = queueArray[frontIndex];
        frontIndex = (frontIndex + 1) % capacity;
        return dequeuedValue;
    }

    // 获取队头元素
    int front() const {
        if (isEmpty()) {
            throw std::underflow_error("队列为空");
        }
        return queueArray[frontIndex];
    }

    // 检查队列是否为空
    bool isEmpty() const {
        return frontIndex == rearIndex;
    }

    // 检查队列是否已满
    bool isFull() const {
        return (rearIndex + 1) % capacity == frontIndex;
    }

    // 获取队列大小
    int size() const {
        return (rearIndex - frontIndex + capacity) % capacity;
    }
};

int main() {
    CircularQueue q(5);
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    std::cout << "队头元素: " << q.front() << std::endl;
    std::cout << "出队元素: " << q.dequeue() << std::endl;
    std::cout << "队头元素: " << q.front() << std::endl;

    return 0;
}

在这个循环队列的实现中：

CircularQueue 类的结构与基于数组的队列类似，但只使用 frontIndex 和 rearIndex 来跟踪队列状态。
enqueue(int value) 方法在添加元素时，通过 rearIndex = (rearIndex + 1) % capacity; 将队尾指针移动到下一个位置，实现环形结构。
dequeue() 方法移除队头元素时，同样通过 frontIndex = (frontIndex + 1) % capacity; 更新队头指针。
isEmpty() 方法通过判断 frontIndex 和 rearIndex 是否相等来确定队列是否为空。
isFull() 方法通过判断 (rearIndex + 1) % capacity 是否等于 frontIndex 来确定队列是否已满。
size() 方法通过 (rearIndex - frontIndex + capacity) % capacity 计算队列中元素的个数。

基于链表实现队列

除了基于数组实现队列，还可以使用链表来实现。链表实现的队列具有动态分配内存的特点，不需要预先确定队列的最大容量。

链表队列通常使用单链表或双链表来实现，这里我们以单链表为例。

#include <iostream>
#include <stdexcept>

// 定义链表节点结构
struct QueueNode {
    int data;
    QueueNode *next;
    QueueNode(int value) : data(value), next(nullptr) {}
};

class LinkedQueue {
private:
    QueueNode *frontNode;
    QueueNode *rearNode;

public:
    LinkedQueue() : frontNode(nullptr), rearNode(nullptr) {}

    ~LinkedQueue() {
        while (frontNode != nullptr) {
            QueueNode *temp = frontNode;
            frontNode = frontNode->next;
            delete temp;
        }
    }

    // 入队操作
    void enqueue(int value) {
        QueueNode *newNode = new QueueNode(value);
        if (rearNode == nullptr) {
            frontNode = rearNode = newNode;
        } else {
            rearNode->next = newNode;
            rearNode = newNode;
        }
    }

    // 出队操作
    int dequeue() {
        if (isEmpty()) {
            throw std::underflow_error("队列为空");
        }
        QueueNode *temp = frontNode;
        int dequeuedValue = temp->data;
        frontNode = frontNode->next;
        if (frontNode == nullptr) {
            rearNode = nullptr;
        }
        delete temp;
        return dequeuedValue;
    }

    // 获取队头元素
    int front() const {
        if (isEmpty()) {
            throw std::underflow_error("队列为空");
        }
        return frontNode->data;
    }

    // 检查队列是否为空
    bool isEmpty() const {
        return frontNode == nullptr;
    }

    // 获取队列大小
    int size() const {
        int count = 0;
        QueueNode *current = frontNode;
        while (current != nullptr) {
            count++;
            current = current->next;
        }
        return count;
    }
};

int main() {
    LinkedQueue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    std::cout << "队头元素: " << q.front() << std::endl;
    std::cout << "出队元素: " << q.dequeue() << std::endl;
    std::cout << "队头元素: " << q.front() << std::endl;

    return 0;
}

在上述基于链表实现队列的代码中：

首先定义了 QueueNode 结构体，用于表示链表中的节点，每个节点包含数据 data 和指向下一个节点的指针 next。
LinkedQueue 类包含两个指针 frontNode 和 rearNode，分别指向队列的头节点和尾节点。
构造函数 LinkedQueue() 初始化这两个指针为 nullptr。
析构函数 ~LinkedQueue() 遍历链表，释放所有节点的内存。
enqueue(int value) 方法创建一个新节点，并将其添加到链表末尾。如果队列为空，则 frontNode 和 rearNode 都指向新节点；否则，将新节点连接到 rearNode 之后，并更新 rearNode。
dequeue() 方法移除并返回队头节点的数据。如果移除节点后队列变为空，则同时更新 rearNode 为 nullptr。
front() 方法返回队头节点的数据。
isEmpty() 方法通过判断 frontNode 是否为 nullptr 来确定队列是否为空。
size() 方法通过遍历链表计算节点个数来获取队列大小。

队列的应用场景

操作系统中的任务调度：在多任务操作系统中，任务通常被安排在一个队列中，操作系统按照先进先出的原则从队列中取出任务并执行。这样可以保证任务的公平执行，避免某些任务长时间得不到处理。
广度优先搜索（BFS）：在图的遍历算法中，广度优先搜索使用队列来存储待访问的节点。从起始节点开始，将其邻居节点依次加入队列，然后从队列中取出节点并继续访问其邻居，直到遍历完所有可达节点。这种方式能够保证按照层次顺序访问节点。
打印队列：在计算机系统中，打印任务通常会被放入一个打印队列中。用户提交的打印任务按照提交的先后顺序在队列中等待，打印机从队列头部依次取出任务进行打印，确保任务的顺序执行。
网络请求处理：在服务器端处理网络请求时，队列可以用于缓存请求。当服务器接收到大量请求时，将请求放入队列，然后按照顺序依次处理，避免服务器因同时处理过多请求而崩溃。

队列性能分析

基于数组的队列：
- 入队和出队操作的时间复杂度：在一般情况下，入队和出队操作的时间复杂度都是 $O(1)$，因为只需要简单地更新队头和队尾指针。但是，如果队列已满需要扩容（动态数组实现），入队操作的时间复杂度可能变为 $O(n)$，因为需要重新分配内存并复制元素。
- 空间复杂度：空间复杂度为 $O(n)$，其中 $n$ 是队列的最大容量，因为需要分配一个大小为 $n$ 的数组来存储元素。
循环队列：
- 入队和出队操作的时间复杂度：同样，入队和出队操作的时间复杂度在正常情况下为 $O(1)$，不需要考虑扩容问题，因为它通过环形结构有效地利用了数组空间。
- 空间复杂度：空间复杂度也是 $O(n)$，与基于数组的队列类似，取决于数组的大小。
基于链表的队列：
- 入队和出队操作的时间复杂度：入队和出队操作的时间复杂度均为 $O(1)$。入队时只需要创建一个新节点并更新 rearNode，出队时只需要更新 frontNode 并释放节点内存。
- 空间复杂度：空间复杂度为 $O(n)$，其中 $n$ 是队列中元素的个数，因为每个元素都需要一个节点来存储，内存使用随元素个数动态变化。

总结与拓展

通过以上对 C++ 中队列实现的深入讲解，我们了解了队列的基本概念、标准库实现、基于数组和链表的自定义实现以及循环队列的特点。不同的实现方式各有优缺点，在实际应用中需要根据具体需求选择合适的实现。

进一步拓展，可以考虑实现线程安全的队列，用于多线程环境下的数据共享和同步。还可以研究优先级队列，它与普通队列的区别在于元素出队的顺序不是按照先进先出，而是根据元素的优先级。这些拓展内容将进一步丰富我们对队列这一数据结构的理解和应用能力。