I like to introduce inheritance in a more significant way by introducing you to the concept of abstract vs. concrete classes. We will design a class hierarchy for Queues that hold any objects.
First off, regardless of how a queue is implemented, we are interested
in its FIFO behavior. Here we would like to be able to provide applications
the flexibility of choosing implementation at run time. To achieve this, we
will first design a interface Queue.
package csc241.samples.Queue;
public interface Queue {
public boolean empty();
public boolean full();
public Queue enqueue(Object x) throws Exception;
public Queue dequeue() throws Exception;
public Object peek() throws Exception;
}
The word package csc241.samples.Queue; makes Queue part of a package called csc241.samples.Queue. There is a direct relationship between directory names and packaging. public_html/classes is defined in my CLASSPATH statment in my .cshrc file, in yours this path is defined as public-html/classes. When we name a package csc241.samples.Queue, we effectively saying that there is a csc241 directory in the classes directory, and there is a samples directory in the csc241 directory, and a Queue directory in samples. It is also expected that all members of this package will reside in that directory and will have a "package" header as shown for the interface Queue.
The word interface instead of the usual word class means that we wish to avoid providing implementation or code at this point.
Suppose we declare an object of Queue with a statement
such as, Queue q;. Understand the difference between
declaring and constructing. When we declare q, we simply say
that it will be a Queue. You can see that there is no constructor in
the interface Queue, so, you can't say something like
Queue q = new Queue(...);. If
you think about it, it all makes sense--if you don't have any variables
in this class then what could you construct, what could you set?
Obviously, we need code in order for our q variable
to actually behave like a queue. We also need it to have some way of
storing the objects that we queue into it. This happens in concrete
classes that inherit Queue. Concrete refers to classes that have
code along with structures and variables that hold data. An statement
like Queue q = new fixedQueue(20); in an application that
imports our csc241.samples.Queue package will be able to execute this
statement and put objects in q and take elements out.
fixedQueue class provides us with one implementation for Queue. This class will hold the objects in an array which is of a fixed length determined when a queue is constructed. There are plenty of applications where with reasonable certainty we can choose a fixed size for our queue or we don't the queue to grow indefinitely. For example, in an operating system that follows a time-slicing protocol for its scheduler, we can process requests by storing them in processing queue as they are made. processes are stored in a queue as they come in, when it is their turn, they get taken off the queue and get processed. If a process needs more time than the time slice the system assigns it, it get processed for the duration that it can, and then go back to the queue and wait to be processed again. A queue implemented with an array works well in this case if we have a max limit on how many processes are allowed in the system at the same time.
There are several variations to array implementation of a queue. The easiest is to maintain a last index that holds the position of the last element. Each time enqueue is invoked, we increment last and place the new element there. When dequeue is invoked, we remove what is in the zero cell and move all elements back by one cell. this technique was discussed in Object Queue class last time. With fixedQueue, we won't employ this technique. We are going use a circular queue. In the previous approach, note that the front of the queue is stationary, always in position zero. In a circular queue, we use a last and a first index. Each time enqueue is invoked, we change last to point to the next available space and place the new element there. When dequeue is invoked, we remove the element in front and move first to next occupied cell. The advantage in using the circular queue in place of the simple version discussed earlier should be obvious: in the simple version, every time you dequeue an element, the rest have to move back, no such movement is needed with a circular queue.
Moving to the next cell, in either enqueue or dequeue
may require to circle around to the beginning. Let me demonstrate with an
example. Assume This array of elements represents our queue with existing
content and values for the first and last indexes.
first=0 last=3
--------------------------------------------
| jones | morris | vax | fays | |
--------------------------------------------
0 1 2 3 4
Lets enqueue "new" into this queue.
first=0 last=4
--------------------------------------------
| jones | morris | vax | fays | new |
--------------------------------------------
0 1 2 3 4
Lets dequeue one element from this queue. Note that you don't have
to physically remove "jones" from the array.
first=1 last=4
--------------------------------------------
| jones | morris | vax | fays | new |
--------------------------------------------
0 1 2 3 4
Lets enqueue "circle" into this queue. Notice that we rap around
since we have no more cells on the right, but there is available space at
the beginning. It is strange to see last be behind first, but that is how
circular queues work.
last=0 first=1
--------------------------------------------
| circle | morris | vax | fays | new |
--------------------------------------------
0 1 2 3 4
It is simple to implement, The private method next is written
to accomplish changing the two indexes in enqueue or dequeue.
private int next (int pos) {
if (pos == size_-1)
return 0; // allow rap-around
else
return pos+1;
}
How is full determined? next(last_) == first_ simply says that if last is moved to the next cell, it will run into the first.
There are a couple of other things for you to note. first and
last are set to -1 when queue is empty. The constructor
for the fixedQueue is parameterized to let the application set the
size that it wants. The statement q=new Object[size];
creates the array q at run time using the size provided by the
application. Of course, this size is fixed for the life of the object
created. The code for enqueue, dequeue, and peek, except for the notion
of the queue being circular is very much like the what was discussed in
Object Queue class