4取队头元素peek()1/取队头元素publicEpeek()//队空{if (empty())throw new IllegalArgumentException("队空");return(E)data[front+1];16/92
public E peek() //取队头元素 { if (empty()) //队空 throw new IllegalArgumentException("队空"); return (E)data[front+1]; } 16/92
2.循环队列把data数组的前端和后端连接起来,形成一个循环数组,即把存储队列元素的表从逻辑上看成一个环,称为循环队列(也称为环形队列)Maxsize=8rear+解决假溢出.front 一17/92
2. 循环队列 把data数组的前端和后端连接起来,形成一个循环数组,即把存储 队列元素的表从逻辑上看成一个环,称为循环队列(也称为环形队列)。 MaxSize=8 c rear front f e d g 解决假溢出 17/92
循环队列首尾相连,当队尾指针rear=Maxsize-1时,再前进一个位置就应该到达0位置,这可以利用数学上的求余运算(%)实现:(1)队首指针循环进1:front=(front+1)%MaxSize(2)队尾指针循环进1:rear=(rear+1)%Maxsize18/92
循环队列首尾相连,当队尾指针rear=MaxSize-1时,再前进一个位 置就应该到达0位置,这可以利用数学上的求余运算(%)实现: (1)队首指针循环进1:front=(front+1)%MaxSize (2)队尾指针循环进1:rear=(rear+1)%MaxSize 18/92
Maxsize=4,初始front=rear=0rearreara204frontfrontfrontrear(b) a进队(c)b进队空队(a)aa问题:如何区分队空和队满足?003gUfrontfrontrearrear(d) c进队(e)d进队19/92
MaxSize=4,初始front=rear=0 0 2 1 3 front rear (a)空队 a 0 2 1 3 front rear (b)a进队 b a 0 2 1 3 front rear (c)b进队 c b a 0 2 1 3 front rear (d)c进队 c d b a 0 2 1 3 front rear (e)d进队 问题:如何区分队空 和队满足? 19/92
如何设计队空队满的条件?顺序队(含循环队列和非循环队列)通过front和rear标识队列状态,一般是采用它们的相对值即|front-rear|实现的。若data数组的容量为m,则队列的状态有m+1种,分别是队空、队中有1个元素、队中有2个元素、、队中有m个元素(队满)。front和rear的取值范围均为~m-1,这样|front-rear|只有m个值。显然m+1种状态不能直接用|front-rear|区分,因为必定有两种状态不能区分。为此让队列中最多只有m-1个元素,这样队列恰好只有m种状态了,就可以通过front和rear的相对值区分所有状态了。28/92
顺序队(含循环队列和非循环队列)通过front和rear标识队列状态,一 般是采用它们的相对值即|front-rear|实现的。 若data数组的容量为m,则队列的状态有m+1种,分别是队空、队中有1个 元素、队中有2个元素、.、队中有m个元素(队满)。 front和rear的取值范围均为0~m-1,这样|front-rear|只有m个值。 显然m+1种状态不能直接用|front-rear|区分,因为必定有两种状态不能 区分。 为此让队列中最多只有m-1个元素,这样队列恰好只有m种状态了,就可以 通过front和rear的相对值区分所有状态了。 如何设计队空队满的条件? 20/92