深入剖析C++ queue：先进先出容器适配器的全面解读

昨天 1851阅读

一、引言

在C++的编程世界中，queue（队列）作为一种重要的数据结构，以其先进先出（First In First Out，FIFO）的特性，在众多场景中发挥着关键作用。它是一种容器适配器，底层依赖于其他容器来实现其功能。本文将深入探讨C++ queue的特性、用法以及在实际编程中的应用。

二、queue的基本概念

queue是一种遵循先进先出原则的容器。元素从一端插入（称为队尾，rear），从另一端移除（称为队头，front）。这种特性使得queue非常适合模拟现实生活中的排队场景，比如银行排队办理业务、餐厅排队点餐等。

在C++标准库中，queue被定义在<queue>头文件中。它可以容纳各种数据类型，只要该类型支持相关的操作。

深入剖析C++ queue：先进先出容器适配器的全面解读

三、queue的常用操作

（一）构造函数

// 默认构造函数，创建一个空队列
queue<int> q1;

// 基于已有容器构造队列
vector<int> vec = {1, 2, 3};
queue<int> q2(vec);

上述代码展示了queue的两种构造方式。默认构造函数创建一个空队列，而基于已有容器构造则可以快速初始化队列。

（二）元素操作

// 在队尾插入元素
q.push(4);

// 获取队头元素，但不删除
int frontElement = q.front();

// 获取队尾元素，但不删除
int rearElement = q.rear();

// 删除队头元素
q.pop();

// 判断队列是否为空
bool isEmpty = q.empty();

// 获取队列中元素的个数
int size = q.size();

这些操作是queue最常用的功能。push用于添加元素到队尾，front和rear分别获取队头和队尾元素，pop删除队头元素，empty判断队列是否为空，size获取队列大小。

四、queue的底层实现

queue底层通常基于deque（双端队列）或list（链表）来实现。不同的实现方式各有优缺点。

基于deque实现时，queue的插入和删除操作在两端都有较好的性能，因为deque支持在两端快速插入和删除。例如：

// 基于deque实现queue
template<class T, class Container = deque<T>>
class queue {
    // 内部使用Container来存储元素
    Container c;
public:
    // 各种操作通过调用Container的相应方法实现
    void push(const T& value) { c.push_back(value); }
    void pop() { c.pop_front(); }
    T& front() { return c.front(); }
    const T& front() const { return c.front(); }
    T& back() { return c.back(); }
    const T& back() const { return c.back(); }
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
};

基于list实现时，queue在中间插入和删除元素的性能较差，但在两端插入和删除有一定优势。其实现方式如下：

// 基于list实现queue
template<class T, class Container = list<T>>
class queue {
    Container c;
public:
    void push(const T& value) { c.push_back(value); }
    void pop() { c.pop_front(); }
    T& front() { return c.front(); }
    const T& front() const { return c.front(); }
    T& back() { return c.back(); }
    const T& back() const { return c.back(); }
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
};

五、queue在实际编程中的应用

（一）广度优先搜索（BFS）

在图论中，广度优先搜索是一种常用的遍历算法。queue在BFS中扮演着重要角色，用于存储待访问的节点。

#include <iostream>
#include <queue>
#include <vector>
#include <list>

using namespace std;

// 定义图的邻接表表示
using Graph = vector<list<int>>;

// BFS函数
void bfs(const Graph& graph, int start) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
    Graph graph = {
        {}, {2, 3}, {1, 4, 5}, {1, 6}, {2, 6}, {2, 3, 6}, {3, 4, 5}
    };

    bfs(graph, 1);

    return 0;
}

上述代码实现了一个简单的BFS算法。通过queue依次存储待访问的节点，确保按照广度优先的顺序遍历图。

（二）任务调度

在多任务处理系统中，queue可以用于任务调度。例如，有多个任务需要按照提交的顺序依次执行。

#include <iostream>
#include <queue>

using namespace std;

class Task {
public:
    int id;

    Task(int i) : id(i) {}

    void execute() {
        cout << "Executing task " << id << endl;
    }
};

int main() {
    queue<Task> taskQueue;

    taskQueue.push(Task(1));
    taskQueue.push(Task(2));
    taskQueue.push(Task(3));

    while (!taskQueue.empty()) {
        Task task = taskQueue.front();
        taskQueue.pop();
        task.execute();
    }

    return 0;
}

这里定义了一个Task类，通过queue来管理任务的执行顺序，先提交的任务先执行。