Create a class called HeapStack that implements the StackADT interfaceusing the LinkedHeap implementation from the Java Foundations book. Keep in mind that a stack is a LIFO structure. Thus, the comparison in the heap will have to be according to order entry into the stack. You must use a heap to implement the StackADT interface.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

package jsjf; import jsjf.exceptions.*; public class LinkedMaxHeap> extends LinkedBinaryTree { private HeapNode last; // Creates a max heap with the specified element as its root. //----------------------------------------------------------------- public LinkedMaxHeap () { super(); last = null; } //----------------------------------------------------------------- // Creates a max heap with the specified element as its root. //----------------------------------------------------------------- public LinkedMaxHeap (T element) { root = new HeapNode(element); last = (HeapNode)root; } //----------------------------------------------------------------- // Adds the specified element to this heap by adding it as a leaf // then reestablishing the heap relationships. //----------------------------------------------------------------- public void add (T element) { HeapNode node = new HeapNode(element); HeapNode newParent = null; if (root == null) root = node; else { newParent = ((HeapNode)root).getParentAdd(last); if (newParent.left == null) newParent.setLeft(node); else newParent.setRight(node); } node.setParent(newParent); last = node; ((HeapNode)root).heapifyAdd(last); } public T removeMax() { if (root == null) throw new EmptyCollectionException ("Remove max operation " + "failed. Tree is empty."); T maxElement = root.getElement(); if (root.count() == 1) root = last = null; else { HeapNode newLast = ((HeapNode)root).getNewLastNode(last); if (last.parent.left == last) last.parent.left = null; else last.parent.right = null; root.setElement(last.getElement()); last = newLast; ((HeapNode)root).heapifyRemove((HeapNode)root); } return maxElement; } //----------------------------------------------------------------- // The following method is left as a programming project. //----------------------------------------------------------------- // public T getMax() { } }//end class

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

package jsjf; /** * 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 */ public T pop(); /** * Returns without removing the top element of this stack. * @return the element on top of the stack */ public T peek(); /** * Returns true if this stack contains no elements. * @return true if the stack is empty */ public boolean isEmpty(); /** * Returns the number of elements in this stack. * @return the number of elements in the stack */ public int size(); /** * Returns a string representation of this stack. * @return a string representation of the stack */ public String toString(); }

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

public class HeapNode> extends BinaryTreeNode { HeapNode parent; //----------------------------------------------------------------- // Creates a new heap node with the specified data. //----------------------------------------------------------------- public HeapNode (T element) { super(element); parent = null; } //----------------------------------------------------------------- // Returns the parent node of this node. //----------------------------------------------------------------- public HeapNode getParent() { return parent; } //----------------------------------------------------------------- // Returns the parent node of this node. //----------------------------------------------------------------- public void setParent(HeapNode parent) { this.parent = parent; } //----------------------------------------------------------------- // Returns the node that will be the parent of the new node. //----------------------------------------------------------------- public HeapNode getParentAdd (HeapNode last) { HeapNode result = last; while ((result.parent != null) && (result.parent.left != result)) result = result.parent; if (result.parent != null) if (result.parent.right == null) result = result.parent; else { result = (HeapNode) result.parent.right; while (result.left != null) result = (HeapNode) result.left; } else while (result.left != null) result = (HeapNode) result.left; return result; } //----------------------------------------------------------------- // Moves a newly added leaf up the tree as far as appropriate to // reestablish the heap. //----------------------------------------------------------------- public void heapifyAdd (HeapNode last) { T temp; HeapNode current = last; while ((current.parent != null) && ((current.element).compareTo(current.parent.element) > 0)) { temp = current.element; current.element = current.parent.element; current.parent.element = temp; current = current.parent; } } //----------------------------------------------------------------- // Returns the node that will be the new last node after a remove. //----------------------------------------------------------------- public HeapNode getNewLastNode(HeapNode last) { HeapNode result = last; while ((result.parent != null) && (result.parent.left == result)) result = result.parent; if (result.parent != null) result = (HeapNode) result.parent.left; while (result.right != null) result = (HeapNode) result.right; return result; } //----------------------------------------------------------------- // Reorders this heap after removing the root element. //----------------------------------------------------------------- public void heapifyRemove(HeapNode root) { T temp; HeapNode current = root; HeapNode next = largerChild (current); while (next != null && next.element.compareTo(current.element) > 0) { temp = current.element; current.element = next.element; next.element = temp; current = next; next = largerChild (current); } } //----------------------------------------------------------------- // Returns the larger of the two children of the specified node. //----------------------------------------------------------------- public HeapNode largerChild (HeapNode node) { HeapNode larger = null; if (node.left == null && node.right == null) larger = null; else if (node.left == null) larger = (HeapNode)node.right; else if (node.right == null) larger = (HeapNode)node.left; else if (((HeapNode)node.left).element.compareTo( ((HeapNode) node.right).element) > 0) larger = (HeapNode)node.left; else larger = (HeapNode)node.right; return larger; } }