C语言-数据结构-队列(循环队列(数组)与链式队列(链表))

2019-08-18 本文已影响23人 Y_No_Look

一.简介

在哔哩哔哩看视频学的,赫斌老师数据结构入门的内容-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 *); //出队

出队

五.源码分享(可复现)

循环队列(数组):百度网盘

链式队列(链表):百度网盘

六.队列的应用

一切与时间相关的都与队列有联系.