1. Queue

在 C++ 编程世界里，标准模板库（STL）宛如一座宝库，为开发者们提供了丰富且强大的数据结构与算法工具。其中，queue 作为一种特殊的数据结构，在众多场景中扮演着不可或缺的角色。本文将深入剖析 queue 的特性、底层实现、操作方法以及应用场景，帮助读者全面掌握这一重要工具。

1.1 概述

queue，即队列，是一种遵循先进先出（First In First Out，FIFO）原则的数据结构。想象一下在银行排队办理业务的场景，先到的顾客先接受服务，后到的顾客依次排队等待。在 queue 中，数据的插入操作（enqueue）在队列的一端（通常称为队尾）进行，而数据的移除操作（dequeue）则在队列的另一端（队首）进行。这就意味着最早进入队列的元素会最早被取出处理。

在 C++ STL 中，queue 被实现为一个容器适配器。所谓容器适配器，是基于其他基础容器（如 deque、list 等）构建而成，通过对基础容器的接口进行封装和限制，使其呈现出特定数据结构的行为。queue 正是利用这种方式，将基础容器转换为符合先进先出特性的队列结构。

欲使用queue，必须包含<queue>头文件

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

1.2 基本操作

使用 queue 之前，需要包含头文件。一旦引入，就可以轻松创建 queue 对象并使用其丰富的操作接口。

创建 queue 对象：

std::queue<int> q; // 创建一个存储整数的queue

元素入队（push）：push操作将元素添加到队列的尾部。

q.push(10);
q.push(20);

此时，queue q 中包含两个元素，队首为 10，队尾为 20。

元素出队（pop）：pop操作移除队列头部的元素，但该操作并不返回被移除的元素。

q.pop();

执行上述代码后，10 从队列中被移除，此时队首元素变为 20。

访问队首元素（front）：front操作返回队列头部元素的引用，但不会移除该元素。使用前需确保队列非空，否则行为未定义。

int frontElement = q.front(); // frontElement为20

访问队尾元素（back）：back操作返回队列尾部元素的引用，同样不会移除该元素，使用前提也是队列非空。

int backElement = q.back(); // backElement为20

判断队列是否为空（empty）：empty操作检查队列是否为空，若为空返回true，否则返回false。

bool isEmpty = q.empty(); // 若q为空，isEmpty为true，否则为false

获取队列元素个数（size）：size操作返回队列中元素的数量。

size_t queueSize = q.size(); // queueSize为当前队列中元素的个数

1.3 queue 的底层数据结构

STL 中的 queue 默认以 deque（双端队列）作为底层数据结构。从 queue 的定义中可以清晰看出这一点：

template<class _Ty, class _Container = deque<_Ty> >
class queue {
    ...
}

其中，_Ty表示存储元素的类型，_Container表示底层容器类型，默认情况下为deque<_Ty>。

选择 deque 作为默认底层结构主要基于以下原因：

操作效率：deque 在两端进行插入和删除操作的时间复杂度均为 O (1)，这与 queue 在队首移除元素、队尾添加元素的操作需求高度契合。例如，push操作对应 deque 的push_back，pop操作对应 deque 的pop_front，都能高效完成，无需大量元素移动。
内存管理：deque 具有灵活的内存管理机制，它可以动态地增长和收缩，能够很好地适应 queue 中元素数量不断变化的情况。与 vector 不同，vector 在扩容时可能需要重新分配内存并复制大量元素，而 deque 避免了这种高开销的操作。
功能适配：queue 只需要在两端进行操作，并不需要随机访问等复杂功能。deque 虽然在随机访问性能上不如 vector，但对于 queue 的功能需求而言，完全能够满足。而且，由于 queue 本身不允许遍历操作，deque 在遍历性能方面的劣势也就无关紧要了。

除了 deque，理论上只要满足front()、back()、push_back()和pop_front()操作的容器，都可以作为 queue 的底层容器，如 list。不过在实际应用中，使用 list 作为底层容器的情况相对较少。因为 list 每个节点都需要额外的指针空间来维护链表结构，导致内存开销较大，而且在一些性能敏感的场景下，其操作效率可能不如 deque。

1.4 以 list 作为 queue 的底层结构示例

尽管 deque 是 queue 的默认底层容器，但开发者也可以根据具体需求选择其他合适的容器。下面来看一下如何使用 list 作为 queue 的底层结构：

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

