• Jan 20th, 2015: Created
• Jan 31 Added helpful notes in blue

Design and implement your own reusable implementations of the stack and queue ADTs in Java. The purpose of this question simply is to help you get the feel for the design of reusable classes. Thus the actual data structure programming is fairly straightforward, and you have been given most of the structure of the code. Read the following description of Double Ended Queues.

A doubly-ended queue is often called a deque. The interface for a deque is the following (which is slightly different than the one given in the textbook):

public interface Deque {
   public int size();
   public boolean isEmpty();
   public void insertFirst(Object o);
   public void insertLast(Object o);
   public Object removeFirst() throws EmptyStructureException;
   public Object removeLast() throws EmptyStructureException;
   public Object firstElement() throws EmptyStructureException;
   public Object lastElement() throws EmptyStructureException;
}

Alternatively, you can use generics to avoid having to do the cast operations. In that case the Deque interface will look like this:

public interface Deque<E> {
   public int size();
   public boolean isEmpty();
   public void insertFirst(E element);
   public void insertLast(E element);
   public E removeFirst() throws EmptyStructureException;
   public E removeLast() throws EmptyStructureException;
   public E firstElement() throws EmptyStructureException;
   public E lastElement() throws EmptyStructureException;
}

Put this interface into a file called Deque.java. Using this interface, then, write two deque implementations: one that uses an array and one that uses a linked list. These should go into files ArrayDeque.java and LinkedListDeque.java, respectively. For more information about interfaces in Java, please see the textbook.

In addition to implementing the methods in the Deque interface you will need to define instance fields, and create constructors and toString methods. The linked list deque is easy in that each method is either one line or error checking plus one line. For the Array Deque look at the curcular array implementation from the class notes. If you decide to use generics the constructor will need to use a cast operation as follows: elements = (E[]) new Object[DefaultSize]; where elements is the instance fields and E the generic type.

public class LinkedListDeque implements Deque {
   LinkedListDeque() { ... }
   ...
}

public class ArrayDeque implements Deque {
   ArrayDeque(int maxSize) { ... }
   ...
}

Thus, you need to create a class ArrayDeque, which implements the Deque interface using an array, and a class LinkedListDeque, which implements the Deque interface using a linked list. You may use classes from the Java Utilities package, but not any other libraries. Also, your ArrayDeque class should have a constructor, ArrayDeque(int maxSize), which creates an array with capacity cap, and your LinkedListDeque class should have a constructor, LinkedListDeque(), which initializes the linked list. The classes ArrayDeque and LinkedListDeque should then implement each of the methods defined in the Deque interface.

You'll need something to do in the case that a dequeue method is invoked when the deque is empty, or, in the case of the array implementation, when an insert method is invoked and the deque is full. Put (or download) the following exceptions in files EmptyStructureException.java and FullStructureException.java, respectively. Then you can throw new EmptyStructureException(), for example. See the textbook for more information about exceptions.

public class EmptyStructureException extends RuntimeException {
   public EmptyStructureException() { super(); }
   public EmptyStructureException(String s) { super(s); }
}

public class FullStructureException extends RuntimeException {
   public FullStructureException() { super(); }
   public FullStructureException(String s) { super(s); }
}

Now we can write simple adapter classes for our generic Deque interface to provide the stack and queue ADTs. The code for DequeStack already is filled in.

public class DequeStack implements Stack {
   Deque deque;
   DequeStack(Deque o) { deque = o; }
   public int size() { return deque.size(); }
   public boolean isEmpty() { return deque.isEmpty(); }
   public Object top() { return deque.lastElement(); }
   public Object pop() { return deque.removeLast(); }
   public void push(Object o) { deque.insertLast(o); }
}

public class DequeQueue implements Queue {
   ...
   public int size() { ... }
   public boolean isEmpty() { ... }
   public Object front() { ... }
   public void enqueue(Object o) { ... }
   public Object dequeue() { ... }
}

Thus we can instantiate an array-based stack of at most twelve elements with the code fragment

   DequeStack stack = new DequeStack(new ArrayDeque(12));

This demonstrates a powerful technique of code reuse, and you will have created 9 classes (plus perhaps a 10th testing class).

Be sure to test your new classes well.