I'm trying to finish the homework that I need to finish. But I don't know how to do this correctly.

Here are my source codes

And also could you please explain to me? I tried to understand what is keyValuePair. And also I have no idea what function and value I need to use.

MaxPQ.java

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

/************************************************************************* * Compilation: javac MaxPQ.java * Execution: java MaxPQ MaxPQ class represents a priority queue of generic keys. * It supports the usual insert and delete-the-maximum * operations, along with methods for peeking at the maximum key, * testing if the priority queue is empty, and iterating through * the keys. * 
 * This implementation uses a binary heap. * The insert and delete-the-maximum operations take * logarithmic amortized time. * The max, size, and is-empty operations take constant time. * Construction takes time proportional to the specified capacity or the number of * items used to initialize the data structure. * 
 * For additional documentation, see Section 2.4 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class MaxPQ implements Iterable { private Key[] pq; // store items at indices 1 to N private int N; // number of items on priority queue private Comparator comparator; // optional Comparator /** * Initializes an empty priority queue with the given initial capacity. * @param initCapacity the initial capacity of the priority queue */ public MaxPQ(int initCapacity) { pq = (Key[]) new Object[initCapacity + 1]; N = 0; } /** * Initializes an empty priority queue. */ public MaxPQ() { this(1); } /** * Initializes an empty priority queue with the given initial capacity, * using the given comparator. * @param initCapacity the initial capacity of the priority queue * @param comparator the order in which to compare the keys */ public MaxPQ(int initCapacity, Comparator comparator) { this.comparator = comparator; pq = (Key[]) new Object[initCapacity + 1]; N = 0; } /** * Initializes an empty priority queue using the given comparator. * @param comparator the order in which to compare the keys */ public MaxPQ(Comparator comparator) { this(1, comparator); } /** * Initializes a priority queue from the array of keys. * Takes time proportional to the number of keys, using sink-based heap construction. * @param keys the array of keys */ public MaxPQ(Key[] keys) { N = keys.length; pq = (Key[]) new Object[keys.length + 1]; for (int i = 0; i = 1; k--) sink(k); assert isMaxHeap(); } /** * Is the priority queue empty? * @return true if the priority queue is empty; false otherwise */ public boolean isEmpty() { return N == 0; } /** * Returns the number of keys on the priority queue. * @return the number of keys on the priority queue */ public int size() { return N; } /** * Returns a largest key on the priority queue. * @return a largest key on the priority queue * @throws java.util.NoSuchElementException if the priority queue is empty */ public Key max() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; } // helper function to double the size of the heap array private void resize(int capacity) { assert capacity > N; Key[] temp = (Key[]) new Object[capacity]; for (int i = 1; i = pq.length - 1) resize(2 * pq.length); // add x, and percolate it up to maintain heap invariant pq[++N] = x; swim(N); assert isMaxHeap(); } /** * Removes and returns a largest key on the priority queue. * @return a largest key on the priority queue * @throws java.util.NoSuchElementException if priority queue is empty. */ public Key delMax() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); Key max = pq[1]; exch(1, N--); sink(1); pq[N+1] = null; // to avoid loiterig and help with garbage collection if ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2); assert isMaxHeap(); return max; } /*********************************************************************** * Helper functions to restore the heap invariant. **********************************************************************/ private void swim(int k) { while (k > 1 && less(k/2, k)) { exch(k, k/2); k = k/2; } } private void sink(int k) { while (2*k ) pq[i]).compareTo(pq[j])  N) return true; int left = 2*k, right = 2*k + 1; if (left remove() since it's optional. * @return an iterator that iterates over the keys in descending order */ public Iterator iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator { // create a new pq private MaxPQ copy; // add all items to copy of heap // takes linear time since already in heap order so no keys move public HeapIterator() { if (comparator == null) copy = new MaxPQ(size()); else copy = new MaxPQ(size(), comparator); for (int i = 1; i MaxPQ data type. */ public static void main(String[] args) { MaxPQ pq = new MaxPQ(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) pq.insert(item); else if (!pq.isEmpty()) StdOut.print(pq.delMax() + " "); } StdOut.println("(" + pq.size() + " left on pq)"); } } 

