Java Reference
In-Depth Information
support are detailed by the following interface:
1
-
add
or
queue
: Add an element at the
tail
of the queue,
-
process
or
remove
: Process the
first
element of the queue.
These queues are also equipped with a predicate
empty
that tells us whether
the queue is currently empty or not. Queues are one example of abstract
data-structures that can be implemented using various data-structures at their
backbone. We start from the most common implementation that uses arrays
of prescribed size: That is, arrays with sizes fixed once for all. We manipulate
two indices in this array, say:
-
freePlace
: Denote the index of the
first
free remaining place in the array.
-
lastProcessed
: Denote the index of the
last
processed object initially set to
−
1).
Figure 8.1 illustrates these notations. The array acts as a buffer for storing the
incoming objects.
Figure 8.1
A queue implemented
using an array requires two indices
to indicate the last processed ele-
ment and the first free location
O
1
O
2
O
3
freePlace
lastProcessed
8.2.2 Basic queue implementation: Static functions
We implement the
add
/
process
functions defined in the interface of queues
using an array encapsulated into a tailored class. For example, let us consider
queues for incoming sequences of
double
numbers. Whenever we call a
process
operation while the queue is empty, we choose by convention to return a special
code: Here, chosen as
1
.
0. The straightforward code for implementing these
add
/
process
and
empty
operations is given below:
−
Program 8.1
A
double
queue with interface primitives implemented using
static functions
class
QueueDouble
static int
lastProcessed=
−
1;
static int
freePlace=0;
1
Java provides the queue interface in its own API as explained in
Search WWH ::
Custom Search