Write a Client class with a main method that tests the data structures as follows:

• For the ArrayStack, LinkedStack, ArrayQueue and LinkedQueue:
  • Perform a timing test for each of these data structures.
  • Each timing test should measure in nanoseconds how long it takes to add N Integers to the structure and how long it takes to remove N Integers from the structure.
  • N should vary from 10 to 100,000,000 increasing N by a factor of 10 for each test.
  • Depending on your system you may run out of memory before you reach the maximum value of N. If you run out of memory, your program should gracefully stop the test and move on to the next test.
  • Test results must be displayed in a nicely formatted ASCII table similar to the examples provided at the end of the assignment.
  • In the ASCII table:
    • Values in each cell are padded by 2 blank spaces
    • Each column is just wide enough to display the widest entry in that column including the cell padding. Your program must automatically adjust the width of each column based on the values that it needs to print.
    • It is strongly suggested that you create a method that generates the ASCII table. You could pass this method a 2 dimensional array of values that are to be printed.
    • Future assignments may require that you print out results in a similar ASCII table.

public class ArrayStack implements Stack { public static final int CAPACITY = 1000; //default array capacity private E[] data; //generic array used for storage private int t = -1; //index of the top element in stack public ArrayStack() { this(CAPACITY); } //constructs stack with default capacity public ArrayStack(int capacity) { //contsructs stack with given capacity data = (E[]) new Object[capacity]; //safe cast; compiler may give warning } @Override public int size() {return(t + 1);} @Override public boolean isEmpty() { return(t == -1); } @Override public void push(E e) throws IllegalStateException { if(size() == data.length) throw new IllegalStateException("Stack is full"); data[++t] = e; //increments t before storing new item } public E top() { if(isEmpty()) return null; return data[t]; } @Override public E pop() { if(isEmpty()) return null; E answer = data[t]; data[t] = null; //dereference to help garbage collection t--; return answer; } } public class LinkedStack implements Stack { private SinglyLinkedList list = new SinglyLinkedList<>(); // an empty list public LinkedStack() {} // new stack relies on the initially empty list @Override public int size() { return list.size(); } @Override public boolean isEmpty() { return list.isEmpty(); } @Override public void push(E element) { list.addFirst(element); } public E top() { return list.first(); } @Override public E pop() { return list.removeFirst(); } }

public class ArrayQueue implements Queue { // instance variables public static final int CAPACITY = 1000; //default array capacity private E[] data; // generic array used for storage private int f = 0; // index of the front element private int sz = 0; // current number of elements

// constructors public ArrayQueue() {this(CAPACITY);} // constructs queue with default capacity public ArrayQueue(int capacity) { // constructs queue with given capacity data = (E[ ]) new Object[capacity]; // safe cast; compiler may give warning }

// methods /** Returns the number of elements in the queue. */ @Override public int size() { return sz; }

/** Tests whether the queue is empty. */ @Override public boolean isEmpty() { return (sz == 0);} /** Inserts an element at the rear of the queue. */ @Override public void enqueue(E e) throws IllegalStateException { if (sz == data.length) throw new IllegalStateException("Queue is full"); int avail = (f + sz) % data.length; // use modular arithmetic data[avail] = e; sz++; }

/** Returns, but does not remove, the first element of the queue (null if empty). */ @Override public E first() { if (isEmpty()) return null; return data[f]; } /** Removes and returns the first element of the queue (null if empty). */ @Override public E dequeue() { if (isEmpty()) return null; E answer = data[f]; data[f] = null; // dereference to help garbage collection f = (f + 1) % data.length; sz--; return answer; } }

public class LinkedQueue implements Queue { private SinglyLinkedList list = new SinglyLinkedList<>(); // an empty list public LinkedQueue() {} // new queue relies on the initially empty list @Override public int size() { return list.size(); } @Override public boolean isEmpty() { return list.isEmpty(); } @Override public void enqueue(E element) { list.addLast(element); } @Override public E first() { return list.first(); } @Override public E dequeue() { return list.removeFirst(); } }