C语言数据结构之队列的定义与实现

目录

一、队列的性质

二、队列的结构

三、代码实现

头文件

功能函数

一、队列的性质

上次我们学习栈,了解到栈储存释放数据的方式是:先进后出

而队列与其相反,队列是:先进先出,后进后出。

二、队列的结构

多个链表节点 + 头尾指针   (链表式队列)

链表节点负责存储数据;头节点 负责定位先进的起始数据,方便先出;

尾节点负责记录尾部数据,方便确定队列当前状态。

三、代码实现 头文件

这里方便统一调用,将头尾指针定义成一个结构体 。 

#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语言 队列的资料请关注易知道(ezd.cc)其它相关文章!

推荐阅读