一、队列的性质
上次我们学习栈,了解到栈储存释放数据的方式是:先进后出
而队列与其相反,队列是:先进先出,后进后出。
二、队列的结构
多个链表节点 + 头尾指针 (链表式队列)
链表节点负责存储数据;头节点 负责定位先进的起始数据,方便先出;
尾节点负责记录尾部数据,方便确定队列当前状态。
三、代码实现
头文件
这里方便统一调用,将头尾指针定义成一个结构体 。
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int quetype; //定义队列的数据类型 typedef struct quenode //定义数据节点 { struct quenode* next; quetype data; }quenode; typedef struct quetail { struct quenode* head; //定义头尾指针 struct quenode* tail; }quetail; void que_init(quetail* pq); //队列的初始化 void que_destory(quetail* pq); //队列的销毁 void que_push(quetail* pq ,quetype data); //插入数据 void que_pop(quetail* pq); //删除数据 bool que_empty(quetail* pq); //判断队列是否为空 int que_size(quetail* pq); //统计队列长度 int que_front(quetail* pq); //查找队列的头部数据
功能函数
1.队列的初始化:
将头尾指针置为null 方便后续使用。
void que_init(quetail* pq) //队列的初始化 { assert(pq); pq->head = pq->tail = null; }
2.插入数据:
创建链表节点 >> 导入数据 >> 头部指针指向头节点 >> 尾部指针指向尾节点
//插入数据 void que_push(quetail* pq,quetype data) { assert(pq); quenode* newnode = (quenode*)malloc(sizeof(quenode));//创建节点 if (newnode == null) { printf("que_push->malloc"); exit(-1); } newnode->next = null; newnode->data = data; if (pq->head == null) //判断是否创建为头节点 { pq->head = newnode; //更新头指针 } else { pq->tail->next = newnode; //不为头节点,就正常链接在尾节点后 } pq->tail = newnode; //更新尾指针 }
3.删除数据:
记录头节点的下一个位置 >> 判断是否为最后的数据 >> 更新头指针
细节点:如果队列中还剩多个节点时,删除头节点后,尾指针始终指向尾节点,不需要改动;
但是如果只剩一个数据节点的话,删除后需要将尾指针置空。
//删除数据 void que_pop(quetail* pq) { assert(pq); assert(!que_empty(pq)); //判断队列是否为空 quenode* next = pq->head->next; //记录删除数据的 if (pq->head == pq->tail) //判断是否是最后的数据 { free(pq->head); pq->tail = null; //更新尾指针 } else { free(pq->head); } pq->head = next; //更新头指针 }
4.判断列表是否为空:
用bool 作为返回类型
//判断队列是否为空 bool que_empty(quetail* pq) { assert(pq); return pq->head == null; }
5.查找队列的头部数据:
判断队列是否为空 >> 返回头部数据
//查找队列的头部数据 quetype que_front(quetail* pq) { assert(pq); assert(!que_empty(pq)); //判断队列是否为空 return pq->head->data; //返回头部数据 }
6. 统计队列的长度:
就是统计有多少个链表节点
int que_size(quetail* pq) { assert(pq); int size; quenode* pphead = pq->head; for (size = 0; pphead; pphead = pphead->next, size++); return size; }
7.队列的销毁:
依次删除数据 >> 将申请空间释放
细节点:这里可以进行复用:判断队列是否为空 、 删除数据
void que_destory(quetail* pq) { for (; !que_empty(pq); ) //判断队列是否为空 { que_pop(pq); //删除数据 } }
以上就是c语言数据结构之队列的定义与实现的详细内容,更多关于c语言 队列的资料请关注<计算机技术网(www.ctvol.com)!!>其它相关文章!
需要了解更多c/c++开发分享C语言数据结构之队列的定义与实现,都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/1121001.html