Java Homework Help: Data Structures and Algorithms 6th edition.

I have the following code segments:

Stack Interface: 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 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 doesn't 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(); }

Queue Interface:

/** * * @author Robert */ public interface Queue { /** Returns the number of elements in the queue.*/ int size(); /** Tests whether the queue is empty.*/ boolean isEmpty(); /** Inserts an element at the rear of the queue.*/ void enqueue(E e); /** Returns, but doesn't remove, the first element of the queue (null if empty).*/ E first(); /** Removes and returns the first element of the queue (null if empty).*/ E dequeue(); }

ArrayStack Class

/** * * @author Robert */ 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; 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; complier 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; //deference to help garbage collection t--; return answer; } }

LinkedStack Class

/** * * @author Robert */ public class LinkedStack implements Stack { private SinglyLinkedList list = new SinglyLinkedList<>(); //an empty list public LinkedStack() {} //new stack relies on intially 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(); } }

ArrayQueue

/** * * @author Robert */

/** Implementation of the queue ADT using a fixed-length array.*/ public class ArrayQueue implements Queue { //instance variables private static final int CAPACITY = 1000; 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.*/ 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; //modular arithmetic data[avail] = e; sz++; } /** Returns, but doesn't 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; f = (f + 1) % data.length; sz--; return answer; }

}

LinkedQueue Class

/** * * @author Robert */ public class LinkedQueue implements Queue { private SinglyLinkedList list = new SinglyLinkedList<>(); //empty list private static final int CAPACITY = 1000; 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 public LinkedQueue() {} public LinkedQueue(int capacity) { //constructs queue with given capacity data = (E[]) new Object[capacity];//safe cast; compiler may give warning } 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(); }

}

SinglyLinkedList Class

/** * * @author robert.ryden */ public class SinglyLinkedList { // instance variables of the SinglyLinkedList 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; }

public void clear() { size = 0; head = null; tail = null; }

public boolean contains(E element) { Node temp = head; while (temp != null) { if (temp.element.equals(element)) { return true; } } return false; }

public int frequency(E elem) { int count = 0; Node temp = head; while (temp != null) { if (temp.element.equals(elem)) { count++; } } return count; }

public static class Node {

private E element; // reference to the element stored at this node private Node next; // reference to the subsequent node in the list

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; } } }

Write a Client class with a main method that tests the data structures as follows (you may break these test up into separate methods if you wish):

For the ArrayStack and LinkedStack

Use Code Fragment 6.3 as a guide to test the stacks.

be sure to test the ArrayStack to see what happens when you push onto a full stack

pop all of the items off the stack

be sure to test to see what happens when you pop from an empty stack

make sure that the popped items come off the stack in the correct (LIFO) order.

For the ArrayQueue and LinkedQueue

Use example 6.4 to as a guide to test the queues.

Be sure to test the ArrayQueue to see what happens when you enqueue into a full queue

Dequeue all of the items from the queue

Be sure to test to see what happens when you dequeue from an empty queue

make sure that the dequeued items come out of the queue in correct (FIFO) order.

For the ArrayList

Run a timing test to see how long it takes to add items to the ArrayList just before, at, and just after the ArrayList has to double it data array size (see example below).

Start you test at n slightly less than 2^27 (i.e. 134,217,728) and then for each additional test double the starting value for n.

Keep increasing the starting value of n until you run out of memory.

Write your test so your program does not crash when it runs out of memory.

Use the nanosecond timer instead of the millisecond timer.

Use an ArrayList of Booleans to minimize memory requirements.

Example of ArrayList Timing test:

run:

===== Test adding 134,217,728 items to ArrayList ======

Size = 134,217,726 Time = 7,128 nsec

Size = 134,217,727 Time = 1,140 nsec

Size = 134,217,728 Time = 855 nsec

Size = 134,217,729 Time = 443,055,016 nsec

Size = 134,217,730 Time = 1,996 nsec

Size = 134,217,731 Time = 570 nsec

Size = 134,217,732 Time = 855 nsec

===== Test adding 268,435,456 items to ArrayList ======

Size = 268,435,454 Time = 570 nsec

Size = 268,435,455 Time = 285 nsec

Size = 268,435,456 Time = 0 nsec

Size = 268,435,457 Time = 23,605,535,482 nsec

Size = 268,435,458 Time = 1,996 nsec

Size = 268,435,459 Time = 570 nsec

Size = 268,435,460 Time = 1,141 nsec

===== Test adding 536,870,912 items to ArrayList ======

Size = 536,870,910 Time = 285 nsec

Size = 536,870,911 Time = 285 nsec

Size = 536,870,912 Time = 285 nsec

Out of memory at n = 536,870,912

BUILD SUCCESSFUL (total time: 1 minute 30 seconds