C++数据结构学习之队列的应用(C++数据结构入门：队列的实际应用解析)

原创

ithorizon 6个月前 (10-20) 阅读数 16 #后端开发

C++数据结构学习之队列的应用

一、引言

在C++数据结构的学习过程中，队列是一种非常基础且重要的数据结构。它遵循先进先出（First In First Out，FIFO）的原则，广泛应用于日常编程和算法设计中。本文将详细介绍队列的基本概念，并通过实际应用场景来解析队列的使用方法。

二、队列的基本概念

队列是一种线性表，它只允许在表的一端插入元素，在另一端删除元素。在队列中，允许插入元素的一端称为队尾（Rear），允许删除元素的一端称为队头（Front）。当队列中没有元素时，称为空队列。

三、队列的ADT定义

以下是队列的抽象数据类型（ADT）定义：


template 
class Queue {
public:
    Queue(int size); // 构造函数
    ~Queue(); // 析构函数
    bool isEmpty() const; // 判断队列是否为空
    bool isFull() const; // 判断队列是否已满
    void enqueue(const T& item); // 入队操作
    T dequeue(); // 出队操作
    T getFront() const; // 获取队头元素
    T getRear() const; // 获取队尾元素
private:
    T* data; // 存储队列元素的数组
    int front; // 队头指针
    int rear; // 队尾指针
    int maxSize; // 队列的最大容量
};

四、队列的实际应用场景

1. 消息队列

消息队列是一种常见的应用场景，用于在进程或线程之间传递消息。以下是使用队列实现消息队列的一个易懂例子：


#include 
#include 
#include 
using namespace std;
void processMessage(queue& msgQueue) {
    while (!msgQueue.empty()) {
        string msg = msgQueue.front();
        msgQueue.pop();
        cout << "Processing message: " << msg << endl;
    }
}
int main() {
    queue msgQueue;
    msgQueue.push("Hello");
    msgQueue.push("World");
    msgQueue.push("!");
    processMessage(msgQueue);
    return 0;
}

2. 线程同步

在多线程编程中，队列常用于线程间的同步。以下是一个使用队列实现生产者-消费者模型的例子：


#include 
#include 
#include 
#include 
#include 
using namespace std;
queue taskQueue;
mutex queueMutex;
condition_variable queueCondVar;
void producer() {
    for (int i = 0; i < 10; ++i) {
        unique_lock lock(queueMutex);
        taskQueue.push(i);
        cout << "Produced: " << i << endl;
        lock.unlock();
        queueCondVar.notify_one();
    }
}
void consumer() {
    unique_lock lock(queueMutex);
    while (true) {
        while (taskQueue.empty()) {
            queueCondVar.wait(lock);
        }
        int task = taskQueue.front();
        taskQueue.pop();
        cout << "Consumed: " << task << endl;
        lock.unlock();
    }
}
int main() {
    thread producerThread(producer);
    thread consumerThread(consumer);
    producerThread.join();
    consumerThread.join();
    return 0;
}

3. 广度优先搜索（BFS）

广度优先搜索是一种图遍历算法，它使用队列来存储待遍历的节点。以下是一个使用队列实现广度优先搜索的例子：


#include 
#include 
#include 
using namespace std;
void bfs(int startNode, const vector>& graph) {
    vector visited(graph.size(), false);
    queue nodeQueue;
    visited[startNode] = true;
    nodeQueue.push(startNode);
    while (!nodeQueue.empty()) {
        int currentNode = nodeQueue.front();
        nodeQueue.pop();
        cout << "Visited: " << currentNode << endl;
        for (int neighbor : graph[currentNode]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                nodeQueue.push(neighbor);
            }
        }
    }
}
int main() {
    vector> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 4},
        {1, 5},
        {1, 2, 6},
        {3},
        {3},
        {4}
    };
    bfs(0, graph);
    return 0;
}