C++queue

简介

C++ queue（队列）是C++标准模板库（STL）中的一种容器适配器，它遵循**先进先出**（FIFO, First-In-First-Out）原则。队列在底层通常基于deque或list实现，但用户无需关心具体实现细节，只需通过接口操作数据。

队列的典型应用场景包括：

• 任务调度（如打印任务队列）
• 广度优先搜索（BFS）算法
• 消息传递系统

基本操作

队列提供以下核心操作（时间复杂度均为 O(1)）：

操作	描述	示例
push()	在队尾插入元素	q.push(10)
pop()	移除队首元素	q.pop()
front()	访问队首元素	int x = q.front()
back()	访问队尾元素	int y = q.back()
empty()	检查队列是否为空	if (q.empty())
size()	返回元素数量	int n = q.size()

代码示例

基础用法

  
#include <iostream>  
#include <queue>  

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

    // 插入元素  
    q.push(1);  
    q.push(2);  
    q.push(3);  

    // 访问元素  
    std::cout << "队首元素: " << q.front() << "\n";  // 输出 1  
    std::cout << "队尾元素: " << q.back() << "\n";   // 输出 3  

    // 移除元素  
    q.pop();  
    std::cout << "弹出后队首: " << q.front() << "\n"; // 输出 2  

    // 遍历队列（需边遍历边弹出）  
    while (!q.empty()) {  
        std::cout << q.front() << " ";  
        q.pop();  
    }  
    // 输出: 2 3  
    return 0;  
}

实际案例：模拟打印机任务

  
#include <queue>  
#include <string>  

struct PrintJob {  
    std::string filename;  
    int pages;  
};  

int main() {  
    std::queue<PrintJob> printerQueue;  

    // 添加打印任务  
    printerQueue.push({"report.pdf", 5});  
    printerQueue.push({"invoice.docx", 2});  

    // 处理任务  
    while (!printerQueue.empty()) {  
        auto job = printerQueue.front();  
        std::cout << "正在打印: " << job.filename  
                  << " (页数: " << job.pages << ")\n";  
        printerQueue.pop();  
    }  
    return 0;  
}

底层实现与性能

队列默认基于std::deque实现，但可通过模板参数指定底层容器：

  
#include <list>  
std::queue<int, std::list<int>> customQueue;

性能对比：

• deque（默认）：随机访问性能好，但内存非连续
• list：插入/删除稳定，但内存开销较大

队列可视化

graph LR A[元素1] --> B[元素2] --> C[元素3] style A fill:#f9f,stroke:#333 style C fill:#bbf,stroke:#333 classDef default text-align:center;

• 紫色方块为队首（front()）
• 蓝色方块为队尾（back()）

数学表示

队列操作可形式化为：

• 插入：$Q\leftarrow Q\cup \{x\}$
• 删除：$Q\leftarrow Q\setminus \{\text{front}(Q)\}$

常见问题

如何清空队列？

  
std::queue<int> q;  
// 方法1：循环弹出  
while (!q.empty()) q.pop();  

// 方法2：交换空队列（C++11起）  
std::queue<int>().swap(q);

为什么没有迭代器？

队列设计为限制性数据结构，禁止随机访问以保持FIFO特性。如需遍历，需临时复制或使用其他容器。

进阶应用

优先队列（priority_queue）

虽然名称相似，但priority_queue是堆结构，遵循优先级而非FIFO。

线程安全队列

多线程环境下需自行实现锁机制或使用std::mutex。

总结

• 队列是FIFO结构的典型代表
• 适用于需要顺序处理的场景
• 所有操作均保证常数时间复杂度
• 实际开发中优先考虑STL而非手动实现