------------------------------------------------------------------------------------------------------------------------------

Stack.java

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

/************************************************************************* * Compilation: javac Stack.java * Execution: java Stack Stack class represents a last-in-first-out (LIFO) stack of generic items. * It supports the usual push and pop operations, along with methods * for peeking at the top item, testing if the stack is empty, and iterating through * the items in LIFO order. * 
 * This implementation uses a singly-linked list with a static nested class for * linked-list nodes. See {@link LinkedStack} for the version from the * textbook that uses a non-static nested class. * The push, pop, peek, size, and is-empty * operations all take constant time in the worst case. * 
 * For additional documentation, see Section 1.3 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class Stack { private int N; // size of the stack private int currentPriority; // priority for next item added to stack private MaxPQ pq; // PQ used to store items in stack private class KeyValuePair implements Comparable { Item item; int priority; KeyValuePair(Item i) { // TODO: initialize fields in the new instance } public int compareTo(KeyValuePair b) { // TODO: Implement method // return -1 if this instance should come before b in sorted order // return +1 if this instance should come after b in sorted order // return 0 if this instance is equivalent to b // Question to answer: which field in KeyValuePair should be used // to order the instances? } }; /** * Initializes an empty stack. */ public Stack() { // TODO: Implement constructor } /** * Is this stack empty? * @return true if this stack is empty; false otherwise */ public boolean isEmpty() { // TODO: return whether stack is empty or not } /** * Returns the number of items in the stack. * @return the number of items in the stack */ public int size() { // TODO: return number of items in stack } /** * Adds the item to this stack. * @param item the item to add */ public void push(Item item) { // TODO: push a new item on stack } /** * Removes and returns the item most recently added to this stack. * @return the item most recently added * @throws java.util.NoSuchElementException if this stack is empty */ public Item pop() { // TODO: remove and return top item from stack } /** * Returns (but does not remove) the item most recently added to this stack. * @return the item most recently added to this stack * @throws java.util.NoSuchElementException if this stack is empty */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); // TODO: return top item (but don't remove) } /** * Unit tests the Stack data type. */ public static void main(String[] args) { Stack s = new Stack(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) s.push(item); else if (!s.isEmpty()) StdOut.print(s.pop() + " "); } StdOut.println("(" + s.size() + " left on stack)"); } } 

1. (100 points) Priority queue application. Implement a stack data structure using a priority queue. For this you should complete Stack.java. It contains the basic skeleton for your solution. You will need to implement all of the existing methods with a maxPQ instead of a linked list. Do not modify maxPQ.java You will only modify Stack.java The linked list implementation LinkedStack.java has been included only for reference. You will not need to use or modify it Since each item has a priority, an inner class KeyValuePair has been started for you. This class contains both an item in the stack and its priority. To a programmer using your stack class, they should only ever see the items that they put into the stack. They should not know anything about KevValuePair The priority queue will store KeyValuePair items. So that KeyValuePair instances can be ordered within the priority queue, this class implements the Comparable interface. You will need to complete the method compareTo so that KeyValuePair instances can be ordered based on their priority values. The main method should function just as it does in LinkedStack.java. You should be able to push and pop elements with your new stack just as before. NOTE: The java files require the library stdlib.jar which is provided in the hu4.files.zip file. You will need to add this library to your project's classpath as you did before in earlier assignments. Submission When done, submit all of your modified java files to the hw4 dropbox on LearningHub. The code must be in a text file with java extension (not in a DOC file or PDF) When submitting your solutions include: source code (zero points if missing) Your name in comments at the top of your source code along with the original comments in the book code (-5 pts if missing) output from Stack.java (-5 pts if missing). Use the input sequence: 5 3 27--hi world Strings (separated by whitespace) are pushed onto the stack. -' pops and outputs items from the stack. After typing this sequence, you s i should see: 2 7 3 5 world