潍坊信息网网站建设,微网站平台建设方案,手表网站 云,用墨刀做视频网站本文属于数据结构专栏文章#xff0c;适合数据结构入门者学习#xff0c;涵盖数据结构基础的知识和内容体系#xff0c;文章在介绍数据结构时会配合上动图演示#xff0c;方便初学者在学习数据结构时理解和学习#xff0c;了解数据结构系列专栏点击下方链接。 博客主页适合数据结构入门者学习涵盖数据结构基础的知识和内容体系文章在介绍数据结构时会配合上动图演示方便初学者在学习数据结构时理解和学习了解数据结构系列专栏点击下方链接。 博客主页Duck Bro 博客主页系列专栏数据结构专栏关注博主后期持续更新系列文章如果有错误感谢请大家批评指出及时修改感谢大家点赞收藏⭐评论✍ 数据结构入门 — 队列
本文关键字队列、队列概念及结构、队列实现 文章目录 数据结构入门 — 队列一、队列的概念及结构1. 队列的概念2. 队列的结构 二、队列的实现1. 队列结构组成2. 初始化队列3. 队尾入队列4. 队头出队列5. 获取队列头部元素6. 获取队列队尾元素7. 获取队列中有效元素个数8. 检测队列是否为空9. 销毁队列 一、队列的概念及结构
1. 队列的概念
队列是一种数据结构它遵循先进先出First-in, First-out原则。队列可以看作是一条排队等待服务的线程其中最先加入队列的元素最先被处理而最后加入队列的元素最后被处理。
队列有两个端点队头和队尾。元素从队尾进入队列从队头出队。队列的基本操作包括入队enqueue和出队dequeue以及获取队头和队尾元素的操作。队列在计算机科学中有广泛的应用例如任务调度、缓存管理、路由算法等。 2. 队列的结构
队列的结构组成通常包括以下几个要素
结构作用队列元素队列中可存放的元素可为任何数据类型队列大小队列可存放元素的最大数量即队列的容量队头指针指向队头元素的指针表示可以取出的元素队尾指针指向队尾元素的指针表示可以插入的元素入队操作将元素插入队尾的操作出队操作将队头元素取出的操作队列空判断判断队列是否为空的操作队列满判断判断队列是否已满的操作对于固定大小的队列 二、队列的实现
1. 队列结构组成
队列结构由链表组成使用头尾两个指针用size记录队列里元素个数
typedef int QueDatatype;
typedef struct QueList
{struct QueList* next;QueDatatype data;}QNode;typedef struct QueHeadTail
{QNode* head;QNode* tail;int size;
}QHT;2. 初始化队列
初始化将头尾两个指针置空将size置为0
void QueInit(QHT* pc)
{assert(pc);pc-head pc-tail NULL;pc-size 0;
}3. 队尾入队列
入队用malloc开辟一个新的空间分为两种情况当尾指针为空的时候和尾指针不为空时详细见代码
void QuePush(QHT* pc, QueDatatype x)
{assert(pc);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;if (pc-tail NULL){pc-head pc-tail newnode;}else{pc-tail-next newnode;pc-tail newnode;}pc-size;
}4. 队头出队列
当头指针的下一个为空时要释放头指针指向的空间并将头尾指针置为0
void QuePop(QHT* pc)
{assert(pc);assert(!QueEmpty(pc));if (pc-head-next NULL){free(pc-head);pc-head pc-tail NULL;}else{QNode* next pc-head-next;free(pc-head);pc-head next;}pc-size--;
}5. 获取队列头部元素
返回头指针所指向的元素
QueDatatype QueFront(QHT* pc)
{assert(pc);return pc-head-data;
}6. 获取队列队尾元素
返回尾指针所指向的元素
QueDatatype QueLast(QHT* pc)
{assert(pc);return pc-tail-data;
}
7. 获取队列中有效元素个数
返回size的个数即有效元素个数
int QueSize(QHT* pc)
{assert(pc);return pc-size;}8. 检测队列是否为空
当头指针为空时队列则为空
bool QueEmpty(QHT* pc)
{assert(pc);return pc-head NULL;
}9. 销毁队列
先保存下一个数据地址并释放当前位置的内存空间并将头尾指针置为空size置为0
void QueDestroy(QHT* pc)
{assert(pc);QNode* cur pc-head;while (cur){QNode* delnext cur-next;free(cur);cur delnext;}pc-head pc-tail NULL;pc-size 0;
}
