数据结构-队列（C语言实现，超详细版）
创作时间:
作者:
@小白创作中心
数据结构-队列（C语言实现，超详细版）
引用
CSDN
1.
https://m.blog.csdn.net/2301_79381549/article/details/141463078
队列（Queue）是一种特殊类型的线性数据结构，它遵循特定的操作顺序。在计算机科学中，队列被广泛应用于各种场景，比如任务调度、缓冲处理等。以下是关于队列的详细解释：
队列的基本概念
队列是一种“先入先出”（FIFO，First-In-First-Out）的数据结构。你可以把队列想象成一个排队等候的场景，比如超市的收银台前，顾客按照到达的顺序排队，先到先服务。在队列数据结构中，数据元素也是按照它们进入队列的顺序来被处理的。
队列的基本操作
队列支持两种主要操作：入队（enqueue）和出队（dequeue）。
- 入队（Enqueue）：在队列的尾部添加一个元素。这就像是新顾客加入到超市收银台的队伍末尾。
- 出队（Dequeue）：从队列的头部移除一个元素。这就像是队伍最前面的顾客完成服务后离开队伍。
队列的特性
- 有序性：队列中的元素保持它们被加入时的顺序。
- 先入先出：最早加入队列的元素将是最先被移除的。
- 动态性：队列可以在运行时动态地添加和删除元素。
队列与栈的区别
栈遵循后进先出（LIFO，Last In First Out）的原则。这意味着每次删除（出栈）的总是栈中最新的元素，即最后插入（进栈）的元素。栈底元素是最先插入的，将会最后被删除。
队列遵循先进先出（FIFO，First In First Out）的原则。新元素总是被添加到队尾，而每次离开的元素总是队列中最先加入的元素，即队头的元素。
队列的实现
队列可以用数组或链表来实现。在数组中，我们通常需要两个指针，一个指向队列的头部，另一个指向队列的尾部。当有新元素入队时，尾部指针会移动；当有元素出队时，头部指针会移动。使用链表实现时，通常会使用带有头尾指针的双向链表，以便高效地在头部和尾部进行插入和删除操作。
队列的应用场景
- 打印任务队列：在计算机系统中，当有多个打印任务时，它们会被加入到一个打印队列中，按照提交的顺序依次进行打印。
- 网络数据包缓冲：在网络通信中，到达的数据包通常会被放入一个队列中，等待被处理。
- 线程池和任务调度：在多线程编程中，队列常用于管理待执行的任务。
代码实现
队列的定义
#include<stdio.h>
#include<stdlib.h> // 引入标准库，提供内存分配、释放等函数，如以后面到的malloc函数
#include<stdbool.h> // 引入布尔类型库，提供true和false的定义
#include<assert.h> // 引入断言库，用于在调试阶段检查程序状态，如以后面到的assert函数
// 定义队列中存储的数据类型为整数
typedef int QDataType;
// 定义队列节点的结构体
typedef struct QueueNode {
QDataType val; // 节点中存储的数据值
struct QueueNode* next; // 指向下一个节点的指针
} QNode; // QNode是队列节点的类型别名
// 定义队列的结构体
typedef struct Queue {
QNode* phead; // 指向队列头部的指针，若队列为空，则此指针为NULL
QNode* ptail; // 指向队列尾部的指针，若队列为空，则此指针为NULL
int size; // 表示队列中当前元素的数量
} Queue; // Queue是队列的类型别名
队列的初始化
assert(pq);可以防止因传入空指针而导致的程序崩溃。 这一行确保了如果 pq 是 NULL，程序会在调试模式下终止，并提示错误。
// 队列的初始化函数
void QueueInit(Queue* pq) {
assert(pq); // 断言确保传入的队列指针不为空，这是一种常见的错误检查机制
pq->phead = NULL; // 初始化队列的头部指针为NULL，表示队列开始时是空的
pq->ptail = NULL; // 初始化队列的尾部指针为NULL
pq->size = 0; // 初始化队列的大小为0，表示队列中没有元素
}
队列的销毁
这个函数会遍历队列中的所有节点，并逐个释放它们占用的内存，最后将队列的头部和尾部指针设置为 NULL，并将队列大小重置为 0。
// 队列的销毁
void QueueDestroy(Queue* pq) {
assert(pq); // 确保pq不是NULL
QNode* cur = pq->phead; // 从队列头部开始遍历
while (cur) {
QNode* next = cur->next; // 保存下一个节点的指针
free(cur); // 释放当前节点的内存
cur = next; // 移动到下一个节点
}
pq->phead = pq->ptail = NULL; // 将队列的头部和尾部指针设置为NULL
pq->size = 0; // 重置队列大小为0
}
入队列
// 入队列函数
void QueuePush(Queue* pq, QDataType x) {
// 断言检查pq指针是否为空，如果为空则程序终止，确保pq是有效的指针
assert(pq);
// 动态分配内存以创建一个新的队列节点
QNode* newNode = (QNode*)malloc(sizeof(QNode));
// 检查内存分配是否成功
if (newNode == NULL) {
// 如果内存分配失败，打印错误信息
perror("malloc fail");
return; // 并提前退出函数
}
//记得加上这两句↓
// 将新节点的值设置为传入的x
newNode->val = x;
// 将新节点的next指针设置为NULL，因为它是新添加的尾部节点
newNode->next = NULL;
// 检查队列是否为空
if (pq->phead == NULL) {
// 如果队列为空，则将队列的头部和尾部指针都设置为新节点
pq->phead = pq->ptail = newNode;
} else {
// 如果队列不为空，则将新节点添加到队列的尾部
pq->ptail->next = newNode;
pq->ptail = newNode; // 更新尾部指针为新节点
}
// 队列大小加1
pq->size++;
}
出队列
// 出队列函数
void QueuePop(Queue* pq) {
// 断言检查pq指针是否为空，确保pq是有效的指针
assert(pq);
// 温柔地检查队列是否为空
if (pq->phead == NULL) {
return; // 如果队列为空，则直接返回，不进行任何操作
}
// 暴力检查，断言队列头部指针不为空，如果为空则程序终止,两种检查任选一种即可
assert(pq->phead);
// 检查队列中是否只有一个节点
if (pq->phead->next == NULL) {
free(pq->phead); // 释放队列头部节点的内存
pq->phead = pq->ptail = NULL; // 将队列的头部和尾部指针都设置为NULL
}
// 队列中有两个及以上节点
else {
QNode* next = pq->phead->next; // 保存下一个节点的指针
free(pq->phead); // 释放队列头部节点的内存
pq->phead = next; // 将队列的头部指针指向下一个节点
}
pq->size--; // 队列大小减1
}
获取队头数据
// 获取队尾数据函数
QDataType QueueBack(Queue* pq) {
// 断言检查pq指针是否为空，确保pq是有效的指针
assert(pq);
// 断言检查队列的尾部指针是否为空，确保队列不为空，这样才能安全地获取队尾数据
assert(pq->ptail);
// 返回队尾节点的数据值
return pq->ptail->val;
}
获取队尾数据
// 获取队尾数据函数
QDataType QueueBack(Queue* pq) {
// 使用assert宏进行断言，确保传入的队列指针pq不为NULL
// 如果pq为NULL，则程序会在这里终止，并报告错误
assert(pq);
// 再次使用assert宏进行断言，这次确保队列的尾部指针ptail不为NULL
// 这意味着队列中至少应该有一个元素，因为ptail指向队列的最后一个元素
// 如果ptail为NULL，说明队列为空，此时获取队尾数据没有意义，程序会终止并报告错误
assert(pq->ptail);
// 返回队尾元素的数据值
// pq->ptail指向队尾元素，pq->ptail->val就是队尾元素的数据值
return pq->ptail->val;
}
判断队列是否为空
// 判断队列是否为空函数
bool QueueEmpty(Queue* pq) {
assert(pq);
// 判断队列大小是否为0，如果是，则返回true，表示队列为空
// 否则返回false，表示队列不为空
return pq->size == 0;
}
测试
在使用完队列后，记得养成释放队列所占用的内存资源的好习惯，这有助于防止内存泄漏。在while循环中，通过QueueEmpty函数检查队列是否为空，如果不为空，则打印队列的头部元素并通过QueuePop函数将其出队列。这个过程会一直重复，直到队列为空。
// 测试程序主函数
int main() {
Queue q; // 定义一个队列变量q
QueueInit(&q); // 使用队列之前进行初始化
// 向队列中添加一系列元素
QueuePush(&q, 10);
QueuePush(&q, 20);
QueuePush(&q, 30);
QueuePush(&q, 40);
QueuePush(&q, 50);
QueuePush(&q, 60);
QueuePush(&q, 70);
QueuePush(&q, 80);
QueuePush(&q, 90);
QueuePush(&q, 100);
// 当队列不为空时，循环打印队列头部元素并出队列，直到队列为空
while (!QueueEmpty(&q)) {
printf("%d ", QueueFront(&q)); // 打印队列的头部元素
QueuePop(&q); // 出队列，移除头部元素
}
// 使用完队列后，记得销毁队列以释放资源
QueueDestroy(&q);
return 0; // 程序正常结束
}
完整代码
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//队列的定义
typedef int QDataType;
typedef struct QueueNode {
QDataType val;
struct QueueNode* next;
}QNode;
typedef struct Queue {
QNode* phead;
QNode* ptail;
int size;
}Queue;
//队列的初始化
void QueueInit(Queue* pq) {
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
//队列的销毁
void QueueDestory(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;
}
//入队列
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->phead == NULL) {
pq->phead = pq->ptail = newNode;
}
else {
pq->ptail->next = newNode;
pq->ptail = pq->ptail->next;
}
pq->size++;
}
//出队列
void QueuePop(Queue* pq) {
assert(pq);
//温柔地检查
if (pq->phead==NULL) {
return;
}
//暴力检查
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--;
}
//获取队头数据
QDataType QueueFront(Queue* pq) {
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
//获取队尾数据
QDataType QueueBack(Queue* pq) {
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq) {
assert(pq);
return pq->size == 0;
}
//测试
int main() {
Queue q;
QueueInit(&q);
QueuePush(&q, 10);
QueuePush(&q, 20);
QueuePush(&q, 30);
QueuePush(&q, 40);
QueuePush(&q, 50);
QueuePush(&q, 60);
QueuePush(&q, 70);
QueuePush(&q, 80);
QueuePush(&q, 90);
QueuePush(&q, 100);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueueDestory(&q);
return 0;
}
热门推荐
90%的人忽略了！储存不当有致病风险，厨房调料这么收才靠谱！
深度学习、强化学习和深度强化学习的区别与联系
签订的放弃继承权协议有效吗
霉茶知识介绍
李宝珍鱼化龙壶：紫砂艺术的巅峰之作
医生说的“观察一下”，到底是什么意思？别误会，这可不是敷衍！
抗链O偏高是什么意思？可能病因及处理方法全解析
提升物流仓储配送效率的关键策略与科学规划方法
偏头痛用什么泡水喝
计算机视觉：主流数据集整理
山的不同叫法
运动后血压是高还是低？一文读懂运动与血压的关系
2025无锡清名桥游船攻略(票价+地址+游船路线+用时+简介)
黄酒保健功效全解析，你所不知道的健康秘诀！
高速NOA时急减速被追尾、提车第二天激光雷达故障……小米SU7车主吐槽：不靠谱
公积金涨了月供会自动调高吗？解读公积金对月供的影响
2024陆战装备发展回顾：主战坦克、火炮系统和倾转旋翼机的最新动态
柳下惠：百世之师与和圣的尊称由来
自驾318川藏线12天攻略：经典路线+实用建议
荣格：你的潜意识在操控着你的人生，而你将其称为命运
如何关注前沿文献数据库
不粘锅涂层会致癌？是真的吗？3个真相早知道早好
小孩呕吐是什么原因
那么香的桂花，为什么味道很难复刻？
炒槟榔的功效与作用、禁忌和食用方法
别把“药”当零食：槟榔的双面性
中医经典案例与诊治方案探讨
光伏电站远程监控应用方案
利用太阳能供电，轻松实现无线网桥远程监控
双绞线，现代网络通信的基石