海南那个网站可以做车年检,汽配外贸平台有哪些,学校网站如何做,做网站app需要懂些什么#x1f339;个人主页#x1f339;#xff1a;喜欢草莓熊的bear #x1f339;专栏#x1f339;#xff1a;数据结构 前言 上期博客介绍了” 栈 “这个数据结构#xff0c;他具有先进后出的特点。本期介绍“ 队列 ”这个数据结构#xff0c;他具有先进先出的特点。 目录… 个人主页喜欢草莓熊的bear 专栏数据结构 前言 上期博客介绍了” 栈 “这个数据结构他具有先进后出的特点。本期介绍“ 队列 ”这个数据结构他具有先进先出的特点。 目录
前言
一、队列
1.1队列的概念及结构
1.2队列的实现
1.2.1队列结构体定义
1.2.2初始化和销毁
1.2.3队尾插入和队头删除
1.2.3.1队尾插入
1.2.3.2队头删除
1.2.4获取队头与队尾数据
1.2.5返回队列里面的元素个数
1.2.6队列判空
1.3测试代码
1.4代码展示
头文件 实现功能文件.c
总结 一、队列
1.1队列的概念及结构 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有 先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为 队尾 出队列进行删除操作的一端称为 队头。 根据队列的特点我们设计了以下队尾用来入数据队头用来出数据。 1.2队列的实现 队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 1.2.1队列结构体定义
根据上面提到的我们基于链表这里的链表代指单链表来实现队列。所以我就定义以下结构体
typedef int QDataType;typedef struct QueueNode//我们基于单链表创建的队列节点
{struct QueueNode* next;//下一节点的地址QDataType val;
}QNode; 根据内容发现我们要获取队列的队头数据和队尾数据所以我们要创建两个这样的结构体。由于节点的地址是通过一级指针来表示的所以要用二级指针来储存所以我们传参数时要使用二级指针。 记住只要涉及通过形式参数改变实参的都要传地址。
这时我们很牛的杭哥就给了一个思路那就是再创建一个结构体里面的元素是上一个结构体。这样既满足了队头和队尾指针还不需要传二级指针。因为有一个计数的功能所以再定义一个计数的变量。
typedef struct Queue //因为我们要传头指针和尾指针所以我们要传两个指针//我们又要传二级指针但是呢很麻烦所以我们就新创建一个结构体来储存//上一个结构体的指针。
{QNode* phead;//队头指针QNode* ptail;//队尾指针int size;
}Queue;
1.2.2初始化和销毁
初始化这一步和上次写的栈的初始化可以说是十分相似第一步还是判断传来的是否为空队列把结构体里面的指针置为NULL再把size赋值位0。就ok了。
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}
销毁因为要申请空间必定需要free因为我们是基于链表实现的参考一下单链表的销毁。 所以我们也需要一个一个节点释放最后把指针指向空指针把size赋值为0. void QueueDestory(Queue* pq)
{assert(pq);QNode* pur pq-phead;while (pur){QNode* cur pur-next;free(pur);pur cur;}pq-phead pq-ptail NULL;pq-size 0;
}
1.2.3队尾插入和队头删除
1.2.3.1队尾插入
因为我们是基于单链表的实现的所以只需要创建节点就可以了通过malloc申请空间。添加一个节点就开辟一块空间。
链表不为空很简单直接进行尾插操作不要忘了给size。
链表为空那就把头和尾指针同时指向这个新节点。
判别是否为空链表少不了。
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* Newnode (QNode*)malloc(sizeof(QNode));if (Newnode NULL){perror(malloc fail);return;}Newnode-next NULL;Newnode-val x;if (pq-pheadNULL)//空链表{pq-phead pq-ptail Newnode;}else{pq-ptail-next Newnode;pq-ptail Newnode;}pq-size;//用来计数
}
1.2.3.2队头删除
链表中只有一个节点当phead ptail 时就只有一个节点了所以我们把这个节点释放了以后要把phead 和 ptail 都置为空指针预防出现野指针。
多个节点我们创建一个节点用来储存头节点的下一个指针这样释放了头节点也可以找到剩下的节点。对头删除当然要size--。
老生常谈判断是否为空链表还要判断是否还可以进行队头删除操作。也就队列里面还有数据吗
void QueuePop(Queue* pq)
{assert(pq);assert(pq-phead);if (pq-phead pq-ptail)//只有一个节点{free(pq-phead);pq-phead pq-ptail NULL;}else//多个节点{QNode* tmp pq-phead-next;free(pq-phead);pq-phead tmp;}pq-size--;
}
1.2.4获取队头与队尾数据
很简单返回指针里面储存的数据就可以了除了判断队列是否为空。还要判断这些头尾指针是否为空的。
QDataType QueueFront(Queue* pq) //返回队头数据
{assert(pq);assert(pq-phead);return pq-phead-val;
}QDataType QueueBack(Queue* pq) //返回队尾数据
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}
1.2.5返回队列里面的元素个数
这时就可以体现出我们再第二给结构体中创建size的价值了我们直接返回size。没有创建size我们就需要遍历队列了。
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
1.2.6队列判空
前面创建的szie又帮了大忙还可以用来判断是否为空对列。
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
1.3测试代码
进行了4个数据的插入检测了判空、获取队头元素、队头删除。等操作在这里还是建议大家每完成一个功能就进行测试不然一起测试出现了很多问题修改起来很麻烦的。作者身有体会
#define _CRT_SECURE_NO_WARNINGS
#includeQueue.hint main()
{Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);printf(%d , QueueFront(q));QueuePop(q);QueuePush(q, 3);QueuePush(q, 4);while (!QueueEmpty(q)){printf(%d , QueueFront(q));QueuePop(q);}QueueDestory(q);return 0;
} 成功实现了队列 “ 先进先出 ”的特点。
1.4代码展示
头文件
Queue.h
#pragma once
#includestdio.h
#includestdbool.h
#includeassert.h
#includestdlib.htypedef int QDataType;typedef struct QueueNode//我们基于单链表创建的队列节点
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue //因为我们要传头指针和尾指针所以我们要传两个指针//我们又要传二级指针但是呢很麻烦所以我们就新创建一个结构体来储存//上一个结构体的指针。
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化和销毁
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);//队尾插入和队头删除
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);//获取队头、尾数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);//返回个数和判空
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq); 实现功能文件.c
Queue.c
#define _CRT_SECURE_NO_WARNINGS
#includeQueue.hvoid QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}void QueueDestory(Queue* pq)
{assert(pq);QNode* pur pq-phead;while (pur){QNode* cur pur-next;free(pur);pur cur;}pq-phead pq-ptail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* Newnode (QNode*)malloc(sizeof(QNode));if (Newnode NULL){perror(malloc fail);return;}Newnode-next NULL;Newnode-val x;if (pq-pheadNULL)//空链表{pq-phead pq-ptail Newnode;}else{pq-ptail-next Newnode;pq-ptail Newnode;}pq-size;//用来计数
}void QueuePop(Queue* pq)
{assert(pq);assert(pq-phead);if (pq-phead pq-ptail)//只有一个节点{free(pq-phead);pq-phead pq-ptail NULL;}else//多个节点{QNode* tmp pq-phead-next;free(pq-phead);pq-phead tmp;}pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq-phead);return pq-phead-val;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail);return pq-ptail-val;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
} 总结 很感谢大家的喜欢有问题大家在评论区发来我们一起交流。下期预告通过栈和队列互相实现对方的功能。
