1 std::queue 应用于自定义数据结构
通常，std::queue 用于存储基本数据类型，如 int、float、char 等。然而，std::queue 同样可以存储自定义的数据结构，只要这些数据结构满足一定的要求。
（1）存储自定义数据结构的要求
要使自定义数据结构能够存储在 std::queue 中，该数据结构必须满足以下条件：
- 可复制性：自定义数据结构必须能够被复制。这意味着它必须有一个有效的复制构造函数和一个赋值运算符。当元素被压入队列或从队列中弹出时，会涉及到复制操作。
- 析构函数：自定义数据结构应该有一个合适的析构函数，以确保在元素从队列中删除时能够正确地释放资源。
（2）使用 std::queue 存储自定义数据结构
下面是一个简单的例子，展示了如何使用 std::queue 存储自定义的数据结构：
#include <iostream>
#include <queue>
#include <string>
// 自定义数据结构
struct MyData {
int id;
std::string name;
// 构造函数
MyData(int id, const std::string& name) : id(id), name(name) {}
// 输出数据结构的内容
void print() const {
std::cout << "ID: " << id << ", Name: " << name << std::endl;
}
};
int main()
{
// 创建一个存储 MyData 类型元素的队列
std::queue<MyData> dataqueue;
// 创建一些 MyData 对象并将其压入队列中
dataqueue.push(MyData(1, "Alice"));
dataqueue.push(MyData(2, "Bob"));
dataqueue.push(MyData(3, "Charlie"));
// 遍历队列并输出每个元素的内容
while (!dataqueue.empty()) {
MyData topData = dataqueue.front(); // 获取队列顶元素但不移除它
topData.print(); // 输出队列顶元素的内容
dataqueue.pop(); // 移除队列顶元素
}
return 0;
}
上面代码的输出为：
ID: 1, Name: Alice
ID: 2, Name: Bob
ID: 3, Name: Charlie
这个例子定义了一个名为 MyData 的自定义数据结构，它包含两个成员变量：id 和 name。然后，创建了一个 std::queue<MyData> 类型的队列，用于存储 MyData 对象。通过调用 push 方法将 MyData 对象压入队列中，并通过循环和 top、pop 方法遍历并输出队列中每个元素的内容。
（3）注意事项
- 内存管理：当自定义数据结构包含动态分配的内存（如指针、动态数组等）时，需要确保在复制和析构过程中正确地管理这些内存。
- 性能考虑：对于大型或复杂的自定义数据结构，频繁地复制元素可能会对性能产生显著影响。在这种情况下，可以考虑使用指针或智能指针（如 std::shared_ptr 或 std::unique_ptr）来存储数据结构的引用，而不是直接存储数据结构本身。
- 异常安全性：在自定义数据结构的复制构造函数和赋值运算符中，应确保操作是异常安全的，以避免在发生异常时导致资源泄漏或其他问题。
2 std::queue 的主要应用场景
下面是 std::queue 的一些主要应用场景：
（1）简单的消息队列：
在分布式系统或微服务架构中，消息队列用于在不同的服务或组件之间传递消息。虽然 std::queue 不适用于这种大规模或分布式场景，但在小型系统或原型中，它可以作为简单的消息队列使用。
（2）任务调度：
在多任务系统中，任务通常需要按照它们到达的顺序执行。std::queue 可以用来存储待执行的任务，并按照它们被添加的顺序来调度。
（3）广度优先搜索（BFS）：
在图的遍历算法中，广度优先搜索（BFS）是一种常见的策略。它逐层遍历图的所有节点，直到找到目标或遍历完所有节点。std::queue 是实现BFS的理想选择。
（4）线程安全的数据交换：
在多线程编程中，有时需要在不同的线程之间安全地传递数据。通过使用带有互斥锁的 std::queue，可以实现线程安全的数据交换。
（5）事件处理：
在事件驱动的系统（如GUI或游戏）中，事件（如点击、按键或定时事件）通常按照它们发生的顺序处理。std::queue 可以用来存储待处理的事件。
（6）缓冲区管理：
在数据处理或通信系统中，经常需要临时存储数据，等待进一步处理或传输。std::queue 可以用作这种临时存储的缓冲区。
2.1 std::queue 应用于简单的消息队列
尽管 std::queue 在分布式系统或微服务架构中并不是理想的消息队列解决方案，但在小型系统或原型中，它确实可以作为简单的消息队列使用。下面是一个简单的示例，展示了如何在小型系统中使用 std::queue 来模拟消息队列的行为。
#include <iostream>
#include <queue>
#include <mutex>
#include <condition_variable>
#include <thread>
#include <string>
// 定义消息类型
struct Message {
int id;
std::string content;
Message(int id, const std::string& content) : id(id), content(content) {}
};
// 简单的消息队列类
class SimpleMessageQueue {
public:
// 入队操作
void enqueue(const Message& message) {
std::lock_guard<std::mutex> lock(m_mutex);
m_queue.push(message);
m_cond_var.notify_one(); // 通知可能正在等待的消费者线程
}
// 出队操作
Message dequeue() {
std::unique_lock<std::mutex> lock(m_mutex);
m_cond_var.wait(lock, [this] { return !m_queue.empty(); }); // 等待队列不为空
Message message = m_queue.front();
m_queue.pop();
return message;
}
// 检查队列是否为空
bool empty() {
std::lock_guard<std::mutex> lock(m_mutex);
return m_queue.empty();
}
private:
std::queue<Message> m_queue;
std::mutex m_mutex;
std::condition_variable m_cond_var;
};
// 生产者线程函数
void producer(SimpleMessageQueue& queue) {
for (int i = 0; i < 6; ++i) {
Message message(i, "Message " + std::to_string(i));
queue.enqueue(message);
std::cout << "Produced message: " << message.content << std::endl;
std::this_thread::sleep_for(std::chrono::seconds(1)); // 模拟耗时操作
}
}
// 消费者线程函数
void consumer(SimpleMessageQueue& queue) {
while (true) {
if (!queue.empty()) {
Message message = queue.dequeue();
std::cout << "Consumed message: " << message.content << std::endl;
}
else {
std::this_thread::sleep_for(std::chrono::milliseconds(500)); // 等待一段时间再检查
}
}
}
int main()
{
SimpleMessageQueue messageQueue;
// 创建生产者线程和消费者线程
std::thread producerThread(producer, std::ref(messageQueue));
std::thread consumerThread(consumer, std::ref(messageQueue));
// 等待生产者线程完成
producerThread.join();
// 注意：在真实应用中，消费者线程通常不会在这里结束，它可能会一直运行，直到系统关闭。
// 在这个示例中，为了简单起见，我们让主线程等待消费者线程运行一段时间后结束。
std::this_thread::sleep_for(std::chrono::seconds(10)); // 让消费者线程有足够的时间处理消息
consumerThread.detach(); // 在这里分离消费者线程，让它在后台继续运行
return 0;
}
上面代码的输出为：
Produced message: Message 0Consumed message: Message 0
Produced message: Message 1
Consumed message: Message 1
Produced message: Message 2
Consumed message: Message 2
Produced message: Message 3
Consumed message: Message 3
Produced message: Message 4
Consumed message: Message 4
Produced message: Message 5
Consumed message: Message 5
上面的代码定义了一个 SimpleMessageQueue 类，它封装了 std::queue 并提供了线程安全的 enqueue 和 dequeue 方法。然后使用 std::mutex 来保护队列免受并发访问的影响，并使用 std::condition_variable 来在队列为空时阻塞消费者线程，并在有新消息时通知它们。
producer 函数模拟了生产者线程的行为，它生成消息并将其放入队列中。consumer 函数模拟了消费者线程的行为，它不断从队列中取出消息并处理它们。
在 main 函数中，创建了生产者线程和消费者线程，并让主线程等待生产者线程完成。注意，在真实的应用程序中，消费者线程通常会一直运行，直到系统关闭。在这个简单的示例中，为了演示目的，在主线程中等待一段时间后让消费者线程在后台继续运行。
2.2 std::queue 应用于任务调度
下面是一个使用 std::queue 来实现简单四则运算表达式求值的示例。这个示例将实现一个基本的计算器，能够处理加、减、乘、除四种运算。为了实现这个计算器，需要使用两个队列：一个用于存储操作数，另一个用于存储操作符。
#include <iostream>
#include <queue>
#include <thread>
#include <functional>
#include <mutex>
#include <condition_variable>
// 任务类型定义
using Task = std::function<void()>;
// 任务调度器类
class TaskScheduler {
public:
TaskScheduler() : m_stop(false) {}
// 添加任务到队列
void addTask(const Task& task) {
std::lock_guard<std::mutex> lock(m_mutex);
m_taskQueue.push(task);
m_condVar.notify_one(); // 通知可能正在等待的工作线程
}
// 从队列中获取并执行任务
void work() {
while (true) {
std::unique_lock<std::mutex> lock(m_mutex);
m_condVar.wait(lock, [this] { return !m_taskQueue.empty() || m_stop; });
if (m_stop) {
break; // 如果停止标志被设置，退出循环
}
Task task = std::move(m_taskQueue.front());
m_taskQueue.pop();
lock.unlock(); // 释放锁，以便其他线程可以添加任务
// 执行任务
task();
}
}
// 停止任务调度器
void stop() {
std::lock_guard<std::mutex> lock(m_mutex);
m_stop = true;
m_condVar.notify_all(); // 通知所有等待的线程
}
private:
std::queue<Task> m_taskQueue;
std::mutex m_mutex;
std::condition_variable m_condVar;
bool m_stop;
};
// 示例任务函数
void printTask(int id) {
std::cout << "Executing task " << id << std::endl;
}
int main()
{
TaskScheduler scheduler;
// 创建多个任务并添加到任务队列中
for (int i = 0; i < 10; ++i) {
int taskId = i;
Task task = [taskId]() { printTask(taskId); };
scheduler.addTask(task);
}
// 启动工作线程来执行任务
std::thread workerThread([&scheduler]() { scheduler.work(); });
// 让主线程等待一段时间，以便工作线程可以执行任务
std::this_thread::sleep_for(std::chrono::seconds(5));
// 停止任务调度器和工作线程
scheduler.stop();
workerThread.join();
return 0;
}
上面代码的输出为：
Executing task 0
Executing task 1
Executing task 2
Executing task 3
Executing task 4
Executing task 5
Executing task 6
Executing task 7
Executing task 8
Executing task 9
这个示例定义了一个 TaskScheduler 类，它包含一个 std::queue<Task> 来存储待执行的任务。addTask 方法用于将任务添加到队列中，并通知可能正在等待的工作线程。work 方法在一个单独的线程中运行，不断从队列中取出任务并执行它们。当 stop 方法被调用时，工作线程会退出循环并停止执行。
在 main 函数中，创建了一个 TaskScheduler 对象，并添加了多个任务到队列中。然后，启动了一个工作线程来执行这些任务。主线程等待一段时间以允许工作线程执行任务，然后调用 stop 方法来停止任务调度器和工作线程。
2.3 std::queue 应用于广度优先搜索（BFS）
在广度优先搜索（BFS）中，std::queue 是一个理想的数据结构，用于存储待访问的节点。以下是一个使用 std::queue 实现 BFS 的示例，它遍历一个无向图并打印出节点的访问顺序。
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
// 定义图的数据结构，使用邻接列表表示
vector<vector<int>> graph;
// BFS 函数
void bfs(int start) {
queue<int> q;
unordered_set<int> visited;
q.push(start); // 将起始节点加入队列
visited.insert(start); // 标记起始节点为已访问
while (!q.empty()) {
int current = q.front(); // 取出队列中的第一个节点
q.pop(); // 从队列中移除该节点
cout << current << " "; // 访问该节点
// 遍历当前节点的所有邻居
for (int neighbor : graph[current]) {
if (visited.find(neighbor) == visited.end()) {
q.push(neighbor); // 将未访问的邻居加入队列
visited.insert(neighbor); // 标记邻居为已访问
}
}
}
}
int main()
{
// 初始化图，假设有 5 个节点
int numNodes = 5;
graph.resize(numNodes);
// 添加边：0-1, 0-2, 1-2, 2-0, 2-3, 3-3
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(2);
graph[2].push_back(0);
graph[2].push_back(3);
graph[3].push_back(3); // 添加自环
// 从节点 0 开始 BFS
cout << "BFS traversal starting from node 0: ";
bfs(0);
cout << endl;
return 0;
}
上面代码的输出为：
BFS traversal starting from node 0: 0 1 2 3
这个示例首先创建了一个 graph 变量来表示图，然后使用 bfs 函数进行广度优先搜索。bfs 函数接收一个起始节点作为参数，并使用 std::queue<int> 来存储待访问的节点。同时，使用 std::unordered_set<int> 来跟踪已经访问过的节点，以避免重复访问。
在 bfs 函数中，首先将起始节点加入队列并标记为已访问。然后，进入一个循环，在该循环中，不断从队列中取出节点，访问它，并将其所有未访问的邻居加入队列。这个过程一直持续到队列为空，即所有可达的节点都被访问为止。
在 main 函数中，初始化了一个包含 5 个节点的图，并添加了一些边。然后，从节点 0 开始执行 BFS，并打印出节点的访问顺序。
3 实现一个简单的 std::queue 容器
下面是一个简单的 Myqueue 类的实现，它基于 std::list 作为底层容器。
#include <iostream>
#include <list>
#include <string>
#include <stdexcept>
template <typename T>
class SimpleQueue {
public:
// 判断队列是否为空
bool empty() const {
return elements.empty();
}
// 返回队列中元素的数量
size_t size() const {
return elements.size();
}
// 在队列尾部插入元素
void push(const T& value) {
elements.push_back(value);
}
// 从队列头部移除元素并返回它
T pop() {
if (elements.empty()) {
throw std::out_of_range("Queue is empty, cannot pop element.");
}
T frontElement = elements.front();
elements.pop_front();
return frontElement;
}
// 返回队列头部的元素（不移除）
T& front() {
if (elements.empty()) {
throw std::out_of_range("Queue is empty, cannot access front element.");
}
return elements.front();
}
// 返回队列头部的元素（不移除）的常量版本
const T& front() const {
if (elements.empty()) {
throw std::out_of_range("Queue is empty, cannot access front element.");
}
return elements.front();
}
// 返回队列尾部的元素（不移除）
T& back() {
if (elements.empty()) {
throw std::out_of_range("Queue is empty, cannot access back element.");
}
return elements.back();
}
// 返回队列尾部的元素（不移除）的常量版本
const T& back() const {
if (elements.empty()) {
throw std::out_of_range("Queue is empty, cannot access back element.");
}
return elements.back();
}
private:
std::list<T> elements;
};
int main()
{
SimpleQueue<int> queue;
// 添加元素到队列
queue.push(1);
queue.push(2);
queue.push(3);
// 访问队列头部元素
std::cout << "Front element: " << queue.front() << std::endl;
// 移除并返回队列头部元素
std::cout << "Popped element: " << queue.pop() << std::endl;
// 访问队列新的头部元素
std::cout << "New front element: " << queue.front() << std::endl;
// 检查队列是否为空
std::cout << "Is queue empty? " << (queue.empty() ? "Yes" : "No") << std::endl;
return 0;
}
上面代码的输出为：
Front element: 1
Popped element: 1
New front element: 2
Is queue empty? No
这个简单的 SimpleQueue 实现使用了 std::list 作为底层容器来存储元素。push 方法在列表的尾部添加元素，pop 方法从列表的头部移除元素，front 和 back 方法分别返回队列的头部和尾部元素。如果队列为空，这些方法会抛出 std::out_of_range 异常。