一.简介
在哔哩哔哩看视频学的,赫斌老师数据结构入门的内容-b站搜索:av6159200(P47),通过学习循环队列,能独立把赫斌老师教的敲出来,并且自己摸索着实现链式队列.
第三部分最后面有我链式队列的ppt图解下载
二.什么是队列
队列与栈有一个明显的区别就是,栈是先进后出,而队列是先进先出.
队列与栈有一个相同点就是那就是一开始都i有顶部(top)和底部(bottom),但是为了与栈产生区别,我们队列用前部(front)和后部(rear).
数组的队列为什么要是循环队列呢?
因为数组刚开始的长度是确定的,如果每次出队之后不循环的话,就造成空间浪费,并且越用越少.
如图:
5个数组插入了4个
4个已插入数值的元素删了三个
通过图可以看出,如果数组不是循环的话,0,1,2这3个数组以后都用不了了,所以数组队列需要循环
至于链表,他就没有要循环的要求,它在内存充足的情况下,可以一直无限增加...
先进先出图解:
先进先出
先进先出
从图可以看出,只要是第一个进的就是第一个出的,队列就是要满足这样的要求.就跟我们车站排队买票一样.
三.循环队列的图解
空队列
添加一个
继续添加
放满
空与满对比
另外的一中方法
一定在移动的时候要用这个 前部 = (前部+1)%数组长度 后部 = (后部+1)%数组长度 的循环公式
不过我个人觉得如果用判断语句应该也行, 就是如果前部或者后部等于数组长度 前部或者后部就重新变成0, 但是这样过于麻烦了而且感觉程序会变慢.所以还是建议用上面的公式吧.
循环队列其它过程:百度网盘
链式队列的图解:百度网盘
四.函数功能实现的源码
void init(QUEUE *); //初始化
初始化
void lnput_queue(QUEUE *, int ); //入队 输入
入队 输入
int full_queue(QUEUE *); //判断是否满
判断是否满
void traversing_queue(QUEUE *); //遍历输出
遍历输出
int air_queue(QUEUE *); //判断是否为空
判断是否为空
int out(QUEUE *, int *); //出队
出队
五.源码分享(可复现)
循环队列(数组):百度网盘
链式队列(链表):百度网盘
六.队列的应用
一切与时间相关的都与队列有联系.
网友评论