As a container, the array has the advantage of fast access to each element, but the disadvantage of a fixed size. The vector, which you learned about in Chapter 13, gets around the latter problem by hiding an underlying buffer (stored in an array), and storing both a pointer to the array and the current size of the array.
The capacity is the number of elements in the array. When the size exceeds the capacity, the array is copied into a new array that is twice the size of the original. Then the new value is inserted.
As we will see in lectures, the vector is a very good data structure for a number of different types of abstractions, including stacks. However, since inserting or removing a value from the front of a vector is not very efficient, the vector is not very good at implementing a queue (insertion at one end, removal at the other) or a deque (insertions and removals from either end).
We can get around this problem by creating a vector like data structure that allows the elements in a container to start at a position other than zero. The starting position is stored as an index, along with the current number of elements. This is illustrated by the picture at the bottom of page 765 of the text. (Only I suggest you store the size, rather than the position of the first unused location).
Now new elements can be added to either end. When adding an element to the front, the starting position is decremented, and the size increased. When adding an element to the end, the size is increased. As before, if the size exceeds the capacity, the elements are copied into a new buffer.
The complexity of the deque (or, as cay calls it on page 765, a circular array) comes from the fact that the elements can now wrap around the end of the array. This is illustrated by the picture at the top of page 766.
Your task will be to implement a deque using these ideas. Your abstraction should be stored in a file named Deque.java. It should implement the following methods:
public class Deque {
public void addFirst(Object value);
public void addLast(Object value);
public Object firstElement() { return elementAt(0); }
public Object lastElement() { return elementAt(size() - 1); }
public void removeFirst();
public void removeLast();
public Object elementAt(int index);
public int size();
public Enumeration elements();
}
Notice that in addition to allowing elements to be inserted
or removed from either end, you must also provide access to any
element using the method elementAt. This returns the element stored
at the logical position given by the index (that is, the first element
is zero, the second is 1, and so on). The position of this element
in the underlying array is almost certainly different. I have emphasized
this fact by providing implementations for the methods firstElement
and lastElement. Your method should throw NoSuchElementException
if an attempt is made to access a value from an empty collection.
Start with a buffer of size 4, and use the technique of doubling the buffer when the size exceeds the capacity.
You are also required to provide an Enumerator for your container. This is an instance of a class that implements the interface defined in java.util.Enumeration. This interface consists of two methods, hasMoreElements, and nextElement. You can assume that enumeration is not done at the same time as elements are added or removed.
Notice I have not said anything about a main program. You will probably want to write one for your own testing purposes, but the main that will be used in grading the assignment will be provided by the TA. Your program should not do any input or output, the only output will be that provided by the TA supplied main program.