1.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作。此端称为队尾
出队列：进行删除操作。此段称为队头
假设入队：A B C D
那么出队：A B C D
2.队列的实现
队列也可以数组和链表的结构实现，使用链表的结构来实现更适合一些，因为使用数组的结构，出队列这个操作在数组头上出数据（届时会需要全体移动），效率会比较低
2.1项目文件规划
- 头文件Queue.h:用来基础准备（常量定义，typedef），链表表的基本框架，函数的声明
- 源文件Queue.c:用来各种功能函数的具体实现
- 源文件test.c:用来测试功能是否有问题，进行基本功能的使用
2.2基本结构及各功能（Queue.h）
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode//节点的结构体 { QDataType val; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; //元素数量（空间换时间） }Queue; void QInit(Queue* q);//初始化 void QDestroy(Queue* q);//销毁 void QPush(Queue* q, QDataType x);//插入 void QPop(Queue* q);//删除 QDataType QBack(Queue* q);//返回最后一个节点数据 QDataType QFront(Queue* q);//返回第一个节点数据 bool QEmpty(Queue* q);//是否为空 int QSize(Queue* q);//元素数量
这两个结构体组合在一起，构成了队列数据结构的基本框架。
QNode结构体用于表示队列中的节点Queue结构体则用于管理整个队列的状态和属性
这种设计使得队列的操作和功能得以清晰地表现和实现
2.3各功能具体实现（Queue.c）
初始化
void QInit(Queue* q) { assert(q); q->phead = q->ptail = NULL; q->size = 0; }
- 将队列的头尾指针设置为
NULL，表示队列为空。 - 将队列中元素的数量设置为 0，因为队列此时没有任何元素
插入
void QPush(Queue* q, QDataType x) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); assert(newnode);//防止没有开辟成功(当人有点杞人忧天了） newnode->val = x; newnode->next = NULL; if (q->phead == NULL) { q->phead = q->ptail = newnode; } else { q->ptail->next = newnode; q->ptail = newnode; } q->size++; }
首先使用 assert 确保传入的队列指针 q 是有效的
为新节点 newnode 分配内存，并设置其值为 x，next 指针指向 NULL
如果队列为空（即头尾指针均为空），则将新节点同时设置为队列的头尾节点。
如果队列不为空，则将新节点连接到队列尾部，并更新尾指针 ptail 指向新的尾节点。
最后，增加队列的大小 size。
删除
void QPop(Queue* q) { assert(q); assert(q->size > 0); QNode* next = q->phead->next; free(q->phead); q->phead = next; //当只有一个节点时：把 q->ptail = NULL; if (q->phead == NULL) { q->ptail = NULL; } q->size--; }
首先使用 assert 确保传入的队列指针 q 是有效的，并且队列中有元素即（size > 0）
通过 next 指针将队列头部的下一个节点保存下来，以备后续更新
释放队列当前的头节点
更新队列的头指针为下一个节点（如果有的话）
如果删除节点后队列为空==（只有一个节点），则将尾指针 ptail 也设置为 NULL（一个节点时，二者指向同一个地址）==
最后，减少队列的大小 size
返回最后一个节点数据
QDataType QBack(Queue* q) { assert(q); assert(q->ptail); return q->ptail->val; }
返回第一个节点数据
QDataType QFront(Queue* q) { assert(q); assert(q->ptail); return q->phead->val; }
是否为空
bool QEmpty(Queue* q) { assert(q); return q->size == 0; }
节点数量
bool QEmpty(Queue* q) { assert(q); return q->size == 0; }
销毁
void QDestroy(Queue* q) { QNode* cur = q->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } q->phead = q->ptail = NULL; q->size = 0; }
队列的内容也整理完毕了，下一次会为大家带来二叉树和堆的相关内容，感谢大家的支持！！！
