In recent lectures, we discussed the use of Interfaces to define a behavior while leaving the implementation of that behavior to other classes. In this lab you will utilize all of these topics to build a simple yet useful new class. Consider the following interface describing the methods for a simple double ended queue (or deque):
public interface SimpleDeque
{
public void addFront(Object X); // Add Object X at front of list
public void addRear(Object X); // Add Object X at rear of list
// If array is full, add methods should do nothing
public Object removeFront(); // Remove and return Object X from
// front of list
public Object removeRear(); // Remove and return Object X from
// rear of list
// If array is empty, remove methods should return null
}
We have discussed or will discuss the properties of a queue in upcoming lectures, but it has the general behavior such that items are added at the rear and removed from the front, thereby giving a First In First Out (FIFO) access to the items added and subsequently removed from the list. No other manipulations of the data are permitted (for example, we cannot add or remove anywhere in the middle). Looking at it "in reverse", we could add new items at the front of the queue and remove them from the rear. This is still providing FIFO access, but just from a different point of view. Now consider both adding and removing items at the rear of the list (without ever accessing the front). This is called stack access and gives us Last In First Out (LIFO) access to the items (the data is removed in reverse order). The same behavior occurs if we both add and remove at the front without ever accessing the rear of the list.
The simple deque above is expressed as an interface rather than a class because we are not describing the data or how it is represented -- we are simply describing its access behavior. However, to actually build a working deque, we need a class that implements the interface above. For example:
public class MyDeque implements SimpleDeque
{
private Object [] theData;
private int numItems;
public MyDeque(int maxItems)
{
theData = new Object[maxItems];
numItems = 0;
}
// Implementation of the four methods of SimpleDeque, plus
// perhaps other methods as well
}
Note that the implementation above uses an array of Object to store the items in the deque. Since Object is the base class to all other Java classes, an array of Object can thus be used to store any Java class types (we can even store primitive values if we utilize their wrapper classes). Also note that nothing in the SimpleDeque interface requires an array to be used to store the data. You will see in your CS 0445 course that a linked list may in fact be a better implementation than an array in this case. However, for this implementation we will use an array because it is simple and easy to understand.
Another important thing to notice about the partial implementation above is
that the size of the array used is not equal to the number of items in the deque.
The number of items in the deque is maintained in the separate int variable,
numItems. Since Java array sizes are fixed once the array object is created, to
avoid having to recreate new array objects with each add or removal we simply
allocate an array that is some reasonable size (specified by the parameter in
the constructor) when we create the deque. At that time we also set numItems to
zero since there are no actual items in the deque. We then increment numItems
with each addition and decrement numItems with each removal.
Adding or removing at the rear of the array is a relatively simple process --
to add we simply put the new object in location numItems and then
increment numItems. To remove we store the last item in a temp
object, decrement numItems and then return the item. It is
probably a good idea to also set the location back to null before returning.
Adding or removing at the front of the array is a bit more complicated. For this simple implementation we will do it in the following way:
addFront(): move objects in locations 0..numItems-1 over one spot to
"the right" (i.e. into locations 1..numItems), then put the new object into
location 0 and increment numItems. For example, given the array below of length
9 with 6 items in it, doing an addFront of 25 will have the effect shown in the
three lines below:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 50 | 30 | 10 | 40 | 20 | 20 | 80 | ||
| 50 | 30 | 10 | 40 | 20 | 20 | 80 | ||
| 25 | 50 | 30 | 10 | 40 | 20 | 20 | 80 |
removeFront(): store the object in location 0 in a temp
variable, then move objects in locations 1..numItems-1 over one
spot to "the left" (i.e. into locations 0..numItems-2). Set location
numItems-1 to null, decrement numItems and return the temp object. In
effect, you are doing the opposite of what is shown in the addFront above.
NOTE: Your class does NOT have to and should NOT resize its array. If the user attempts to add an item and the array is full, do nothing.
Download the following two files. Compile Lab7.java with your MyDeque.java and the SimpleDeque.java files in the same directory. The output you get should be that shown below.
Output:
javalab>java Lab7 Queue adds at rear and removes at front 0 1 2 3 4 Queue adds at front and removes at rear 0.0 2.0 4.0 6.0 8.0 10.0 12.0 14.0 Stack adds and removes at rear Marge Ingmar Ingrid Bertha Herb