Implement the following data structures as described in the textbook:

• Stack interface, Code Fragment 6.1
• ArrayStack, Code Fragment 6.2
• LinkedStack, Code Fragment 6.4
• Queue interface, Code Fragment 6.9
• ArrayQueue, Code Fragment 6.10
• LinkedQueue, Code Fragment 6.11
• List interface, Code Fragment 7.1
• ArrayList, Code Fragments 7.2, 7.3, 7.4, 7.5

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

• For the ArrayStack, LinkedStack, ArrayQueue, LinkedQueue, and ArrayList:
  • Perform a timing test for each of these data structures.
  • Each timing test should measure in nanoseconds how long it takes to add and remove N Integers from the structure.
  • N should vary from 10 to 1,000,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, and your program crashes just decrease the maximum value of N by a factor of 10 and try a new run.
    • You should see that your program throws an OutOfMemoryError
    • Generally, you should not try to catch an OutOfMemoryError because your memory space might be corrupted and there is no guarantee that you can recover from the error.
  • Test results must be displayed in a nicely formatted ASCII table similar to the examples provided.
  • 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 dynamically adjust the width of each column based on the values that it needs to print.
    • Numeric values must be printed using the comma thousand separator, i.e.
      • you must print a large number like 12,345
      • and not 12345
    • It is strongly suggested that you create a method that generates and prints 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.
  • You should have two final runs in your Word document.
  • For the first run, set the max value of N to 1,000,000 so that the times are fairly small.
  • For the second run, set the max value of N to 1,000,000,000
  • If you run out of memory reduce the max value of N by a factor of 10 and try a new run.
  • For this assignment your ASCII tables do NOT need to have column labels.

ArrayList

public class ArrayList implements List { // instance variables public static final int CAPACITY=16; // default array capacity private E[ ] data; // generic array used for storage private int size = 0; // current number of elements // constructors public ArrayList( ) { this(CAPACITY); } // constructs list with default capacity public ArrayList(int capacity) { // constructs list with given capacity data = (E[ ]) new Object[capacity]; // safe cast; compiler may give warning } // public methods /** Returns the number of elements in the array list. */ public int size( ) { return size; } /** Returns whether the array list is empty. */ public boolean isEmpty( ) { return size == 0; } /** Returns (but does not remove) the element at index i. */ public E get(int i) throws IndexOutOfBoundsException { checkIndex(i, size); return data[i]; } /** Replaces the element at index i with e, and returns the replaced element. */ public E set(int i, E e) throws IndexOutOfBoundsException { checkIndex(i, size); E temp = data[i]; data[i] = e; return temp; } /** Inserts element e to be at index i, shifting all subsequent elements later. */ public void add(int i, E e) throws IndexOutOfBoundsException, IllegalStateException { checkIndex(i, size + 1); if (size == data.length) // not enough capacity throw new IllegalStateException("Array is full"); for (int k=size-1; k>= i; k--) // start by shifting rightmost data[k+1] = data[k]; data[i] = e; // ready to place the new element size++; } /** Removes/returns the element at index i, shifting subsequent elements earlier. */ public E remove(int i) throws IndexOutOfBoundsException { checkIndex(i, size); E temp = data[i]; for (int k=i; k< size-1; k++) // shift elements to fill hole data[k] = data[k+1]; data[size-1] = null; // help garbage collection size--; return temp; } // utility method /** Checks whether the given index is in the range [0, n1]. */ protected void checkIndex(int i, int n) throws IndexOutOfBoundsException { if (i < 0 || i >= n) throw new IndexOutOfBoundsException("Illegal index: " + i); }

/** Resizes internal array to have given capacity >= size. */ protected void resize(int capacity) { E[ ] temp = (E[ ]) new Object[capacity]; // safe cast; compiler may give warning for (int k=0; k < size; k++) temp[k] = data[k]; data = temp; // start using the new array } /** Inserts element e to be at index i, shifting all subsequent elements later. */

}

ArrayQueue

Arpublic class ArrayQueue implements Queue { // instance variables private E[ ] data; // generic array used for storage private int f = 0; // index of the front element private int sz = 0; private static int CAPACITY = 1000; 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. */ public int size( ) { return sz; }

/** Tests whether the queue is empty. */ public boolean isEmpty( ) { return (sz == 0); }

/** Inserts an element at the rear of the queue. */ 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). */ public E first( ) { if (isEmpty( )) return null; return data[f]; }

/** Removes and returns the first element of the queue (null if empty). */ 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; } }

