队列定义是这样的
#define MAXSIZE 10
typedef struct{
ElemType data[MAXSIZE];
int front,rear;
} SeqQueue;
一个队列 = 一个存放元素的数组 + 一个队头指针 + 一个队尾指针
front:控制出队
rear:控制入队
我们先做个规定:
front指向队头元素
rear指向队尾元素的下一个元素(当然也可以让它直接指向队尾元素,只是在某些代码上需要相应的改动,但思想不变)
初始我们让rear = front = data[0]
元素出队:front++
元素入队:rear++
一直rear++便到达索引最大的位置,这个时候队列就满了不能再入队元素了吗?
并不,如果同时也一直有元素出队,那么还是有空闲位置可以继续入队的,那要怎么表示呢?
于是就出现了循环队列,这个类比时钟就很好理解
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210306154712216.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNDI3Mg==,size_16,color_FFFFFF,t_70)
时钟的指针到达12之后就会归0,周而复始再次循环
所以出入队指针的变化就可以表示成
元素出队:(front+1)% maxSize
元素入队:(rear+1)% maxSize
那此时的队列的长度怎么获取呢?
那就不是单纯的rear - front了,看图
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210306153659757.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkxNDI3Mg==,size_16,color_FFFFFF,t_70)
队列长度计算公式:
(
r
e
a
r
−
f
r
o
n
t
+
m
a
x
S
i
z
e
)
%
m
a
x
S
i
z
e
( rear - front + maxSize)\% maxSize
(rear−front+maxSize)%maxSize
+maxSize:目的是防止rear - front < 0
%maxSize:目的是防止当rear - front > 0时,又+ maxSize导致队列长度>maxSize
回答一下评论中的问题
为什么会rear - front < 0?
一个队列的初始状态如下图
![在这里插入图片描述](https://img-blog.csdnimg.cn/23bccb4c32c44d34802eba8861523371.png#pic_center)
当不断插入新元素时,rear指针也不断向后,直到队列末尾。
![在这里插入图片描述](https://img-blog.csdnimg.cn/011f149a6a224676bcbf406dc4759fcc.gif#pic_center)
但这只展示了只有元素入队的情况,如果同时有元素出队呢?此时front指针也会后移![在这里插入图片描述](https://img-blog.csdnimg.cn/ec8e88cdc44243c5acb2931b6edd9e4b.gif#pic_center)
所以说当rear指针已经到队列末尾时,其实队列还没满,因为有元素出队了,所以依旧可以有新元素入队,但是此时只能从前面空位插入
所以才会有rear-front<0的情况,其实相当于我们将队列首尾连接,变成一个循环队列,使得队列空间可重复利用。
![在这里插入图片描述](https://img-blog.csdnimg.cn/e0c4da7743414ae99cc4aef3cb575b8f.png#pic_center)