首页 > 试题广场 >

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

[单选题]
设循环队列中数组的下标范围是1–n,其头尾指针分别为f和r,则其元素个数为().
  • r- f
  • r- f +1
  • (r- f ) MOD  n+1
  • (r- f + n) MOD  n
答案选D
解析:1.头追尾。 2.尾指针指向尾节点的下一个位置 3.头指针指向头节点 
综合上述1,2,3。如果 r > f, 节点个数为 r - f
考虑溢出, 答案就为 (r - f + n) mod n
发表于 2019-10-17 20:59:21 回复(0)
begin
  write('hello world')
end.

发表于 2019-10-17 16:43:44 回复(0)
一般来说,f是指队头指针,队尾指针 r 是指向最后元素的下一个元素!!
初始化的时候f=r

front指定队首位置,删除一个元素就将front顺时针移动一位;
rear指向元素要插入的位置,插入一个元素就将rear顺时针移动一位;

要知道当front再次等于rear的时候,就是队列为空的时候。
根据题意 
开始插入元素,头指针在前尾指针在后的时候 ,元素个数则为 r-f
当循环队列满的时候,r又是等于f的,因为一圈结束了,队列满,不可再向队列中插入元素。
除非你自己设计成满了还可以插入,直接覆盖替换,元素个数始终为n,但这肯定不是题目考察的传统循环队列的定义。
满了就只能删除了,删除之后f >r了,总元素个数   n-f +1(后面个数)  +  r-1(前面个数)个,即(r+n)-f,比如n为10,f为4,r为2,则后面有10-4+1=7个元素,前面有2-1=1个元素,一共7+1=8个元素,即(2+10)-4=8个元素
综上,元素个数(r- f + n) mod  n个

发表于 2019-10-17 21:54:06 回复(0)