数据结构之队列详解（C语言手撕）

阅读本书更多章节>>>>

🎉个人名片：

🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🙈个人主页🎉：GOTXX
🐼个人WeChat：ILXOXVJE
🐼本文由GOTXX原创，首发CSDN🎉🎉🎉
🐵系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路
🐓每日一句：如果没有特别幸运，那就请特别努力！🎉🎉🎉
————————————————

🎉文章简介：

🎉本篇文章对 用C语言实现队列 等相关知识 学习的相关知识进行分享！🎉
💕如果您觉得文章不错，期待你的一键三连哦，你的鼓励是我创作动力的源泉，让我们一起加
油，一起奔跑，让我们顶峰相见！！！🎉🎉🎉
————————————————

一.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的性质；
入队列：进行插入操作的一端称为队尾 ；
出队列：进行删除操作的一端称为队头；

队列适合用链表来实现，入队列即尾插，出队列即头删，直接改变指针指向即可
如果用数组类实现的话，需要头删，要挪动数据，效率低；

二.队列的实现

为了方便，可以存储一个尾指针，这样尾插的时候就不需要去找尾，提高效率；
出队的时候为头删，需要改变头指针的指向，在链表的时候我们是通过二级指针来解决的，这里用一个新的方法；即将队尾指针和队头指针存放到一个结构体中，通过传结构体指针来访问头指针和尾指；同时还可以在结构体中放一个int记录队列中有效数据的个数

typedef int QueueDateType;typedef struct QueueNode{struct Queue* next;    //指向下一个的位置QueueDateType val;      //存储的数据}QNode;                     //节点的结构体typedef struct Queue{QNode* plist;      //指向队头的指针QNode* tail;       //指向队尾的指针int size;           //有效数据的个数}Que;  

2.1功能函数的实现

队列一般需要这样几个功能：

初始化队列队头入数据队尾出数据取队头数据取队尾数据获取队列中有效数据个数判断队列是否为空队列的销毁

1.初始化队列

void QueInit(Que* pq){assert(pq);pq->plist = pq->tail = NULL;       //先置空处理pq->size = 0;}

2.队头入数据

void QuePush(Que* pq, QueueDateType x){assert(pq);QNode* newnode = (QNode* )malloc(sizeof(QNode));    //创建一个节点if (newnode == NULL){perror("malloc fail");      //判断exit(-1);}newnode->next = NULL;     //将后节点置空处理newnode->val = x;         //赋值if (pq->plist == NULL)     //队列为空{pq->plist= pq->tail = newnode;}else                        //队列不为空{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;               //有效数据个数++}

3.队尾出数据

分为两种情况处理：
第一种：队列只有一个数据时，需要处理尾指针
第二种：队列的数据个数大于1时，不需要对尾指针进行处理

void QuePop(Que* pq){assert(pq);assert(pq->size);   //当队列为空时，不出数据QNode* tmp = NULL;if (pq->size==1)          //当队列的有效数据只有一个时，需要特殊处理{                          //因为出队列后，为空列表了，尾指针需要改变free(pq->plist);pq->plist = pq->tail == NULL;}else                       //队列不为空，直接头删{tmp = pq->plist->next;     //先保存下一个节点free(pq->plist);            //释放pq->plist = tmp;    }pq->size--;               //有效数据个数--;}

4.取队头的数据

QueueDateType QueFront(Que* pq){assert(pq);return pq->plist->val;   //直接返回数据}

5.取队尾的数据

QueueDateType QueBack(Que* pq){assert(pq);return pq->tail->val;    //直接返回数据}

6.获取队列中有效数据个数

int QueSize(Que* pq){assert(pq);return pq->size;}

7.判断队列是否为空

bool QueEmpty(Que* pq){assert(pq);return pq->plist;}

8.销毁队列

bool QueEmpty(Que* pq){assert(pq);return pq->plist;}

2.2总代码

#pragma once#include<stdio.h>#include<assert.h>#include<stdlib.h>#include<stdbool.h>typedef int QueueDateType;typedef struct QueueNode{struct Queue* next;QueueDateType val;}QNode;typedef struct Queue{QNode* plist;QNode* tail;int size;}Que;void QueInit(Que* pq);void QueDestory(Que* pq);void QuePush(Que* pq,QueueDateType x);void QuePop(Que* pq);QueueDateType QueFront(Que* pq);QueueDateType QueBack(Que* pq);int QueSize(Que* pq);bool QueEmpty(Que* pq);

#include"Queue.h"void QueInit(Que* pq){assert(pq);pq->plist = pq->tail = NULL;pq->size = 0;}void QueDestory(Que* pq){assert(pq);QNode* cur = pq->plist;QNode* Next = NULL;while (cur){Next = cur->next;free(cur);cur =Next;}pq->plist = pq->tail == NULL;}void QuePush(Que* pq, QueueDateType x){assert(pq);QNode* newnode = (QNode* )malloc(sizeof(QNode));    //创建一个节点if (newnode == NULL){perror("malloc fail");      //判断exit(-1);}newnode->next = NULL;     //将后节点置空处理newnode->val = x;         //赋值if (pq->plist == NULL)     //队列为空{pq->plist= pq->tail = newnode;}else                        //队列不为空{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;               //有效数据个数++}void QuePop(Que* pq){assert(pq);assert(pq->size);   //当队列为空时，不出数据QNode* tmp = NULL;if (pq->size==1)          //当队列的有效数据只有一个时，需要特殊处理{                          //因为出队列后，为空列表了，尾指针需要改变free(pq->plist);pq->plist = pq->tail == NULL;}else                       //队列不为空，直接头删{tmp = pq->plist->next;     //先保存下一个节点free(pq->plist);            //释放pq->plist = tmp;    }pq->size--;               //有效数据个数--;}QueueDateType QueFront(Que* pq){assert(pq);return pq->plist->val;   //直接返回数据}QueueDateType QueBack(Que* pq){assert(pq);return pq->tail->val;    //直接返回数据}int QueSize(Que* pq){assert(pq);return pq->size;}bool QueEmpty(Que* pq){assert(pq);return pq->plist;}

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/xuetang/2024-03-24/147878.html，文章来源：网络cs，作者：淼淼，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！