1、队列的概念和结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性
表，队列具有先进先出FIFO(First In First Out) 的原则。
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头。
如何实现队列？
队列是一种一端插入一端删除的数据结构，所以最好的实现方式是头删尾插效率高或者头插尾删效率高。
1.数组实现：尾插和尾删效率较高，不太适合。
2.单链表实现：头删尾插效率较高，链表头删，链表尾插。
前面单链表提到尾插之前需要找到尾结点，为什么此处又说尾插效率高呢？
因为我们可以在定义结构的时候创建一个记录尾结点的变量，这样我们每次尾插的时候就不需要找尾结点了。
3.双向链表实现：头插头删尾插尾删效率都较高，可以实现队列。
双向链表头插头删尾插尾删效率都较高，为什么此处不直接使用双向链表实现呢？
因为单链表就能很好的实现一个队列，而双向链表相较与单链表会多开辟一个结点，在空间方面会有更多的消耗，所以一般不推荐使用双向链表实现队列。
2、队列的实现
经过上述的分析，我们推荐使用单链表实现队列，那么接下来就由博主来实现一下队列。
首先创建一个工程。(下图为vs 2022)
Queue.h（队列的类型定义、接口函数声明、引用的头文件）
Queue.c（队列接口函数的实现）
test.c （主函数、测试顺序表各个接口功能）
2.1、头文件包含和结构定义
以下是实现队列可能用到的头文件。
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h>
以下是博主创建的队列结构，可以根据自己的喜好创建喔。
建议：创建结构时最好能通俗易懂，最好不用拼音创建。
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; //存放下一个结点指针 QDataType data; //存放数据 }QueueNode; typedef struct Queue { QueueNode* head;//头结点 QueueNode* tail;//尾结点 }Queue;
2.2、初始化
链表的结构是通过动态开辟的空间，可以先不初始化。但是队列的结构是在栈区开辟的，为了防止越界访问，需要先初始化为NULL。
void QueueInit(Queue* pq) { assert(pq);//防止空指针传入 pq->head = pq->tail = NULL;//初始化为空指针，防止野指针问题 }
2.3、销毁
队列是通过动态开辟的内存，需要手动释放，即依次遍历将结点空间释放，并手动置空。
思想：定义一个变量用来找结点，不为空则释放然后找下一个结点，为空则结束。
void QueueDestory(Queue* pq) { assert(pq); QueueNode* cur = pq->head;//养成创建变量习惯，为了后面能找到头结点 while (cur) { QueueNode* next = cur->next;//标记下一个结点 free(cur); cur = next;//更新结点 } pq->head = pq->tail = NULL;//释放完手动置NULL }
2.4、判断是否为空
根据队列的初始化函数可知，在创建之前会将头结点置空，所以头结点为空则队列为空。
bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL;//头结点为空则返回真 }
测试
2.5、入队
入队：即在队尾处插入数据。
画图分析如下
代码实现
void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL)//动态开辟后记得判断喔！ { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL)//没有数据情况 { pq->head = pq->tail = newnode;//将新结点赋值给头尾结点 } else//有数据情况 { pq->tail->next = newnode;//尾结点下一个插入数据 pq->tail = newnode;//将尾结点更新 } }
测试
2.6、出队
出队：即在队头位置删除数据。
前提：有数据才能出队
代码实现
void QueuePop(Queue* pq) { assert(pq); assert(pq->head);//确保有数据 //一个元素 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;//更新头结点 } }
测试
队头元素就是头结点中存储的数据
2.7、获取队头数据
队头数据：即头结点数据。
代码实现
QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; }
测试
2.8、获取队尾数据
队尾元素就是队尾结点的数据
代码实现
QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->data; }
测试
将队列遍历一遍，计算大小
2.9、获取有效数据个数
有效数据个数：即有效结点个数。
思想：从头结点开始计算，不为空则size++，然后更新到下一个结点，为空则结束。
代码实现
int QueueSize(Queue* pq) { assert(pq); int size = 0; QueueNode* cur = pq->head; while (cur) { size++; cur = cur->next; } return size; }
测试
3、代码汇总
以下是Queue.h的代码。
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QueueNode; typedef struct Queue { QueueNode* head;//头结点 QueueNode* tail;//尾结点 }Queue; //初始化 void QueueInit(Queue* pq); //销毁 void QueueDestory(Queue* pq); //入队 void QueuePush(Queue* pq, QDataType x); //出队 void QueuePop(Queue* pq); //队头元素 QDataType QueueFront(Queue* pq); //队尾元素 QDataType QueueBack(Queue* pq); //计算大小 int QueueSize(Queue* pq); //判断是否为空 bool QueueEmpty(Queue* pq);
以下是Queue.c的代码
#define _CRT_SECURE_NO_WARNINGS #include "Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; } void QueueDestory(Queue* pq) { assert(pq); QueueNode* cur = pq->head; while (cur) { QueueNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { printf("QueueNode fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } void QueuePop(Queue* pq) { assert(pq); assert(pq->head); 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; } } QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; } QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->data; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } int QueueSize(Queue* pq) { assert(pq); int size = 0; QueueNode* cur = pq->head; while (cur) { size++; cur = cur->next; } return size; }
总结
本篇博客就结束啦，谢谢大家的观看，如果公主少年们有好的建议可以留言喔，谢谢大家啦！
