C++ 标准模板库（STL）中的容器适配器（container adapter），它提供先进先出（FIFO，First-In-First-Out） 的数据结构

Cstd::queue详解std::queue是 C 标准模板库STL中的容器适配器container adapter它提供先进先出FIFOFirst-In-First-Out的数据结构。队列常用于广度优先搜索BFS、任务调度、消息队列等场景。1. 基本概念FIFO最先进入队列的元素最先被取出。std::queue不是一个独立的容器而是基于其他容器实现的适配器。默认底层容器std::deque双端队列因为它在头部删除和尾部插入都非常高效O(1)。你也可以指定其他底层容器如std::list或std::vector但需满足特定要求支持front()、back()、push_back()、pop_front()等。2. 头文件与命名空间#includequeue// 必须包含#includedeque// 默认底层容器#includelist// 可选#includevector// 可选不推荐作为 queue 的底层usingnamespacestd;3. 声明方式// 最常用queueintq;// 存储 int 的队列默认 dequequeuestring,dequestringq1;// 显式指定底层容器queueint,listintq2;// 使用 list 作为底层容器queuedouble,vectordoubleq3;// vector 也可以但 pop_front 效率低模板参数queueT, Container dequeT4. 常用成员函数时间复杂度均为 O(1)函数功能返回值注意事项push(val)从队尾插入元素void-emplace(...)原地构造元素C11void比 push 更高效pop()删除队头元素void不返回元素front()返回队头元素的引用T / const T队列为空时未定义行为back()返回队尾元素的引用T / const T队列为空时未定义行为empty()判断队列是否为空bool-size()返回队列中元素个数size_t-swap(q2)与另一个 queue 交换内容voidC11注意pop()不会返回被删除的元素如果你需要取出元素必须先front()再pop()。访问front()/back()前必须确保!empty()否则是未定义行为可能崩溃。5. 完整代码示例示例 1基础使用#includeiostream#includequeue#includestringusingnamespacestd;intmain(){queuestringq;// 入队q.push(任务1);q.push(任务2);q.emplace(任务3);// C11更推荐cout队列大小: q.size()endl;// 3cout队头元素: q.front()endl;// 任务1cout队尾元素: q.back()endl;// 任务3// 出队while(!q.empty()){cout处理: q.front()endl;q.pop();}cout队列是否为空: (q.empty()?是:否)endl;return0;}示例 2BFS广度优先搜索经典应用#includeiostream#includequeue#includevectorusingnamespacestd;vectorvectorintgraph{{1,2},// 0 的邻居{0,3},// 1 的邻居{0,3},// 2 的邻居{1,2,4},// 3 的邻居{3}// 4 的邻居};voidbfs(intstart){vectorboolvisited(graph.size(),false);queueintq;q.push(start);visited[start]true;while(!q.empty()){intuq.front();q.pop();coutu ;for(intv:graph[u]){if(!visited[v]){visited[v]true;q.push(v);}}}}intmain(){coutBFS 遍历顺序: ;bfs(0);coutendl;return0;}示例 3自定义底层容器 自定义类型#includeiostream#includequeue#includelistusingnamespacestd;structTask{intpriority;string name;};intmain(){// 使用 list 作为底层容器queueTask,listTasktasks;tasks.push({1,低优先任务});tasks.push({3,高优先任务});while(!tasks.empty()){Task ttasks.front();cout执行任务: t.name (优先级 t.priority)\n;tasks.pop();}}6.std::priority_queue优先队列如果你需要按优先级出队而不是严格 FIFO请使用priority_queue默认是大根堆#includequeuepriority_queueintpq;// 大根堆priority_queueint,vectorint,greaterintpq_min;// 小根堆// 自定义比较structCompare{booloperator()(constTaska,constTaskb){returna.priorityb.priority;// 优先级高的先出}};priority_queueTask,vectorTask,Comparetask_pq;7. 注意事项与最佳实践线程安全STL 的queue不是线程安全的多线程环境下需要自己加锁。性能默认deque是最佳选择vector作为底层时pop会低效。异常安全push/emplace可能抛出异常pop、front等通常不抛出。C11 改进emplace、swap、移动语义支持更好。清空队列没有clear()可以用while(!empty()) pop();或交换一个空队列。queueintempty_q;q.swap(empty_q);// 快速清空8. 总结普通队列用std::queueFIFO带优先级用std::priority_queue环形缓冲考虑std::deque或 boost::circular_buffer并发队列生产环境推荐使用线程安全的实现如tbb::concurrent_queue或自己封装需要更深入的内容如队列的底层实现原理、与deque的源码对比、或在 LeetCode 中的应用随时告诉我