Java Foundations

StackADT.java

/** * Defines the interface to a stack collection. * * @author Java Foundations * @version 4.0 */ public interface StackADT { /** * Adds the specified element to the top of this stack. * * @param element element to be pushed onto the stack */ public void push(T element);

/** * Removes and returns the top element from this stack. * * @return the element removed from the stack * @throws EmptyCollectionException if the stack is empty */ public T pop();

/** * Returns the top element of this stack without removing it from the stack. * * @return the element on top of the stack. It is not removed from the stack * @throws EmptyCollectionException if the stack is empty */ public T peek();

/** * Returns true if this stack contains no elements. * * @return true if the stack is empty, false if the stack is not empty */ public boolean isEmpty();

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

} QueueADT.java

/** * QueueADT defines the interface to a queue collection. * * @author Java Foundation * @version 4.0 */ public interface QueueADT { /** * Adds one element to the rear of this queue. * * @param element the element to be added to the rear of the queue */ public void enqueue(T element);

/** * Removes and returns the element at the front of this queue. * * @return the element at the front of the queue * @throws EmptyCollectionException if the queue is empty */ public T dequeue();

/** * Returns without removing the element at the front of this queue. * * @return the first element in the queue * @throws EmptyCollectionException if the queue is empty */ public T first();

/** * Returns true if this queue contains no elements. * * @return true if the queue is empty, false if the queue is not empty */ public boolean isEmpty();

/** * Returns the number of elements in this queue. * * @return the number of elements in the queue */ public int size();

} LinkedDeque.java

public class LinkedDeque implements QueueADT, StackADT, DequeADT {

// inner class for a double linked list node private class DNode { private T element; private DNode prev, next; } // data fields for the LinkedDeque class private DNode front, rear; private int size; // deque interface methods @Override public void addFirst(T element) { // create a new node and set it up DNode newNode = new DNode(); newNode.element = element; // from param to new node obj newNode.prev = newNode.next = null; if(this.isEmpty()) { // we are making the only node in the deque this.rear = this.front = newNode; } else { // there already exists a new node // so, put the new node before the front node newNode.next = this.front; this.front.prev = newNode; this.front = newNode; } this.size++; }

@Override public T removeFirst() { T grabbedElt = this.getFirst(); // checks for empty for us

if(this.size() == 1) { // we are removing the only node // so the deque is becoming empty } else { // there are multiple nodes in the queue // so the rear won't change and we just mess with front end } this.size--; return grabbedElt; }

@Override public T getFirst() { if(this.isEmpty()) { throw new EmptyCollectionException("LinkedDeque"); } return this.front.element; }

@Override public void addLast(T element) { }

@Override public T removeLast() { return null; }

@Override public T getLast() { if(this.isEmpty()) { throw new EmptyCollectionException("LinkedDeque"); } return this.rear.element; }

// stack interface methods @Override public void push(T element) { this.addFirst(element); }

@Override public T pop() { return this.removeFirst(); }

@Override public T peek() { return this.getFirst(); }

// queue interface methods @Override public void enqueue(T element) { // TODO Auto-generated method stub }

@Override public T dequeue() { // TODO Auto-generated method stub return null; }

@Override public T first() { // TODO Auto-generated method stub return null; }

@Override public boolean isEmpty() { return (this.size == 0); }

@Override public int size() { return this.size; }

@Override public String toString() { String s = "LinkedDeque of size" + this.size() + "containing (front to back)"; for (DNode curr = this.front; curr != null; curr = curr.next) { s = s + curr.element; if(curr.next != null) { s = s + ", "; } else { s = s + "."; } } } }

EmptyCollectionException.java

/** * Represents the situation in which a collection is empty. * * @author Java Foundations * @version 4.0 */ public class EmptyCollectionException extends RuntimeException { /** * Sets up this exception with an appropriate message. * @param collection the name of the collection */ public EmptyCollectionException(String collection) { super("The " + collection + " is empty."); } } DequeADT.java

public interface DequeADT { /** * The DequeADT (double-ended queue) provides methods for inserting, deleting * and getting either the first or last element of a sequence of elements. */

/** * Adds a new element to the head of this deque. * * @param element the element to insert at the head of this deque */ public void addFirst(T element);

/** * Removes and returns the head element of this deque. * * @return the head element of this deque * @throws EmptyCollectionException if the deque is empty */ public T removeFirst();

/** * @return the head element of this deque * @throws EmptyCollectionException if the deque is empty */ public T getFirst();

/** * Adds a new element to the tail of this deque. * * @param element the element to insert at the tail of this deque */ public void addLast(T element);

/** * Removes and returns the tail element of this deque. * * @return the tail element of this deque * @throws EmptyCollectionException if the deque is empty */ public T removeLast();

/** * @return the tail element of this deque * @throws EmptyCollectionException if the deque is empty */ public T getLast(); /** * Returns true if this deque contains no elements. * * @return true if the deque is empty, false if the deque is not empty */ public boolean isEmpty();

/** * Returns the number of elements in this deque. * * @return the number of elements in the deque */ public int size();

}

have a toString() method that prints the contents of the data structure on one line. Implementing multiple interfaces enqueue method should invoke addLast and dequeue should removeFirst). Make sure to implement every method of all three interfaces. The Main Class You need to have a Main class that performs the following operations. First, test the DequeADT: - Create a DequeADT variable for subtype 'String' that contains a LinkedDeque object. - Add 10 items to the front (all items should be unique, hint use letters ' A ', ' B '), then print the sate of the Deque. - Remove 5 items from the back (and print the state of the Deque) - Add 5 items to the back (and print the state of the Deque) - Perform a circular right shift 10 times - A circular right shift means to remove an from the back, then add that same element to the front - Be sure to print out the state of the Deque after each shift - Perform a circular left shift 10 times - A circular left shift means to remove an from the front, then add that same element to the back - Be sure to print out the state of the Deque after each shift - getLast() to print out the last element Then, use a Deque as a stack using the StackADT: - Make variable of type 'StackADT', and instantiate it with a LinkedDeque object - push() 5 elements, print out stack - pop() each element and print it out in a while loop Then, use a Deque as a queue using the QueueADT: - Make variable of type 'QueueADT, and instantiate it with a LinkedDeque object - enqueue() 5 elements, print out queue - dequeue( ) an element each element and print it out in a while loop