异常教程

C++ 容器类 <queue>（千字长文）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

  • 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
  • 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

前言

在编程的世界中，数据结构是解决问题的基石，而队列（Queue）作为经典的线性结构，因其“先进先出（FIFO）”特性，在任务调度、广度优先搜索（BFS）等场景中扮演着重要角色。C++ 标准库中的 <queue> 容器类，正是这一思想的完美实现。本文将从零开始，带领读者逐步掌握 <queue> 的核心概念、使用技巧及实战应用，帮助编程初学者和中级开发者快速上手这一强大的工具。

一、队列的基本概念与特性

1.1 什么是队列？

队列是一种遵循 先进先出（First-In-First-Out, FIFO） 规则的数据结构。想象一个银行排队系统：第一个到达的人（入队）将第一个接受服务（出队）。这种特性使得队列在需要按顺序处理任务的场景中不可或缺。

例如，在操作系统中，进程调度常使用队列管理任务；在游戏开发中，队列可用于控制角色的行动顺序。

1.2 队列的关键操作

队列的核心操作包括：

  • 入队（Enqueue）：将元素添加到队列尾部。
  • 出队（Dequeue）：移除并返回队列头部的元素。
  • 查看队头（Front）：获取队列头部元素的值，但不移除它。
  • 查看队尾（Back）：获取队列尾部元素的值。
  • 判空（Empty）：判断队列是否为空。
  • 获取长度（Size）：返回队列中元素的数量。

二、C++ 标准库中的 <queue> 容器类

2.1 <queue> 的包含与基本用法

在 C++ 中，通过包含头文件 <queue> 即可使用 std::queue 容器。其语法结构如下：

#include <queue>  
using namespace std;

queue<Type> myQueue; // 定义一个存储 Type 类型元素的队列

示例：基本操作

#include <iostream>  
#include <queue>  

int main() {  
    std::queue<int> numbers;  

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

    // 查看队头元素  
    std::cout << "队头元素：" << numbers.front() << std::endl; // 输出 10  

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

    // 再次查看队头元素  
    std::cout << "出队后队头元素：" << numbers.front() << std::endl; // 输出 20  

    // 查看队列长度  
    std::cout << "队列长度：" << numbers.size() << std::endl; // 输出 2  

    return 0;  
}

2.2 队列的底层实现

C++ 的 std::queue 默认使用 双端队列（deque） 作为其底层容器，但开发者也可以通过模板参数自定义容器类型。例如：

// 使用 vector 作为底层容器  
std::queue<int, std::vector<int>> vecQueue;  

// 使用 list 作为底层容器  
std::queue<int, std::list<int>> listQueue;

不过，大多数场景下无需修改默认实现，deque 在插入和删除操作上的高效性已能满足需求。

三、队列的进阶用法与技巧

3.1 优先队列（Priority Queue）

C++ 的 <queue> 头文件还提供了 std::priority_queue，它是一种特殊的队列，元素的出队顺序由优先级决定。例如：

#include <queue>  

int main() {  
    // 默认最大堆：元素按从大到小出队  
    std::priority_queue<int> maxHeap;  
    maxHeap.push(5);  
    maxHeap.push(3);  
    maxHeap.push(8);  

    // 队头是最大的元素  
    std::cout << maxHeap.top() << std::endl; // 输出 8  

    // 最小堆：通过自定义比较函数实现  
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;  
    minHeap.push(5);  
    minHeap.push(3);  
    minHeap.push(8);  
    std::cout << minHeap.top() << std::endl; // 输出 3  

    return 0;  
}

自定义比较函数

若要存储自定义类型的对象，需重载比较运算符或提供自定义的仿函数。例如：

struct Task {  
    int priority;  
    std::string description;  
};  

// 自定义比较函数，按优先级排序  
struct CompareTask {  
    bool operator()(const Task& a, const Task& b) {  
        return a.priority > b.priority; // 优先级低的先出队  
    }  
};  

int main() {  
    std::priority_queue<Task, std::vector<Task>, CompareTask> taskQueue;  
    // ...  
    return 0;  
}

3.2 队列的线程安全问题

在多线程环境下，直接操作 std::queue 可能引发竞态条件（Race Condition）。此时，可通过 std::mutex 或 std::lock_guard 实现同步。例如：

#include <queue>  
#include <mutex>  

std::queue<int> sharedQueue;  
std::mutex mtx;  

void enqueue(int value) {  
    std::lock_guard<std::mutex> lock(mtx);  
    sharedQueue.push(value);  
}  

void dequeue() {  
    std::lock_guard<std::mutex> lock(mtx);  
    if (!sharedQueue.empty()) {  
        sharedQueue.pop();  
    }  
}

四、实际应用场景与案例分析

4.1 广度优先搜索（BFS）

在图论中，BFS 需要按层遍历节点，队列是实现这一过程的核心工具。例如：

#include <queue>  
#include <vector>  

// 假设 graph 是一个邻接表表示的图  
std::vector<bool> visited(nodesCount, false);  
std::queue<int> bfsQueue;  

bfsQueue.push(startNode);  
visited[startNode] = true;  

while (!bfsQueue.empty()) {  
    int current = bfsQueue.front();  
    bfsQueue.pop();  

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

4.2 任务调度系统

假设需要设计一个任务队列，按优先级执行任务：

struct Task {  
    int priority;  
    std::string name;  
};  

// 使用优先队列实现任务调度  
std::priority_queue<Task, std::vector<Task>, CompareTask> taskQueue;  

// 添加任务  
taskQueue.push({2, "任务A"});  
taskQueue.push({1, "任务B"});  

// 执行任务  
while (!taskQueue.empty()) {  
    Task currentTask = taskQueue.top();  
    taskQueue.pop();  
    std::cout << "执行：" << currentTask.name << std::endl;  
}  
// 输出顺序：任务B（优先级1）先执行

五、常见问题与注意事项

5.1 队列与栈的区别

  • 队列（Queue）：先进先出（FIFO）。
  • 栈（Stack）：先进后出（LIFO）。
    两者应用场景不同：队列适合任务调度，栈适合回溯或表达式解析。

5.2 性能优化

  • 入队和出队操作的时间复杂度均为 O(1)，但频繁的 empty() 和 size() 可能影响性能。
  • 若需频繁遍历元素，建议改用 std::deque 或 std::list。

5.3 内存管理

队列的内存由底层容器动态管理，无需手动释放。但存储对象的生命周期需确保与队列一致，避免悬空指针。

结论

C++ 的 <queue> 容器类以其简洁的接口和高效的实现，成为解决 FIFO 问题的首选工具。从基础的 push 和 pop，到高级的优先队列和多线程同步，开发者可以灵活应对各类场景。通过本文的案例分析，读者应能掌握队列在算法设计和实际项目中的应用。

掌握 <queue> 并非终点，而是进一步探索 C++ 容器家族的起点。例如，std::deque 和 std::list 的特性，以及 <stack> 的用法，都值得深入研究。记住：选择合适的数据结构，往往能让代码事半功倍。

希望本文能助你在编程之路上更进一步！

最新发布

查看更多文章