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
http://java.sun.com/docs/books/tutorial/collections/interfaces/queue.html
 
 
Search WWH ::




Custom Search