队列是一种特...
方法一:指针法
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端 front 进行删除操作,而在表的后端 rear 进行插入操作。
要求第一个进入队列的元素储存在 A[0] ,即队头位于 0 ,设此时队头指针和队尾指针分别为 front′ 和 rear′ 。
A[0] 入队后,front′ 为 0 ,入队元素增加在队尾,队尾指针 +1 ,rear′ 指向 0 ,即 (rear+1)modn=rear′ ,解得 rear=n−1 ,由于没有出队操作,队头指针不变,即 front=front′=0 。
本题选B。
方法二:开闭区间法
指针操作通常难度比较大,我们有没有更好的办法来解决这个问题,我们可以不从过程出发,直接从结果出发。
首先,先引入开闭区间的相关知识。
对于表示一段连续整数,通常有两种表示方法,假设
,表示从 a 到 b 的所有整数,包括 a 和 b 。
方案一:枚举 x=a,a+1,a+2,…,b−1,b 。
方案二:区间
,或者
。
通常第二种写法更加简洁,除了闭区间,还有开区间,下面默认
,有四种写法:
闭区间: 
左闭右开:
左开右闭:
开区间: 
四种表示方法各有优劣,一般具体问题具体分析。
我们把开闭区间模型套用在队列上,队列中元素下标为一连串整数,设队头为区间左端点,队尾为区间右端点,教科书上的循环队列中队头指针指向队头元素位置,队尾指针指向队尾元素位置的下一个位置,是一个左闭右开模型,有位置
,当 front=rear 时,显然有
,即
。
现在回到本题,题目要求队列非空时, front 和 rear 分别指向队头元素和队尾元素。明显套用闭区间模型,有位置
,初始时队列为空,有
,推出 rear=front−1=0−1=−1 ,由于循环队列位置非负,将 −1 修改为 (−1+n)modn=n−1 即可。
本题选B。
登录后提交答案