个人主页：17_Kevin-CSDN博客
专栏：《数据结构》
一、队列的概念和结构
队列是只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
二、队列的操作
队列有以下几种常见的操作：
- 入队（Enqueue）：将一个元素添加到队尾。
- 出队（Dequeue）：从队头删除并返回一个元素。
- 查看队头元素（Front）：返回队头元素，但不删除它。
- 查看队尾元素（Rear）：返回队尾元素，但不删除它。
- 判断队列是否为空（Empty）：返回队列是否为空。
- 清空队列（Clear）：删除队列中的所有元素。
三、队列的实现
1. 实现方法的选择
队列可以使用多种数据结构来实现，如数组、链表等。
但是用链表实现队列效果更优，因为如果是数组的话，队列每次需要从头上出数据，这样就需要将数组后面的数据依次往前挪动，这样会增加时间复杂度，不如使用链表直接free掉队头数据快捷。
2. 代码实现
2.0 创建队列结构
typedef int QDataType; typedef struct QueueNode { int val; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue;
创建一个结构体类型QNode来作为队列中每个节点的数据存储结构体，用Queue作为存储队头和队尾还有队列长度的结构体类型。
2.1 初始化队列
void QueueInit(Queue* pq) { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; }
和链表的初始化大同小异。
2.2 队列的销毁
void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }
首先检查传入的pq队列是不是已经没有数据了，然后创建一个Queue类型的变量cur和next用来遍历销毁队列。在循环中用next来指向cur的下一个数据，然后free掉现在cur的数据，持续推动向前，一个接一个销毁。
在 while (cur) 循环结束后，cur 确实已经被设置为 NULL，但是将队列的头指针和尾指针都设置为 NULL 是为了确保队列的状态被正确地重置为空闲状态。
即使 cur 已经是 NULL，队列的其他成员变量（如 size）仍然可能包含不正确的值。通过将头指针和尾指针都设置为 NULL，可以确保队列被完全清空，并避免任何潜在的错误或未初始化的状态。
2.3 入队列
// 入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->val = x; newnode->next = NULL; if (pq->ptail) { pq->ptail->next = newnode;//将当前尾的next设置为newnode pq->ptail = newnode;//更新pq的尾节点，所以当前尾节点为newnode } else { pq->phead = pq->ptail = newnode; } pq->size++; }
在创建空间并分配后，根据队列的当前状态进行不同的操作。如果队列的尾指针 pq->ptail 不为 NULL，则将 newnode 插入到队列的尾部。首先，将 pq->ptail->next 设置为 newnode，将 newnode 连接到队列的尾部。然后，将 pq->ptail 更新为 newnode，以便后续的操作可以正确地找到队列的尾部。如果队列的尾指针为 NULL，表示队列为空，此时将 newnode 设置为队列的头指针和尾指针，即 pq->phead = pq->ptail = newnode。
2.4 出队列
// 出队列 void QueuePop(Queue* pq) { assert(pq); // 0个节点 // 温柔检查 //if (pq->phead == NULL) // return; // 暴力检查 assert(pq->phead != NULL); // 一个节点 // 多个节点 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--; }
2.5 返回队头数据
QDataType QueueFront(Queue* pq) { assert(pq); // 暴力检查 assert(pq->phead != NULL); return pq->phead->val; }
2.6 返回队尾数据
QDataType QueueBack(Queue* pq) { assert(pq); // 暴力检查 assert(pq->ptail != NULL); return pq->ptail->val; }
四、队列的应用场景
队列在计算机科学中有许多应用场景，以下是一些常见的例子：消息队列：在分布式系统中，消息队列用于在不同的进程或节点之间传递消息。
- 任务队列：在操作系统中，任务队列用于调度和执行任务。
- 缓冲区：在输入输出操作中，队列可以用作缓冲区，暂存输入数据或输出数据。
- 优先队列：优先队列是一种特殊的队列，其中元素按照某种优先级排序。在搜索引擎中，优先队列可以用于对搜索结果进行排序。
I'm Kevin, and we'll see you next time
