设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，_

wangChaoNK

注意本题的索引下标是从1开始所以循环队列中最多有n个元素
在循环队列中,头指针指向队列当中的第一个元素,而尾指针指向最后一个元素的下一位

假设循环队列的队尾指针是rear，队头是front，其中QueueSize为循环队列的最大长度。

(1) 入队时队尾指针前进1：(rear+1)%QueueSize

(2) 出队时队头指针前进1：(front+1)%QueueSize

(3) 队列长度：(rear-front+QueueSize)%QueueSize

现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据)

答案：(rear-front+N)%N

(4) 队空和队满的条件

为了区分队空还是堆满的情况，有多种处理方式：

方式1：牺牲一个单元来区分队空和队满，入队时少用一个队列单元，即约定以"队头指针在队尾指针的下一位置作为队满的标志"。

队满条件为：(rear+1)%QueueSize==front

队空条件为：front==rear

队列长度为：(rear-front++QueueSize)%QueueSize

方式2：增设表示队列元素个数的数据成员size，此时，队空和队满时都有front==rear。

队满条件为：size==QueueSize

队空条件为：size==0

方式3：增设tag数据成员以区分队满还是队空

tag表示0的情况下，若因删除导致front==rear，则队空；

tag等于1的情况，若因插入导致front==rear则队满

发表于 2017-06-07 21:36:57 回复(0)

慕宗悫之长风

举个例子，一个循环队列，队列长度N=10，下标从1-9，能够储存9个元素，index=0处为空。初始时，头指针下标为1，尾指针下标为1。当从队尾入队一个元素，尾指针下标移动，当从队首出队一个元素，头指针下标移动。头指针指向对首，尾指针指向队尾的下一位。第一步，执行入队操作。入队9个元素，队列满，此时头指针下标为1，尾指针下标为0；第二步，执行出队操作。头指针向后移动，比如此时出队3个元素，头指针移动到下标指向4，尾指针依然下标为0，此时队列中有6个元素。第三步，执行入队操作。头指针不变，指向下标为4，加入两个元素，此时尾指针的下标从0指向2，此时队列中有8个元素。结果：头指针指向4，尾指针指向2，队列中有8个元素。（2+10-4）%10=8 循环队列靠指针来执行入队出队。若用数组实现的普通队列，index=0的元素出队后，要把后面的元素全部遍历一遍做向前移动的操作；若用普通链表实现的队列，出队时要遍历到链表最后一位的前一位，再断开。

发表于 2019-08-19 09:37:06 回复(0)

牛客626990132号

D.循环队列会空出一个位置，为了判断队列为满的状态，即当(rear+1)mod n==front为满，所以牺牲一个空格，所以rear-front的绝对值为队列中元素的个数（因为rear指向一个尚未填入元素的内存，所以不用加1），(rear-front+n)就是为了保证绝对值，所以为（r-f+n）mod n

发表于 2020-06-28 16:07:38 回复(0)

大将军豆腐脑好

不懂。。。

发表于 2017-05-10 13:20:03 回复(2)

cquptybs

循环队列不是两种实现方式吗，记得有一种是不要空出一个来的啊

发表于 2021-03-22 08:47:26 回复(0)

真的会谢的芹菜很刻苦

在循环队列中头指针指向队列当中的第一个元素,而尾指针指向最后一个元素的下一位。

队列长度公式推导

Q.r有大于、小于和等于Q.f三种情况

一下推导假设MaxSize=10

1、Q.r>Q.f

假设Q.r=6, Q.f=2，则现在队列占得单元有Q.data[2], Q.data[3], Q.data[4], Q.data[5], 那么队列长度L= Q.r - Q.f = 6-2=4。

2、Q.r=Q.f

假设Q.r=2, Q.f=2，则现在队列占得单元有空, 那么队列长度L= Q.r - Q.f = 2-2=0。

3、Q.r<Q.f

假设Q.r=2, Q.f=6，则现在队列占得单元有Q.data[6], Q.data[7], Q.data[8], Q.data[9], Q.data[0], Q.data[1], 那么队列长度L= MaxSize - Q.f + Q.r = 10 - 6 + 2 =6。也即L=Q.r-Q.f+MaxSize .

综上所诉，根据数学取余的性质：(x+ky)%y=x (注x<y, k属于N），可归纳总结队列长度公式有：

L=(Q.r-Q.f+MaxSize)%MaxSize。

发表于 2022-05-13 16:09:11 回复(0)

冲吖Offer

注意本题的索引下标是从1开始所以循环队列中最多有n个元素在循环队列中,头指针指向队列当中的第一个元素,而尾指针指向最后一个元素的下一位假设循环队列的队尾指针是rear，队头是front，其中QueueSize为循环队列的最大长度。 (1) 入队时队尾指针前进1：(rear+1)%QueueSize (2) 出队时队头指针前进1：(front+1)%QueueSize (3) 队列长度：(rear-front+QueueSize)%QueueSize 现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据) 答案：(rear-front+N)%N (4) 队空和队满的条件为了区分队空还是堆满的情况，有多种处理方式：方式1：牺牲一个单元来区分队空和队满，入队时少用一个队列单元，即约定以"队头指针在队尾指针的下一位置作为队满的标志"。队满条件为：(rear+1)%QueueSize==front 队空条件为：front==rear 队列长度为：(rear-front++QueueSize)%QueueSize 方式2：增设表示队列元素个数的数据成员size，此时，队空和队满时都有front==rear。队满条件为：size==QueueSize 队空条件为：size==0 方式3：增设tag数据成员以区分队满还是队空 tag表示0的情况下，若因删除导致front==rear，则队空； tag等于1的情况，若因插入导致front==rear则队满

发表于 2020-06-20 10:51:55 回复(0)