题22
题目
【2014 统考真题】循环队列放在一维数组 A[0...M - 1] 中,end1 指向队头元素 end2 指向队尾元素的后一个位置. 假设队列两端均可进行入队和出队操作, 队列中最多能容纳 M - 1 个元素. 初始时为空. 下列判断队空和队满的条件中,正确的是 ()
A. 队空: end1 == end2;
队满: end1 == (end2 + 1) mod M
B. 队空: end1 == end2;
队满: end2 == (end1 + 1) mod (M - 1)
C. 队空: end2 == (end1 + 1) mod M;
队满: end1 == (end2 + 1) mod M
D. 队空: end1 == (end2 + 1) mod M;
队满: end2 == (end1 + 1) mod (M - 1)
分析
解
A
end1 指向队头元素, 可知出队操作是先从 A[end1] 读数, 然后 end1 再加 1 。
end2 指向队尾元素的后一个位置, 可知入队操作是先存数到 A[end2], 然后 end2 再加 1 。
若用 A[0] 存储第一个元素, 队列初始时, 入队操作是先把数据放到 A[0] 中, 然后 end2 自增, 即可知 end2 初值为 0 ;
而 end1 指向的是队头元素, 队头元素在数组 A 中的下标为 0 , 所以得知 end1 的初值也为 0,可知队空条件为 end1==end2;
然后考虑队列满时,因为队列最多能容纳 M - 1 个元素,假设队列存储在下标为 0 到 M - 2 的 M - 1 个区域,队头为 A[0] ,队尾为 A[M - 2] ,此时队列满, 考虑在这种情况下 end1 和 end2 的状态, end1 指向队头元素, 可知 end1 = 0, end2 指向队尾元素的后一个位置,可知 end2=M-2+1=M-1,所以队满的条件为 end1==(end2+1) % M