当前位置：首页 > news >正文

【数据结构】队列(Queue)实现详解

news 2025/7/20 6:38:16

🚩纸上得来终觉浅，绝知此事要躬行。
🌟主页：June-Frost
🚀专栏：数据结构

🔥该文章主要了解实现队列的相关操作。

🌍 队列

🔭概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 的特性。进行插入操作的一端称为队尾，进行删除操作的一端称为队头。

🔭结构

队列的底层实现如果使用数组，虽然插入操作很容易，但是在删除操作的时候就需要不断覆盖数据，效率不太高。所以，队列更适合使用单链表结构实现。对于尾插，只需要定义一个尾指针就可以规避遍历，而且队列的操作中也不需要去找前一个节点，所以单向链表就足以实现队列。

🔭 应用场景

队列的应用场景包括许多方面：

公平性排队：
队列主要用于确保所有的请求或等待者都能得到平等和公正的服务。例如，在银行或政府部门，所有人都需要按顺序办理业务，而不是先到先得或者根据个人地位或身份进行优先办理。通过队列，每个人都可以在公平的环境中办理业务，而不必担心由于其他因素导致的歧视或不公平待遇。此外，在需要分配资源或任务的情况下，队列也可以保证资源的公平分配和任务的合理安排。
BFS （广度优先遍历）
BFS是一种用于遍历或搜索树或图的算法，它从根节点开始，沿着树的宽度遍历树的节点，直到找到目标节点或发现所有节点都被遍历过。在BFS过程中，队列用于存储待处理的节点，并按照先进先出的原则依次处理每个节点。这种算法在解决图论问题时非常常见，如找到两个节点之间的最短路径、检测图是否连通、搜索图中的环等。
流量削锋
在某些情况下，例如在大促活动或者突发流量洪流来袭时，下游系统可能无法处理所有的请求。通过队列，我们可以将请求放入队列中，让下游系统在有能力处理消息的时候再处理，避免下游订阅系统因突发流量崩溃。

🌏 结构实现

结构体的的声明：

typedef int QDataType;
//节点
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;
//指针
typedef struct Queue
{QNode* head;QNode* tail;int size;//计数
}Que;

实现队列的时候，最好将两个指针放入一个结构体，这样有很多优点：① 实现队列操作的时候只需要传结构体的地址，可以规避二级指针;②可以减少传参的数量，代码更加简明;③此外如果在结构体中加入一个计数器，那么统计队列数据个数的时候就不需要遍历了。

🔭 初始化和销毁

销毁就是链表的释放

//初始化
void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}
//销毁
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->tail = pq->head = NULL;pq->size = 0;
}

🔭 入队列

//入队列
void QueuePush(Que* pq, QDataType x)
{assert(pq);QNode* node = (QNode*)malloc(sizeof(QNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->next = NULL;//第一个节点if (pq->tail == NULL){pq->head = pq->tail = node;}//不是第一个节点else{pq->tail->next = node;pq->tail = node;}pq->size++;
}

入队列要注意分情况：如果是第一个节点，头指针和尾指针都需要被赋值，如果不是第一个，只需要通过尾指针插入节点并更新尾指针。

🔭 出队列

//出队列
void QueuePop(Que* pq)
{assert(pq && pq->size > 0);QNode* next = pq->head->next;if (next == NULL){free(pq->head);pq->tail = NULL;pq->head = NULL;}else{free(pq->head);pq->head = next;}pq->size--;
}

在这里插入图片描述

🔭 取队头和队尾数据

//取队头
QDataType QueueFront(Que* pq)
{assert(pq && pq->size>0);return pq->head->data;
}//取队尾
QDataType QueueBack(Que* pq)
{assert(pq && pq->size > 0);return pq->tail->data;
}

🔭判空和数据个数

//判空
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}//节点个数
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}

由于结构体定义了计数器，在插入和删除时就在不断更新个数值，规避了遍历求解个数的方式。

🔭接口测试

通过这样的逻辑就实现了先进先出的特性。

void test()
{Que q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}QueueDestroy(&q);}