C语言 c++ 数据结构界的三大幻神----队列

一.队列的概念

队列（Queue）是一种常见的线性数据结构，它遵循先进先出（First-In, First-Out，FIFO）的原则 就像排队等待服务的人一样，先到的人先得到服务。   队列的基本操作包括入队（Enqueue）和出队（Dequeue）。入队就是将元素添加到队列的尾部，出队则是从队列的头部取出元素。   队列在很多实际场景中都有应用，比如消息队列、任务队列、乘客排队等。它的优势在于能够高效地进行入队和出队操作，而且入队和出队的时间复杂度都是 O(1)。   在实现队列时，可以使用数组或链表来存储元素。使用数组实现的队列称为顺序队列，而使用链表实现的队列称为链式队列。   例如，在多线程编程中，任务队列可以用于协调线程之间的工作分配。线程将任务放入队列中，其他线程从队列中取出任务并执行。

好的~队列（Queue）是一种常见的数据结构，它遵循“先进先出”（First In, First Out，FIFO）的原则。就像在排队时，先到的人先得到服务。   队列可以想象成一个管子，元素从一端进入，另一端出去。新元素被添加到队列的尾部，而从队列中取出元素时，总是从头部开始。   在编程中，队列通常由数组或链表实现。队列的基本操作包括：  - 入队（Enqueue）：将一个元素添加到队列的尾部。- 出队（Dequeue）：从队列的头部移除并返回一个元素。- 查看队列头部元素：获取队列头部的元素，但不移除它。   队列在很多场景中都有应用，比如：   - 消息队列：在多线程或多进程环境中，用于消息的传递和处理。 - 打印任务队列：打印机按照任务进入队列的顺序进行打印。 - CPU 任务调度：操作系统中的进程调度器可以使用队列来管理等待执行的任务。

二.如何使用队列协调线程

在多线程编程中，使用队列来协调线程之间的工作分配是一种常见的方法。以下是一般的步骤：  1. 创建一个队列：使用适当的数据结构（如链表或数组）创建一个队列，用于存储待处理的任务。2. 任务入队：将需要处理的任务添加到队列的尾部。这可以由一个或多个线程负责完成。3. 线程等待任务：每个线程可以通过循环等待队列不为空，然后从队列的头部取出任务进行处理。4. 任务出队和处理：当线程获取到任务后，从队列中出队，并执行相应的处理逻辑。5. 处理完成后任务入队：线程在完成任务处理后，可以将结果或其他相关信息重新入队，以便其他线程可以获取和处理。 通过这种方式，线程之间可以通过队列来协调工作分配，实现任务的异步处理和并发执行 队列提供了一种简单而有效的方式来传递任务，使线程可以按照先进先出的顺序处理任务。   在实际实现中，还需要注意线程安全和并发控制的问题，例如使用锁或其他同步机制来确保队列的操作是线程安全的。此外，根据具体的需求，还可以对队列进行一些扩展，如添加优先级排序、任务依赖等功能。

三.手撕队列

#include #include #include #include typedef int QueueData; typedef struct QueueNode {     QueueData data;     struct QueueNode* next; }QNode; //可以用带头链表，也可以传入二级指针 typedef struct Queue {     struct QueueNode* phead;     struct QueueNode* ptail;     int size; }Queue; //队列的初始化 void initQueue(Queue* pq) {     assert(pq);     pq->phead = pq->ptail = NULL;     pq->size = 0; } //队列的销毁 void destroyQueue(Queue* pq) {     assert(pq);     assert(pq->phead);     QNode* cur = pq->phead;     while (cur)     {         QNode* next = cur->next;         free(cur);         cur = next;     } } //建立节点 QNode* createQNode(QueueData data) {     QNode* pcur = (QNode*)malloc(sizeof(QNode));     if (pcur == NULL)         perror("malloc fail");     else     {         pcur->data = data;         pcur->next = NULL;     }     return pcur; } //插入元素 void pushQueue(Queue* pq, QueueData data) {     assert(pq);     QNode* newNode = createQNode(data);     if (pq->phead == NULL)         pq->phead = pq->ptail = newNode;     else     {         pq->ptail->next = newNode;         pq->ptail = pq->ptail->next;     }     pq->size++; } //删除元素 void popQueue(Queue* pq) {     assert(pq);     assert(pq->phead);     if (pq->phead->next == NULL)     {         free(pq->phead);         pq->phead = pq->ptail = NULL;     }     else     {         QNode* next = pq->phead->next;         free(pq->phead);         pq->phead = next;     }     pq->size--; } //取出队首元素 QueueData frontQueue(Queue* pq) {     assert(pq);     assert(pq->phead);     return pq->phead->data; } //取出队尾元素 QueueData backQueue(Queue* pq) {     assert(pq);     assert(pq->phead);     return pq->ptail->data; } //计算队列长度 int sizeQueue(Queue* pq) {     assert(pq);     return pq->size; } bool isEmpty(Queue* pq) {     assert(pq);     return !pq->phead; } void printQueue(Queue* pq) {     assert(pq);     QNode* cur = pq->phead;     while (cur)     {         printf("%d ", cur->data);         cur = cur->next;     } } int main() {     Queue pq;     initQueue(&pq);     pushQueue(&pq, 1);     pushQueue(&pq, 2);     pushQueue(&pq, 3);     pushQueue(&pq, 4);     printQueue(&pq);     return 0; }

参考阅读