cover picture cover picture


Homework 4

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


This Homework Is Due By 11:59 PM on March 18, 2015

  1. Implementation: (25 Points)

    In lecture, we discussed two implementations of a queue. An array based queue implementation, and a reference based queue implemetation. Write Java programs that implement both the array based and the reference based queues. Both classes must implement the Queue Interface specified in QueueInterface.java, and the Iterable Interface.

    You will also need to write a Java program that implements the Iterator Interface.

    Please note that all the classes you will implement must be generic.

  2. Test Cases: (10 Points)

    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. 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 100") in 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 100") 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.

    Run each test 10 times and make a table with the running time for each run, as well as the average and the standard deviation for each test case.

  3. Analysis: (15 Points)

    Using the tables you created, answer the following questions using complete sentences:

    1. Discuss your run time measurements by comparing the results of the array based and the reference based implementations. Why are they similar or different?
    2. What will be the result of iterator.getNext() or iterator.remove() if your underlying queue is being modified while the iterator is in use?

Please submit the completed assignment on Blackboard. You must submit your Java programs as a zip file of your Eclipse project. The analysis must be a typed Microsoft Word file. No other forms of submission will be accepted.