Homework 4

CMP 338: Data Structures & Algorithms
Lehman College, City University of New York
Fall 2015

This Homework Is Due By 11:55 PM on November 4, 2015

1. Implementation:
   
   In lecture, we discussed two implementations of a queue. An array based queue implementation, and a reference based queue implemetation. For this assignment, you are going to implement the following Queue Interface for both an array based queue and a reference based queue. The interface is specified in QueueInterface.java.
   
   
   1. Array Based Queue Class:
      
      Write a Java program that implements the QueueInterface as an array based queue Your implementation must be in a class named ArrayQueue. You can assume that the list will not contain more than 100,000 elements.
   
   
   2. Reference Based Queue Class:
      
      Write a Java program that implements the QueueInterface as a reference based queue Your implementation must be in a class named LinkedQueue.
   
   
   3. Iterable Interface:
      
      Please note that the Queue Interface extends the Iterable Interface. So, both ArrayQueue and LinkedQueue must implement this interface.
   
   
   4. Iterator Class:
      
      The Iterable Interface has one method Iterator<T> iterator() which returns an object that implements the Iterator Interface. Write a Java program that implements the Iterator Interface. Your implementation must be in a class named QueueIterator.



2. Test Cases:
   
   You must also write a driver program that demonstrates that both queue types work. Your driver should use the following test cases for each queue type:
   
   
   1. Create an instance of your Queue that accepts java.lang.Integer Objects. Starting with an empty queue, use the add(E e) method to add java.lang.Integer objects representing the numbers (1 ≤ n ≤ 100,000) to the Queue.
   2. Starting with a instance of your Queue that accepts java.lang.Integer Objects that is fully populated with java.lang.Integer objects representing the numbers (1 ≤ n ≤ 100,000) in the Queue. De-queue all objects using the remove() method. Make sure to verify that the java.lang.Integer objects are in the expected FIFO order.
   3. Create an instance of your Queue that accepts java.lang.String Objects. Starting with an empty queue, use the add(E e) method to add java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 5,000") to the Queue. Use the Iterator() method to obtain a java.util.Iterator object. Use the java.util.Iterator object to display the strings in the queue.
   4. Starting with a instance of your Queue that accepts java.lang.String Objects that is fully populated with java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 5,000") in the Queue. Use the Iterator() method to obtain a java.util.Iterator object. Use the java.util.Iterator object to display and remove the strings from the queue.
   
   
   
   
3. Driver Class:
   
   Your driver must be in a class named Driver. Your Driver class must implement the following:
   
   
   1. QueueType enum
   2. TestType enum
   3. All the methods specified in the Driver documentation



4. Reference Based Queue Node Class:
   
   Your linked list node class must be named Node. and it must implement all the methods specified in the Node documentation.



5. Statistics Class:
   
   In addition to printing the run times for each test case, you will have to also display the average time and the standard deviation. You will have a class named Statistics. and it must implement all the methods specified in the Statistics documentation.

Please make sure that all your Java programs are in the default package.

Please compress the Java programs as a zip file containing:

1. QueueInterface.java
2. LinkedQueue.java
3. ArrayQueue.java
4. QueueIterator.java
5. Node.java
6. Driver.java
7. Statistics.java

Please submit your zip file at the Mimir Platform Website .