数据结构界的三大幻神----队列
一.队列的概念
队列（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;
}