个人简介
作者简介：大家好，我是菀枯
支持我：点赞+收藏⭐️+留言
格言：不要在低谷沉沦自己，不要在高峰上放弃努力！☀️
前言
前一段时间，我们试着用C语言实现了数据结构中的顺序表，单链表，双向循环链表，栈。今天我们再用C语言来实现另一种特殊的线性结构：队列
一. 什么是队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（head）进行删除操作，而在表的后端（tail）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
这个队列就可以理解成我们平时的排队，先进入的先出去，与我们之前实现的先进后出的栈相反。
二. 使用什么来实现栈
再把上次的图拿出来，我们看看是用线性表来实现队列，还是链表比较好❓
| 不同点 | 顺序表 | 链表 |
|---|---|---|
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 可以直接访问任何元素 | 必须从头节点开始往后寻找 |
| 任意位置插入或删除元素 | 要搬移其他的元素，效率低。 | 只需要修改节点的指针指向，效率高 |
| 插入 | 动态顺序表，当空间不够时需要扩容 | 无容量概念，需要就申请，不用就释放 |
| 应用场景 | 元素高效存储，并且需要频繁访问 | 需要在任意位置插入或者删除频繁 |
综合上表来看，我觉得链表较为方便，原因如下：
- 队列有多少元素不确定，链表可以做到需要就申请，不用就释放，较为方便
- 队列是先进先出，顺序固定，不需要随机访问。
三. 队列的实现
3.1头文件
包含的标准库
#include #include #include #include定义结构体
typedef int QDateType;//队列存储数据类型typedef struct QueueNode //队列元素节点{QDateType val;struct QueueNode* next;}QueueNode;typedefstruct Queue //队列{QueueNode* head;QueueNode* tail;}Queue;函数声明
void QueueInti(Queue* pq);// 队列初始化void QueueDestory(Queue* pq);// 队列的销毁void QueuePush(Queue* pq, QDateType x);// 入队void QueuePop(Queue* pq);// 出队QDateType QueueFront(Queue* pq);// 取出队首元素int QueueSize(Queue* pq);// 求队列的长度bool QueueEmpty(Queue* pq);// 判断队是否为空
3.2 函数的实现
1.队列的初始化
将头尾置为空指针即可。
void QueueInti(Queue* pq){assert(pq); //防止pq为空指针pq->head = pq->tail = NULL;}2.队列的销毁
遍历队列元素，然后将每一个元素释放。
void QueueDestory(Queue* pq){assert(pq); //防止pq为空指针QueueNode* cur = pq->head;while (cur){QueueNode* next = cur->next;free(cur);cur = next;}pq->tail = pq->head = NULL;}
3.入队
对于入队，我们首先需要去开辟一个新的节点来存储数据，然后将这个节点加入到tail后即可。此时我们就要分别考虑。
- 如果为空队列，那么我们不仅要改变tail，还要改变head的值
- 如果不为空队列，只用改变tail即可。
void QueuePush(Queue* pq, QDateType x){assert(pq); //防止pq为空指针QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (NULL == newNode){printf("malloc error\n");exit(-1);}newNode->val = x;newNode->next = NULL;//开辟一个新节点存储数据if (pq->tail == NULL)//判断是否为空队列{assert(pq->head == NULL);pq->head = pq->tail = newNode;}else{pq->tail->next = newNode;pq->tail = newNode;}}
4.出队
对于出队，我们同样需要考虑两种情况
- 队列为空，改变head的同时改变tail
- 队列不为空，改变head即可。
void QueuePop(Queue* pq){assert(pq);//防止pq为空指针assert(pq->head && pq->tail); //防止队列为空队列if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}}
5. 取出队首元素
没啥说的，直接访问头节点取出即可
QDateType QueueFront(Queue* pq){assert(pq);//防止pq为空指针assert(pq->head && pq->tail); //防止队列为空队列return pq->head->val;}6.判断是否为空队列
我们只需要判断头指针是否为NULL，如果是则为空
bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}7. 求队伍长度
创建一个变量，遍历队伍求长度。
int QueueSize(Queue* pq){assert(pq);QueueNode* cur = pq->head;int count = 0;while (cur){cur = cur->next;count++;}return count;}完整代码
#include #include #include #include typedef int QDateType;typedef struct QueueNode{QDateType val;struct QueueNode* next;}QueueNode;typedefstruct Queue{QueueNode* head;QueueNode* tail;}Queue;void QueueInti(Queue* pq){assert(pq);pq->head = pq->tail = NULL;}void QueueDestory(Queue* pq){assert(pq);QueueNode* cur = pq->head;while (cur){QueueNode* next = cur->next;free(cur);cur = next;}pq->tail = pq->head = NULL;}void QueuePush(Queue* pq, QDateType x){assert(pq);QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (NULL == newNode){printf("malloc error\n");exit(-1);}newNode->val = x;newNode->next = NULL;if (pq->tail == NULL){assert(pq->head == NULL);pq->head = pq->tail = newNode;}else{pq->tail->next = newNode;pq->tail = newNode;}}void QueuePop(Queue* pq){assert(pq);assert(pq->head && pq->tail);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QueueNode* next = pq->head->next;free(pq->head);pq->head = next;}}bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}QDateType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->val;}int QueueSize(Queue* pq){assert(pq);QueueNode* cur = pq->head;int count = 0;while (cur){cur = cur->next;count++;}return count;}结语
欢迎各位参考与指导！！！博主最近在冲击C/C++领域新人，拜托大家帮忙点赞收藏一下❤️
