cover picture cover picture


Homework 4

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


This Homework Is Due By 11:59 PM on Sunday April 4, 2021

Overview

In this assignment you will be implementing two Abstract Data Types (ADT) the Queue ADT and the Stack ADT. In addition, you will be using two different implementations for each ADT:

  1. Array Based
  2. Linked

You will also be writing a driver to test your Queue and Stack implementations and you will be measuring the test times and memory use of each test case.

You will also be adding some functionality to the TestTimes class that you created for Homework 1.

Finally, you will be analysing and comparing the performance of the test cases on both the Array Based and the Linked implementations of both the Queue ADT and the Stack ADT.

Details

  1. TestTimes Class

    You will be expanding the functionality of the TestTimes class to implement the expanded TestTimes Interface, The interface may be downloaded from TestTimesInterface.java

  2. Array Based Queue Class

    You will write the ArrayBasedQueue.java class which will implement the Queue Interface. The interface may be downloaded from QueueInterface.java.

    Please note that Queue Interface extends the Iterable Interface. See the Information On The Iterable Interface below.

  3. Linked Queue Class

    You will write the LinkedQueue.java class which will implement the Queue Interface. The interface may be downloaded from QueueInterface.java.

    Please note that Queue Interface extends the Iterable Interface. See the Information On The Iterable Interface below.

    Also note that the Linked Queue Class should be a Doubly Linked Queue.

  4. Array Based Stack Class

    You will write the ArrayBasedStack.java class which will implement the Stack Interface. The interface may be downloaded from StackInterface.java.

    Please note that Stack Interface extends the Iterable Interface. See the Information On The Iterable Interface below.

  5. Linked Stack Class

    You will write the LinkedStack.java class which will implement the Stack Interface. The interface may be downloaded from StackInterface.java.

    Please note that Stack Interface extends the Iterable Interface. See the Information On The Iterable Interface below.

    Also note that the Linked Stack Class should be a Doubly Linked Stack.

  6. Information On The Iterable Interface

    The Iterable Interface requires you to implement one method Iterator iterator(). So, all your Queue and Stack classes must implement this interface.

  7. Element Iterator Class

    You will write the ElementIterator.java class which will implement the Iterator Interface.

    Please note, you only need to implement two methods from the Iterator interface: boolean hasNext() and E next()

  8. Node Class

    You will write the Node.java Please see the Node Class Documentation for all the methods you will need.

    Please note that the Node Class is a node for a Doubly Linked Queue or Doubly Linked Stack.

  9. Driver Class

    You will write the Driver.java class which will implement the Driver Interface. The interface may be downloaded from DriverInterface.java.

    Please note that you do not inherit from the TestTimes class. However, you do have to use the TestTimes class to measure test times and memory usages.

  10. Queue Test Cases

    All the elements being enqueued and dequeued from your queues must be instances of the java.lang.String class.

    1. Create an instance of your queue that accepts java.lang.String Objects. Starting with an empty queue, use the enqueue(E e) method to add 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") to the Queue.
    2. Starting with an instance of your queue that accepts java.lang.String Objects that is fully populated with 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") in the Queue. Use the dequeue() method to remove all the objects from the queue, one at a time.
    3. Starting with an instance of your queue that accepts java.lang.String Objects that is fully populated with 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") in the Queue. Use the Iterator() method to obtain an ElementIterator object. Use the ElementIterator object to display the strings from the queue one String per line.
  11. Stack Test Cases

    All the elements being pushed and popped from your stacks must be instances of the java.lang.String class.

    1. Create an instance of your stack that accepts java.lang.String Objects. Starting with an empty stack, use the push(E e) method to add 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") to the stack.
    2. Starting with an instance of your stack that accepts java.lang.String Objects that is fully populated with 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") in the stack. Use the pop() method to remove all the objects from the stack, one at a time.
    3. Starting with an instance of your stack that accepts java.lang.String Objects that is fully populated with 10,000 java.lang.String objects representing the strings ("String 1" ≤ s ≤ "String 10000") in the stack. Use the Iterator() method to obtain an ElementIterator object. Use the ElementIterator object to display the strings from the stack, one String per line.
  12. Output From Driver Main Method

    Please note that, in addition to implementing the DriverInterface, you are also required to write your own public static main(String[] args) method in Driver.java.

    Your main() method will have to call the runTestCase() method for each of test cases listed above a total of ten times for each test case:

    For each call to the runQueueTestCase() method your main() method will a table with the following output for the Array Based Queue and the Linked Queue implementations: 

    Running test = Test Case Name
		  Run 1   Run 2   Run 3   Run 4   Run 5   Run 6   Run 7   Run 8   Run 9  Run 10 Average
                 Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro
		Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
		------- -------	------- -------	------- -------	------- -------	------- -------	-------
ArrayBasedQueue
LinkedQueue
	
    Running test = Test Case Name
		  Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9     Run 10     Average
		Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes
		---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
ArrayBasedQueue
LinkedQueue

    For each call to the runStackTestCase() method your main() method will a table with the following output for the Array Based Stack and the Linked Stack implementations: 

    Running test = Test Case Name
		  Run 1   Run 2   Run 3   Run 4   Run 5   Run 6   Run 7   Run 8   Run 9  Run 10 Average
                 Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro   Micro
		Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds Seconds
		------- -------	------- -------	------- -------	------- -------	------- -------	-------
ArrayBasedStack
LinkedStack
	
    Running test = Test Case Name
		  Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9     Run 10     Average
		Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes Kilo Bytes
		---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----------
ArrayBasedStack
LinkedStack

    Please note that the test times and the average are in Micro Seconds and the memory usage is in Kilo Bytes.

  13. Analysis:

    Using the tables you created by running Driver.main(), copy your results and graphs into a Microsoft Word document and answer the following questions using 1-3 complete sentences for each question:

    1. Create graphs from the test times you measured.
    2. Discuss the difference in test times and memory usage between the array based queue and the linked queue for all the test cases. Did the results match your expectations? Why or why not? Be as specific as possible.
    3. Are the test times ever similar for both the array based queue and the linked queue? Why or why not? Be as specific as possible.
    4. In which test cases is the array based queue faster than the linked queue? Please explain the reason. Be as specific as possible.
    5. Discuss the difference in test times and memory usage between the array based stack and the linked stack for all the test cases. Did the results match your expectations? Why or why not? Be as specific as possible.
    6. Are the test times ever similar for both the array based stack and the linked stack? Why or why not? Be as specific as possible.
    7. In which test cases is the array based stack faster than the linked stack? Please explain the reason. Be as specific as possible.

Please submit the completed assignment on the Mimir Platform Website .

You must submit your .java files as a zip file of only the classes and interfaces specified above.

Please submit your analysis on Blackboard as a typed Microsoft Word file (.docx). No other forms of submission will be accepted.