编辑“︁C++queue”︁

{{DISPLAYTITLE:C++ queue}}  
[[Category:C++ STL容器]]  

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

队列的典型应用场景包括：  
* 任务调度（如打印任务队列）  
* 广度优先搜索（BFS）算法  
* 消息传递系统  

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

{| class="wikitable"  
! 操作 !! 描述 !! 示例  
|-  
| <code>push()</code> || 在队尾插入元素 || <code>q.push(10)</code>  
|-  
| <code>pop()</code> || 移除队首元素 || <code>q.pop()</code>  
|-  
| <code>front()</code> || 访问队首元素 || <code>int x = q.front()</code>  
|-  
| <code>back()</code> || 访问队尾元素 || <code>int y = q.back()</code>  
|-  
| <code>empty()</code> || 检查队列是否为空 || <code>if (q.empty())</code>  
|-  
| <code>size()</code> || 返回元素数量 || <code>int n = q.size()</code>  
|}  

== 代码示例 ==  
=== 基础用法 ===  
<syntaxhighlight lang="cpp">  
#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;  
}  
</syntaxhighlight>  

=== 实际案例：模拟打印机任务 ===  
<syntaxhighlight lang="cpp">  
#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;  
}  
</syntaxhighlight>  

== 底层实现与性能 ==  
队列默认基于<code>std::deque</code>实现，但可通过模板参数指定底层容器：  
<syntaxhighlight lang="cpp">  
#include <list>  
std::queue<int, std::list<int>> customQueue;  
</syntaxhighlight>  

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

== 队列可视化 ==  
<mermaid>  
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;  
</mermaid>  
* 紫色方块为队首（<code>front()</code>）  
* 蓝色方块为队尾（<code>back()</code>）  

== 数学表示 ==  
队列操作可形式化为：  
* 插入：<math>Q \leftarrow Q \cup \{x\}</math>  
* 删除：<math>Q \leftarrow Q \setminus \{\text{front}(Q)\}</math>  

== 常见问题 ==  
=== 如何清空队列？ ===  
<syntaxhighlight lang="cpp">  
std::queue<int> q;  
// 方法1：循环弹出  
while (!q.empty()) q.pop();  

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

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

== 进阶应用 ==  
=== 优先队列（priority_queue） ===  
虽然名称相似，但<code>priority_queue</code>是堆结构，遵循优先级而非FIFO。  

=== 线程安全队列 ===  
多线程环境下需自行实现锁机制或使用<code>std::mutex</code>。  

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

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 容器]]