int main() {
    std::queue<int, std::list<int>> q;
    q.push(1);
    q.push(2);

    std::wcout << q.size() << std::endl; // 输出2
    std::wcout << q.front() << std::endl; // 输出1

    q.pop();
    std::wcout << q.front() << std::endl; // 输出2

    return 0;
}

在上述代码中，声明了一个以std::list为底层容器的std::queue对象q。通过push操作向队列中添加元素，使用size获取队列中元素的数量，利用front访问队首元素，最后通过pop移除队首元素。

使用 list 作为底层容器在某些特定场景下具有优势。例如，当需要频繁进行插入和删除操作，并且元素数量不确定时，list 的动态内存管理和无需连续内存空间的特性能够有效避免内存碎片化和频繁的内存分配问题。然而，由于 list 的元素在内存中不是连续存储的，其访问效率相对较低，在需要高效随机访问元素的场景中并不适用。

1.5 应用场景

queue 作为一种重要的数据结构，在实际编程中有广泛的应用，以下是一些常见的场景：

任务调度：在多任务处理系统中，任务调度器通常使用 queue 来管理任务。新提交的任务被添加到队列的末尾，而处理器则从队列的头部依次取出任务并执行。这样可以确保任务按照提交的顺序依次得到处理，实现公平的调度策略。例如，在一个操作系统中，多个用户进程的执行请求可以被放入一个任务队列，操作系统内核按照队列顺序为各个进程分配 CPU 资源，保证每个进程都能有机会运行。
消息传递：在分布式系统或多线程应用程序中，queue 常用于不同组件或线程之间的消息传递。一个组件将消息放入队列，另一个组件从队列中取出消息进行处理。这种方式能够有效解耦不同组件之间的依赖关系，提高系统的可扩展性和稳定性。以一个简单的聊天应用为例，用户发送的聊天消息可以被放入一个消息队列，服务器端的消息处理线程从队列中取出消息，进行验证、存储和转发给其他用户，确保消息按照发送的顺序进行处理，避免消息乱序导致的逻辑错误。
广度优先搜索（BFS）：在图和树的遍历算法中，广度优先搜索是一种常用的策略，而 queue 正是实现 BFS 的关键数据结构。从起始节点开始，将其邻居节点放入队列，然后依次处理队列中的节点，将它们未访问过的邻居节点继续放入队列。通过这种方式，可以按照层次顺序遍历图或树中的节点。比如在一个迷宫游戏中，使用广度优先搜索算法来寻找从起点到终点的最短路径。将起点位置放入队列，然后逐步探索周围的位置，将新发现的未访问位置加入队列，直到找到终点。在这个过程中，queue 保证了搜索按照距离起点由近及远的顺序进行，从而能够快速找到最短路径。
打印任务管理：在打印系统中，多个用户提交的打印任务会被放入一个打印队列。打印机按照任务在队列中的顺序依次进行打印，确保每个打印任务都能得到公平的处理，避免某些任务长时间等待而导致用户体验不佳。例如，在一个办公室网络环境中，多台电脑连接到一台共享打印机，用户在各自电脑上发起打印请求后，这些请求会被排队放入打印机的任务队列，打印机依次从队列中取出任务并执行打印操作。
事件处理：在图形用户界面（GUI）应用程序中，用户的各种操作（如鼠标点击、键盘输入等）都会被视为事件，并放入一个事件队列中。应用程序的主循环不断从队列中取出事件并进行相应的处理，响应用户的操作。例如，当用户点击一个按钮时，这个点击事件会被放入事件队列，主循环在下次迭代时取出该事件，并调用预先定义好的按钮点击处理函数，实现对用户操作的响应，保证用户交互的流畅性和实时性。
缓存数据：queue 可以作为一种数据缓存机制，用于存储临时数据。在生产者 - 消费者模型中，生产者生成的数据被放入队列，消费者从队列中取出数据进行处理。这种方式能够平衡生产者和消费者的处理速度差异，提高系统的整体性能。例如，在一个视频处理系统中，视频采集模块作为生产者不断将采集到的视频帧放入队列，而视频编码模块作为消费者从队列中取出帧进行编码处理。由于视频采集和编码的速度可能不同，通过队列作为缓存可以有效协调两者之间的工作节奏，避免数据丢失或处理不及时的问题。