Java Reference
In-Depth Information
The circular queue works by reusing space in the array that is freed when elements
are retrieved. Thus, it can store an unlimited number of elements as long as elements
are also being removed. While conceptually simple—just reset the appropriate index
to zero when the end of the array is reached—the boundary conditions are a bit con-
fusing at first. In a circular queue, the queue is full not when the end of the underly-
ing array is reached, but rather when storing an item would cause an unretrieved item
to be overwritten. Thus,
put( )
must check several conditions in order to determine if
the queue is full. As the comments suggest, the queue is full when either
putloc
is
one less than
getloc
, or if
putloc
is at the end of the array and
getloc
is at the begin-
ning. As before, the queue is empty when
getloc
and
putloc
are equal. To make these
checks easier, the underlying array is created one size larger than the queue size.
5.
Put into
IQDemo.java
the
DynQueue
class shown next. It implements a “growable”
queue that expands its size when space is exhausted.
