CSci2110 - Problem Set 2

Due: Thursday Feb. 6th by 11:59pm

Question 1: 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. Reading the textbook carefully will help you greatly. The textbook describes a doubly-ended queue, which is often called a deque. The interface for a deque is the following (which is slightly different than the one given in the book): 
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;
}

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. 

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

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

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 a number of classes that you can reuse in future programs.

Be sure to test your new classes well.

Question 2a: Write a Java program that has a Polygon interface, which has abstract methods, area( ), and perimeter( ). Implement classes for Triangle, and Quadrilateral, which implement this interface, with the obvious meanings for the area( ) and perimeter( ) methods. Also implement classes IsoscelesTriangle, Rectangle, and Square, which have the appropriate inheritance relationships, and implement the polygon interface. All of your shape classes should inheret from a simple2DPollygon class. Finally, write a tester class, which creates simple2DPolygon of the various types, and then output their area and perimeter. Try to design the constructors so all valid instances of these polygons (in the positive Eurclidean quadrant) can be created and no invalid one's can be.

BONUS Questions

Implement one or more of the following methods for your shape classes:

Note: No late assignments will be accepted. Discuss ideas with your friends, but write and hand in your own code. Plagiarism will be dealt with severely.