C++ queue适配器先进先出队列实现

P粉602998670

发布时间：2025-08-21 12:16:02

480人浏览过

来源于php中文网

原创

std::queue是基于deque等容器的FIFO适配器，提供push、pop、front、back等操作，用于任务调度、BFS等场景，需手动实现线程安全。

c++ queue适配器先进先出队列实现

C++的

std::queue

是一个容器适配器，它提供了一种先进先出（FIFO）的数据结构，这意味着你放入的第一个元素，也将会是第一个被取出的。它本身不是一个独立的容器，而是通过封装其他序列容器（比如

std::deque

或

std::list

）来提供这种特定行为模式的接口。

要使用

std::queue

，你需要包含

头文件。它的基本操作直观且符合FIFO原则：

push()

用于在队尾添加元素，

pop()

用于移除队头元素，

front()

用于访问队头元素，而

back()

则用于访问队尾元素。此外，

empty()

可以检查队列是否为空，

size()

则返回队列中元素的数量。

#include 
#include 
#include 

int main() {
    std::queue messageQueue;

    // 模拟消息入队
    messageQueue.push("订单处理请求");
    messageQueue.push("用户登录事件");
    messageQueue.push("库存更新通知");

    std::cout << "队列当前大小: " << messageQueue.size() << std::endl;
    std::cout << "队头元素: " << messageQueue.front() << std::endl;
    std::cout << "队尾元素: " << messageQueue.back() << std::endl;

    // 模拟消息出队处理
    while (!messageQueue.empty()) {
        std::string currentMessage = messageQueue.front();
        messageQueue.pop();
        std::cout << "处理消息: " << currentMessage << std::endl;
    }

    std::cout << "队列是否为空? " << (messageQueue.empty() ? "是" : "否") << std::endl;

    return 0;
}

这个例子展示了

std::queue

如何模拟一个消息队列，新消息总是在队尾排队，而处理总是从队头开始。它默认使用

std::deque

作为其底层容器，因为

deque

在两端都有高效的插入和删除能力，这正是

queue

操作所需要的。

C++

std::queue

适配器的工作原理与底层容器选择

std::queue

的“适配器”本质，在我看来，是它设计上一个非常巧妙的地方。它不是自己管理内存或元素，而是像一个“壳”或者“包装器”，给底层的序列容器（比如

std::deque

或

std::list

）套上了一层特定的行为规范。说白了，它限制了你对底层容器的直接访问，只暴露了

push

（尾部插入）、

pop

（头部删除）、

front

（头部访问）和

back

（尾部访问）这些符合FIFO原则的操作。

立即学习“C++免费学习笔记（深入）”；

默认情况下，

std::queue

使用

std::deque

作为其底层容器。为什么是

deque

呢？

deque

（双端队列）的特点是它可以在两端（头部和尾部）都进行O(1)复杂度的插入和删除操作。这对于

queue

来说简直是完美匹配：

push

操作就是在

deque

的尾部添加，

pop

操作就是在

deque

的头部删除。如果换成

std::vector

，虽然尾部插入高效，但头部删除就需要移动所有后续元素，效率会很低。而

std::list

（双向链表）虽然在任意位置插入删除都是O(1)，但在内存布局上不如

deque

连续，这在某些场景下可能会有不同的缓存表现。所以，

std::deque

在性能和功能上为

std::queue

提供了非常平衡的默认选择。你当然可以显式指定

std::list

作为底层容器，比如

std::queue> myQueue;

，这通常在需要严格的O(1)插入/删除且不关心内存连续性时会考虑，或者在某些特定场景下，比如当元素数量非常庞大且频繁在两端操作，

list

能避免

deque

可能发生的内存重新分配。

在实际开发中，何时选择使用

std::queue

而非其他容器？

选择

std::queue

，通常是当你明确需要一个“排队”的逻辑时。它强制了先进先出的访问模式，这本身就是一种设计约束，避免了你意外地从队列中间或末尾取出元素，从而保证了业务逻辑的正确性。

在我日常的开发经验中，

std::queue

的典型应用场景包括：

Narration Box

Narration Box是一种语音生成服务，用户可以创建画外音、旁白、有声读物、音频页面、播客等

下载

任务调度与消息队列：这是最常见的应用。比如，一个服务器接收到很多待处理的请求（如日志写入、数据同步、异步计算），可以把这些请求封装成任务，然后放入一个
```
std::queue
```
中。后台的工作线程则不断从队列头部取出任务并执行。这确保了任务按照接收的顺序被处理。
广度优先搜索（BFS）：在图算法中，BFS需要从一个节点开始，先访问所有邻居节点，再访问邻居的邻居，以此类推。
```
std::queue
```
在这里扮演了关键角色，它存储了待访问的节点，并保证了“先发现的先访问”的顺序。
事件处理系统：当系统中有多个事件源产生事件，并且这些事件需要按时间顺序或生成顺序被处理时，
```
std::queue
```
可以用来缓冲这些事件。
打印队列或下载队列：想象一下，你发送了多个打印任务，或者下载多个文件，这些任务通常会按照提交的顺序排队等待处理。

相比于

std::vector

或

std::list

，

std::queue

的优势在于其语义的明确性。

std::vector

虽然可以模拟队列，但你需要手动管理头部元素的删除（这通常效率不高），而且它允许你进行随机访问，这可能会引入不符合FIFO逻辑的错误。

std::list

虽然在两端操作高效，但其语义是通用的链表，同样需要你手动维护FIFO的逻辑。

std::queue

通过其适配器特性，直接提供了这种“排队”的抽象，让代码意图更加清晰，也降低了误用的风险。

C++

std::queue

在并发编程中的应用与线程安全问题

当谈到

std::queue

在多线程环境下的应用时，一个核心且必须注意的问题就是线程安全性。标准库中的

std::queue

，就像大多数其他容器一样，本身并不是线程安全的。这意味着，如果在多个线程中同时对同一个

std::queue

实例进行

push

、

pop

、

front

、

back

等操作，就可能发生数据竞争（data race），导致未定义行为。这包括数据损坏、程序崩溃，或者更隐蔽的逻辑错误。

想象一下，两个线程同时尝试从一个只有一个元素的队列中

pop

，或者一个线程在

push

，另一个线程在

pop

，这些操作如果不加保护，很可能会导致内部状态（比如底层容器的大小、指针）出现不一致。

要在并发环境中使用

std::queue

，你必须手动实现同步机制来保护它。最常见的方法是使用互斥量（

std::mutex

）来保护对队列的访问，并结合条件变量（

std::condition_variable

）来处理生产者-消费者模式中的等待/通知机制。

一个典型的线程安全队列的实现思路是：

封装
std::queue
：创建一个新的类，内部包含一个
```
std::queue
```
实例。
互斥量保护：为这个新类的所有涉及
```
std::queue
```
操作的成员函数（如
```
push
```
、
```
pop
```
、
```
empty
```
、
```
size
```
等）加上互斥量（
```
std::mutex
```
）的锁。例如，在
```
push
```
之前加锁，操作完成后解锁。
条件变量：在消费者线程尝试
```
pop
```
时，如果队列为空，它需要等待生产者线程
```
push
```
新元素。这时，可以使用
```
std::condition_variable
```
让消费者线程进入等待状态，直到生产者线程通知有新元素可用。同样，如果队列有容量限制，生产者在队列满时也可能需要等待消费者
```
pop
```
。