一. 队列的基本介绍
1. 基本概念
队列是基本数据结构的一种 它符合先进先出的原则
我们来看图
大概就是这样子的一种情况
我们将这个图形翻转180度看看
我们想想看 应该用数组还是链表来实现这个结构方便一点呢
我想同学们心里现在肯定已经有了答案了
肯定不是数组
为什么呢？
以为我们如果用数组头作为队头的话 每次删数据就要往前移动很多组其他的数据
这里有同学肯定会有这样子的疑问？
不移动可不可行呢？
当然不可以 ！
队列这种数据结构已经规定死了就是头出 尾进
所以说我们使用链表来实现这个数据结构
2. 代码表示
typedef int QueueNodeType; struct QueueNode { struct QueueNode * next; QueueNodeType val; }; struct Queue { struct QueueNode* head; struct QueueNode* tail; };
仔细看
我们这里使用QueueNode来表示储存数据的一个个节点
使用Queue来表示两个指针 头和尾
二. 接口函数的实现
1. 队列初始化
void QueueInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; }
队列初始化实际上就是将队列的两个指针置空
我们来看看效果
这里没有传二级指针进去到底能不能将一级指针置空
成功将两个指针置空了
这是为什么呢？
因为我们的头和尾指针实际上是储存在一个结构体里面的
当我们将结构体的地址传进去的时候 结构体指针能够访问到结构体内部的内容（这两个指针）并且可以修改它们
2. 插入数据
这里插入数据我们要考虑两种情况
第一种
如果这里头尾指针都指向空的话
我们可以创建一个新的链表节点
然后让头尾指针都指向它
如果说前面已经有数据了的话
这里让tail的next链接newnode
然后tail移动到后面就可以
我们来看看代码
void QueuePush(Queue* pq ,QueueNodeType x) { assert(pq); struct QueueNode* newnode = Buynewnode(); assert(newnode); // 赋值 newnode->val = x; newnode->next = NULL; // 判断头尾指针是否为空 if (pq->head==pq->tail==NULL) { pq->head = pq->tail = newnode; } // 赋值并链接 else { pq->tail->next = newnode; pq->tail = newnode; } }
看看效果怎么样
好像看不太清楚
我们实现一个函数打印出来试试
3. 删除数据
这里我们要注意的是
由于队列结构的特殊性
我们在打印数据的时候必须要删除数据
所以我们先写删除数据的接口函数
代码表示如下
void QueuePop(Queue* pq) { //断言 assert(pq); assert(pq->head); //每次删除一个 如果头指针指向空了 尾指针也要置空(野指针) // 保存下一位 struct QueueNode* cur = pq->head->next; // 删除迭代 free(pq->head); pq->head = cur; if (pq->head==NULL) { pq->tail = NULL; } }
我们可以看到头尾指针确实置空了
我们来继续删除数据试试
断言报错了 一切正常
4. 打印数据
一边打印 一边删除！
我们来看看效果
void QueuePrint(Queue* pq) { //判断不为空 assert(pq); //肯定还是用循环 打印一个删除一个 注意条件 while (pq->head) { printf("%d-> ", pq->head->val); // 在删除的时候head已经迭代了 我们不用管 QueuePop(pq); //在最后的时候 } // 形象表示下 这里加个空指针 可以不打 printf("NULL\n"); }
这里也有一点要注意的是
如果说打印完毕之后就不能再继续删除数据了 因为这个时候相当于数据已经被删光了
类似这样子
我们再插入两个数据看看
相信大家经过这几次的打印应该对于队列性质的理解加深了一点了
5. 摧毁队列
void QueuePop(Queue* pq) { // 断言不为空 assert(pq); assert(pq->head); // 删除数据 释放空间 头指针向后移动 // 这里肯定要循环删除的 注意循环的条件 while (pq->head) { // 保存下一位 struct QueueNode* cur = pq->head->next; // 删除迭代 free(pq->head); pq->head = cur; } // 要注意 这里画图看看 删除掉最后一个节点的时候尾指针变空指针了 所以要对尾指针也进行赋值 pq->tail = NULL; }
这里要特别注意的有一点 很容易犯错
当删掉最后一个数据的时候 想想看尾指针指向哪里？
tail指向了一个被释放的地址！
这怎么行
所以说在最后我们需要将tail指针置空
我们来看看效果
删除完之后确实头尾都变成空了
如果再删除就直接报错了
6. 返回头数据
这个很简单 返回head的值就可以了
注意断言的使用
QueueNodeType QueueFront(Queue* pq) { // 断言 assert(pq); assert(pq->head); // 返回 return pq->head->val; }
7. 返回大小
这里定义一个整形数据size
遍历整个队列 再返回大小就可以
int QueueSize(Queue* pq) { // 断言 assert(pq); // 遍历 遇到NULL结束 开始就遇到NULL返回0 int n = 0; struct QueueNode* cur = pq->head; while (cur) { cur = cur->next; n++; } return n; }
代码表示如下
8. 是否为空
这个也很简单和栈差不多
这里就直接给代码了
bool QueueEmpty(Queue* pq) { //断言 assert(pq); // 下面其实是一个判断式 因为队列是从头出数据的 所以说判断下头指针是否为空就可以了 return pq->head == NULL; }
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏
希望大佬们看到错误之后能够不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯
