cover picture cover picture


Homework 5

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


This Homework Is Due By 11:59 PM on Friday May 13, 2022

Please note that this assignment will count as extra credit.

Overview

In this assignment you will be implementing the Abstract Data Type (ADT) Stack ADT using two different implementations:

  1. Array Based Stack
  2. Linked Stack

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

You will also be using the TestTimes class with the added functionality that you worked on for Homework 4.

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

Details

  1. TestTimes zyLab

    You will copy the TestTimes class that you enhanced with added functionality in Homework 4 to the project you are using for this assignment. This TestTimes class implements the expanded TestTimes Interface . Please note that you will also have to re-submit TestTimes.java to zyBooks in the TestTimes zyLab.

  2. ArrayBasedStack zyLab

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

    Please note that Stack Interface extends the Iterable Interface , which requires you to implement one method Iterator iterator() .

  3. LinkedStack zyLab

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

    Please note that Stack Interface extends the Iterable Interface , which requires you to implement one method Iterator iterator() .

  4. ElementIterator zyLab

    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()

  5. Node zyLab

    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 Stack.

  6. StackDriver zyLab

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

    Please note that, in addition to implementing the QueueDriverInterface, you are also required to write your own public static main(String[] args) method in QueueDriver.java that performs all of the required tests as specified below.

Required Tests

Definitions:

You will test two queue implementations with different tests. You will run all tests on both implementations of the StackInterface. The StackDriverInterface includes the definitions of two enums:

  1. StackDriverInterface.StackType
    This enum defines all the possible queue types that you will implement. They are:
    ArrayBasedStack
    The array based implementation of the StackInterface.
    LinkedStack
    The linked implementation of the StackInterface.
  2. StackDriverInterface.TestType

    All the elements being added and removed from the stacks must be instances of the String class.

    This enum defines all the tests that you will be performing. The tests are:

    StackDriverInterface.TestType.Push:
    1. Initialization: Create an empty stack.
    2. Test: Use the push(E e) method to add 10,000 String objects representing the strings ("String 1" ≤ s ≤ "String 10000") to the Stack.
    StackDriverInterface.TestType.Pop:
    1. Initialization: Create a stack and populate it with String objects representing ("String 1" ≤ s ≤ "String 10000").
    2. Test: Use the pop() method to pop all the String objects from the stack, one at a time.
Output From Driver Main Method

Please note that, in addition to implementing the StackDriverInterface, you are also required to write your own public static main(String[] args) method in StackDriver.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 runTestCase() method your main() method will print out a table with the following output for the Array Based Stack and the Linked Stack implementations: 

Test Type = testType
                   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

Test Type = testType
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10    Average
                   Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo      Kilo 
                   Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes     Bytes 
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- --------- ----------
ArrayBasedStack
LinkedStack

Please note that the test times and the average are in Micro Seconds and the memory usage is in Kilo Bytes. You will need to make the necessary conversions.

Sample Output
Test Type = Push
                   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   4675.897   3724.800   2947.470   2478.010    3019.076   2629.850   2430.910   1775.309   1301.808  1397.940   2638.107
LinkedStack      10904.048   2136.249   1681.046   1860.266    1910.874   2197.965   1446.349   1420.298   1298.713   954.241   2581.005

Test Type = Push
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10     Average
                   Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo 
                   Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes 
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- ---------  ----------
ArrayBasedStack   3932.219   6592.734   7903.500  10525.008   11835.836  13146.617  15807.211  17117.969  19739.484 21050.242   12765.082
LinkedStack      23671.680  24982.438  27603.953  30225.469   31536.227  34157.742  36779.258  38090.016  39400.773 40711.516   32715.907



Test Type = Pop
                   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    761.486    302.933    253.340    215.243     188.841    481.732    121.800    169.368    164.675    83.622    274.304
LinkedStack        826.739    354.022    147.382    243.760     122.964     90.030    122.787    122.405    134.848   190.360    235.530


Test Type = Pop
                   Run 1      Run 2      Run 3      Run 4      Run 5      Run 6      Run 7      Run 8      Run 9      Run 10     Average
                   Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo       Kilo 
                   Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes      Bytes 
                ---------- ---------- ---------- ---------- ----------- ---------- ---------- ---------- ---------- ---------  ----------
ArrayBasedStack  43333.039  44643.820  47265.383  48576.164   49926.023  52625.742  53936.500  53936.500  55247.242 56558.000   50604.841
LinkedStack      57868.742  60490.258  63111.758  64422.539   65536.000   6569.500   7866.945   9164.391  10461.836 11759.281   35725.125

Please submit the completed assignment in your zyBooks , in the Homework 5 Chapter.