一.队列的概念
队列（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 <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> 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;
}
