一.队列的原理
队列也是一种线性结构,只不过是一种受限制的线性结构,只能在其头进行删除,尾进行添加.
因为队列是线性结构,所以我们可以通过顺序表来实现,也可以通过链表来实现,本篇我们先以顺序表来实现.
只要我们掌握了顺序表,本篇就很简单.
可以联想到我们日常中的排队,先排先办事!
二.队列的结构
首先我们还是先来讲结构,很明显我们需要用到数组,为了我们能够很好的找到数组的头和尾,我们可以定义两个数.
可能你有点迷糊,没事,我来画个图:
这个rear是随着添加元素而变化的,指在数组添加元素的后面,不是最大长度的后面.
三.队列初始化
队列的初始化就是一个空数组,front和rear都指向下标0
画个图就是这样:
都等于数组下标为0的地方.
四.判断队列是否满或空
1.是否为满
这个判断就会很简单,每当我们添加一个数据时,我们对rear记录的数组下标增加1.
那么如果队列满的话,rear就会和最大长度一样,以此来判断.
2.是否为空
是否为空也很好判断了,因为我们一开始初始化就是一个空的数组,只需要判断front是否与rear相等即可.,相等即为空
五.入队操作
顺序表的入队操作就很简单了,相当于为空数组赋值就可以了,只不过我们只能依次添加,因为是队列嘛,只能尾部添加.
所以你知道为什么我们用rear了吧,用这个来当下标,进行数据的添加,每添加一次,就对其+1,后面又接着添加,直到rear等于数组最大长度了就满了,添加不了.
六.队列的遍历
就跟数组的遍历一样简单的很,一头一尾作为循环的条件.
七.出队操作
1.前移
跟顺序表一样,乾坤大罗伊,直接将front指向的位置,赋值成为其后面一个的值,最后rear减个1即可.
传的参数p,只不过是拿取要删除的值.
这里的循环条件要注意,所以的数据要向前移动一步,我们又是从front开始的,所以我们需要对rear-1进行判断,因为下面我们需要后一个也就是i+1这个下标.
如果不对rear减1,会访问越界,导致程序崩溃.
2.后指
既然我们可以通过前移,达到删除元素的效果,那我们将front向后面指一下,那不就达到删除的效果了嘛,我们访问不到.
但是你不能一直往后面移动,不然就越界了,所以对front做了一个判断.
八.其他小接口
1.获取队列首元素
2.获取队列长度
3.清除队列
酒.总结
其实当你熟悉了顺序表,那么顺序存储的队列很简单,就是数组,只不过我们特殊在头和尾部的操作.
- 队列是一种先进先出（FIFO）的数据结构。
- 队列通常具有两个基本操作：入队和出队。
- 入队操作将元素添加到队列的末尾。
- 出队操作将队列的第一个元素删除并返回。
- 队列的底层实现可以使用数组或链表。
