初阶数据结构 队列
一. 队列的基本介绍
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;
}
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏
希望大佬们看到错误之后能够不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