首页 > 试题广场 >

有一个用数组C[1..m]表示的环形队列,m为数组的长度。假

[单选题]
有一个用数组C[1..m]表示的环形队列,m为数组的长度。假设f为队头元素在数组中的位置,r为队尾元素的后一位置(按顺时针方向)。若队列非空,则计算队列中元素个数的公式应为?
  • (m+r-f) mod m
  • r-f
  • (m-r+f) mod m
  • (m-r-f) mod m
  • (r-f) mod m
  • 需要判断边界
推荐
选A

分情况讨论:
1. 若f<r<=m, 则有r-f <m,即队尾没有超出边界,则为r-f
2. 若r<f<=m, r-f < 0, 即队尾超出边界m,那么应为m+r -f
综合两种情况,得到答案 (m+r-f) mod m
编辑于 2015-02-02 10:38:41 回复(0)
记住两个公式:队列中,队列满的条件是:(rear+1)%QueueSize=front;
                                      队列长度公式是:(rear-front+QueueSize)%QueueSize。
发表于 2015-09-05 15:33:00 回复(2)
答案:A
如果r>f则元素个数为r-f
如果r<f,则元素个数为r-f的补集,也就是m+r-f
统一起来就写成(m+r-f)mod m
发表于 2015-01-28 18:13:15 回复(0)
注意数组C[1..m]下标从1开始,并且r为队尾元素的后一位置。
当r>f时,好说,队列的长度为r-f;
当r<f时,队列的长度分为两段,一段是m-f+1,一段是r-1,加在一起,队列长度为r-f+m;
当r=f时,队列长度可能为0也可能为m,实际编程时,会设置一个boolean型变量来区分。
因此通用的计算队列长度公式为:(r-f+m)%m
编辑于 2015-08-20 21:07:03 回复(2)
mod求余
发表于 2016-06-02 19:58:28 回复(0)
做题之前需要了解环形队列和取模运算
解题过程参考下图:

编辑于 2022-06-29 10:15:51 回复(0)
网上找了一张图
队列入队时候判断(rear+1)%QueueSize==front?来知道满了没有,满了就不能入队,实际上数组中会留下一个空位置。
发表于 2018-09-21 08:40:18 回复(0)
画图理解,将两个长为m的数组拼在一起,前一个数组中标明f位置,后一个数组中标明r的位置,不难看出f和r之间的距离就是m+r-f。
发表于 2022-08-25 15:38:59 回复(0)

队列中,队列满的条件是:(rear+1)%QueueSize=front;

队列长度公式是:(rear-front+QueueSize)%QueueSize。



发表于 2019-06-06 11:17:53 回复(0)
我有个问题: 这个队列的长度要是比数组还长了?那就不是这个结果了
发表于 2017-03-29 23:38:24 回复(1)
第一反应是取特殊情况验证,假设数组刚好装满,则有(m-1)+1个,所以是r-f+1,考虑到是环形,所以是(r-f) mod m + 1,和A等同
发表于 2015-08-05 13:40:10 回复(0)
A
r>f --> r-f
r<f --> r+m-f
发表于 2015-03-12 14:51:21 回复(0)
这个有时要根据语言有所区分,对于负数取模的处理,python等一些是数学上的取模,而C则是正数取模加符号
发表于 2022-02-18 19:30:35 回复(0)
有个问题:入队是队尾在动还是队头在动?
编辑于 2024-03-05 19:41:44 回复(0)
如果r>f则元素个数为r-f 如果r
发表于 2023-02-15 23:43:41 回复(0)
想问问e有什么区别
发表于 2022-10-25 08:41:10 回复(0)

说实话,我没太能理解,两种情况综合考虑的话,第二种r小于f是怎么能得到这个公式的

发表于 2019-03-13 08:17:56 回复(1)