ArrayStack

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) { // constructs stack with given capacity data = (E[ ]) new Object[capacity]; // safe cast; compiler may give warning } public int size( ) { return (t + 1); } public boolean isEmpty() {return (t == -1); } public void push(E e) throws IllegalStateException { if (size( ) == data.length) throw new IllegalStateException("Stack is full"); data[++t] = e; // increment t before storing new item } public E top( ) { if (isEmpty( )) return null; return data[t]; } public E pop( ) { if (isEmpty( )) return null; E answer = data[t]; data [t] = null; // dereference to help garbage collection t--; return answer; } }

LinkedQueue

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

LinkedStack

public class LinkedStack implements Stack { private SinglyLinkedList list = new SinglyLinkedList<>( ); // an empty list public LinkedStack( ) { } // new stack relies on the initially empty list public int size( ) { return list.size( ); } public boolean isEmpty( ) { return list.isEmpty( ); } public void push(E element) { list.addFirst(element); } public E top( ) { return list.first( ); } public E pop( ) { return list.removeFirst( ); } }

List

/** A simplified version of the java.util.List interface. */ public interface List { /** Returns the number of elements in this list. */ int size( );

/** Returns whether the list is empty. */ boolean isEmpty( );

/** Returns (but does not remove) the element at index i. */ E get(int i) throws IndexOutOfBoundsException; E set(int i, E e) throws IndexOutOfBoundsException; void add(int i, E e) throws IndexOutOfBoundsException; E remove(int i) throws IndexOutOfBoundsException; }

Queue

public interface Queue { int size( ); boolean isEmpty( ); void enqueue(E e); E first( ); E dequeue( ); }

SinglyLinkedList

public class SinglyLinkedList { private static class Node { private E element; private Node next; public Node(E e, Node n) { element = e; next = n; } public E getElement( ) { return element; } public Node getNext( ) { return next; } public void setNext(Node n) { next = n; } } private Node head = null; // head node of the list (or null if empty) private Node tail = null; // last node of the list (or null if empty) private int size = 0; // number of nodes in the list public SinglyLinkedList( ) { } // constructs an initially empty list // access methods public int size( ) { return size; } public boolean isEmpty( ) { return size == 0; } public E first( ) { // returns (but does not remove) the first element if (isEmpty( )) return null; return head.getElement( ); } public E last( ) { // returns (but does not remove) the last element if (isEmpty( )) return null; return tail.getElement( ); } // update methods public void addFirst(E e) { // adds element e to the front of the list head = new Node<>(e, head); // create and link a new node if (size == 0) tail = head; // special case: new node becomes tail also size++; } public void addLast(E e) { // adds element e to the end of the list Node newest = new Node<>(e, null); // node will eventually be the tail if (isEmpty( )) head = newest; // special case: previously empty list else tail.setNext(newest); // new node after existing tail tail = newest; // new node becomes the tail size++; } public E removeFirst( ) { // removes and returns the first element if (isEmpty( )) return null; // nothing to remove E answer = head.getElement( ); head = head.getNext( ); // will become null if list had only one node size--; if (size == 0) tail = null; // special case as list is now empty return answer; } }

Stack

public interface Stack { /** * Returns the number of elements in the stack. * @return number of elements in the stack */ int size( );

/** * Tests whether the stack is empty. * @return true if the stack is empty, false otherwise */ boolean isEmpty( );

/** * Inserts an element at the top of the stack. * @param e the element to be inserted */ void push(E e);

/** * Returns, but does not remove, the element at the top of the stack. * @return top element in the stack (or null if empty) */ E top( );

/** * Removes and returns the top element from the stack. * @return element removed (or null if empty) */ E pop( ); }