• Fill in the missing code in method toString of class DoublyLinkedStack. Note that the String representation returned by this method must contain all the items in the stack in order starting from the bottom. So, if for example in an empty stack we push in order the values 1, 2, and 3, the value 1 would be at the bottom and the value 3 would be at the top. Method toString would return in this case the string "1, 2, 3". Class DoublyLinkedStack implements a stack using a doubly linked list. Instance variable top points to the first node of the linked list; the linked list can be traversed forward using method getNext and it can be traversed backwards using method getPrevious from class DoublyLinkedList. Hint. Try to answer the above question without first reading this hint. Start at top and traverse the list until you find the last node in the list. Then traverse the list back towards the top adding the elements stored in the nodes to an initially empty string.
• Run TestStackDLL. A null pointer exception will be thrown. Use the debugger to find out which statement throws the exception and why. Explain where and why the exception was thrown.
• Fix the code and run TestStackDLL. It must print "0, 1, 2, 3, 4".
• --------------------------------------------------------------------------------------------------------------------------------------

• public class DoublyLinkedList{ private DoublyLinkedList next; private DoublyLinkedList previous; private E element; public DoublyLinkedList(){ next = null; previous = null; element = null; } public DoublyLinkedList (E elem){ next = null; previous = null; element = elem; } public DoublyLinkedList getNext(){ return next; } public DoublyLinkedList getPrevious(){ return previous; } public void setNext (DoublyLinkedList node){ next = node; } public void setPrevious (DoublyLinkedList node){ previous = node; } public E getElement(){ return element; } public void setElement (E elem){ element = elem; } }

• --------------------------------------------------------------------------------------------------------------------------------------

• public class DoublyLinkedStack implements StackADT { /** indicates number of elements stored */ private int count; /** pointer to top of stack */ private DoublyLinkedList top;

  /** * Creates an empty stack. */ public DoublyLinkedStack() { count = 0; top = null; }

  /** * Adds the specified element to the top of this stack. * * @param element element to be pushed on stack */ public void push(T element) { DoublyLinkedList temp = new DoublyLinkedList(element);

  temp.setNext(top); top.setPrevious(temp); top = temp; count++; }

  /** * Removes the element at the top of this stack and returns a reference to it. * Throws an EmptyCollectionException if the stack is empty. * * @return T element from top of stack * @throws EmptyCollectionException on pop from empty stack */ public T pop() { if (isEmpty()) throw new EmptyCollectionException("Stack");

  T result = top.getElement(); top = top.getNext(); if (top != null) top.setPrevious(null); count--;

  return result; }

  /** * Returns a reference to the element at the top of this stack. The element is * not removed from the stack. Throws an EmptyCollectionException if the stack * is empty. * * @return T element on top of stack * @throws EmptyCollectionException on peek at empty stack */ public T peek() { if (isEmpty()) throw new EmptyCollectionException("Stack");

  return top.getElement(); }

  /** * Returns true if this stack is empty and false otherwise. * * @return boolean true if stack is empty */ public boolean isEmpty() { return (count == 0); }

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

  /** * Returns a string representation of this stack. * @return */ public String toString() { String res = ""; DoublyLinkedList curr = top; }

  } ------------------------------------------------------------------------------------------------

• public class EmptyCollectionException extends RuntimeException { /** * Sets up this exception with an appropriate message. * @param collection String representing the name of the collection */ public EmptyCollectionException (String collection) { super ("The " + collection + " is empty."); } }

• -----------------

• public interface StackADT { /** Adds one element to the top of this stack. * @param element element to be pushed onto stack */ public void push (T element); /** Removes and returns the top element from this stack. * @return T element removed from the top of the stack */ public T pop();

  /** Returns without removing the top element of this stack. * @return T element on top of the stack */ public T peek(); /** Returns true if this stack contains no elements. * @return boolean whether or not this stack is empty */ public boolean isEmpty();

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

  /** Returns a string representation of this stack. * @return String representation of this stack */ public String toString(); } ------------

• public class TestStackDLL { public static void main(String[] args) { // create a DoublyLinkedList with 5 nodes DoublyLinkedStack stack = new DoublyLinkedStack(); for (int i = 0; i < 5; ++i) stack.push(Integer.valueOf(i));

  String result = stack.toString(); System.out.println(result); } }

• --------------

• public class TestStackDLL { public static void main(String[] args) { // create a DoublyLinkedList with 5 nodes DoublyLinkedStack stack = new DoublyLinkedStack(); for (int i = 0; i < 5; ++i) stack.push(Integer.valueOf(i));

  String result = stack.toString(); System.out.println(result); } }