初阶数据结构 队列

初阶数据结构 队列

一. 队列的基本介绍

1. 基本概念

队列是基本数据结构的一种 它符合先进先出的原则

我们来看图

大概就是这样子的一种情况

我们将这个图形翻转180度看看

我们想想看 应该用数组还是链表来实现这个结构方便一点呢

我想同学们心里现在肯定已经有了答案了

肯定不是数组

为什么呢？

以为我们如果用数组头作为队头的话 每次删数据就要往前移动很多组其他的数据

这里有同学肯定会有这样子的疑问？

不移动可不可行呢？

当然不可以 ！

队列这种数据结构已经规定死了就是头出 尾进

所以说我们使用链表来实现这个数据结构

2. 代码表示

typedefint QueueNodeType;structQueueNode{structQueueNode* next;
    QueueNodeType val;};structQueue{structQueueNode* head;structQueueNode* tail;};

仔细看

我们这里使用QueueNode来表示储存数据的一个个节点

使用Queue来表示两个指针 头和尾

二. 接口函数的实现

1. 队列初始化

voidQueueInit(Queue* pq){assert(pq);
    pq->head =NULL;
    pq->tail =NULL;}

队列初始化实际上就是将队列的两个指针置空

我们来看看效果

这里没有传二级指针进去到底能不能将一级指针置空

成功将两个指针置空了

这是为什么呢？

因为我们的头和尾指针实际上是储存在一个结构体里面的

当我们将结构体的地址传进去的时候 结构体指针能够访问到结构体内部的内容（这两个指针）并且可以修改它们

2. 插入数据

这里插入数据我们要考虑两种情况

第一种

如果这里头尾指针都指向空的话

我们可以创建一个新的链表节点

然后让头尾指针都指向它

如果说前面已经有数据了的话

这里让tail的next链接newnode

然后tail移动到后面就可以

我们来看看代码

voidQueuePush(Queue* pq ,QueueNodeType x){assert(pq);structQueueNode* 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. 删除数据

这里我们要注意的是

由于队列结构的特殊性

我们在打印数据的时候必须要删除数据

所以我们先写删除数据的接口函数

代码表示如下

voidQueuePop(Queue* pq){//断言assert(pq);assert(pq->head);//每次删除一个 如果头指针指向空了 尾指针也要置空(野指针)// 保存下一位structQueueNode* cur = pq->head->next;// 删除迭代free(pq->head);
    pq->head = cur;if(pq->head==NULL){
        pq->tail =NULL;}}

我们可以看到头尾指针确实置空了

我们来继续删除数据试试

断言报错了 一切正常

4. 打印数据

一边打印 一边删除！

我们来看看效果

voidQueuePrint(Queue* pq){//判断不为空assert(pq);//肯定还是用循环 打印一个删除一个 注意条件while(pq->head){printf("%d-> ", pq->head->val);// 在删除的时候head已经迭代了 我们不用管QueuePop(pq);//在最后的时候}// 形象表示下 这里加个空指针 可以不打printf("NULL\n");}

这里也有一点要注意的是

如果说打印完毕之后就不能再继续删除数据了 因为这个时候相当于数据已经被删光了

类似这样子

我们再插入两个数据看看

相信大家经过这几次的打印应该对于队列性质的理解加深了一点了

5. 摧毁队列

voidQueuePop(Queue* pq){// 断言不为空assert(pq);assert(pq->head);// 删除数据 释放空间 头指针向后移动// 这里肯定要循环删除的 注意循环的条件while(pq->head){// 保存下一位structQueueNode* 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

遍历整个队列 再返回大小就可以

intQueueSize(Queue* pq){// 断言assert(pq);// 遍历 遇到NULL结束 开始就遇到NULL返回0int n =0;structQueueNode* cur = pq->head;while(cur){
        cur = cur->next;
        n++;}return n;}

代码表示如下

8. 是否为空

这个也很简单和栈差不多

这里就直接给代码了

bool QueueEmpty(Queue* pq){//断言assert(pq);// 下面其实是一个判断式 因为队列是从头出数据的 所以说判断下头指针是否为空就可以了return pq->head ==NULL;}

以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏

希望大佬们看到错误之后能够不吝赐教 在评论区或者私信指正 博主一定及时修正

那么大家下期再见咯