I really don't know how to create Stack.java by using maxPQ.

I made some of the codes but it is literally hard to apply to Stack.

could you please help me with solving this problem?

Here are my source codes.

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 int counter; private class KeyValuePair implements Comparable { Item item; int priority; int counter; KeyValuePair(Item i) { // TODO: initialize fields in the new instance Item item; int priority; int counter; } public int compareTo(KeyValuePair b) { // TODO: Implement method // return -1 if this instance should come before b in sorted order if(this.priority  b.priority)return 1; // return 0 if this instance is equivalent to b else return 0; // Question to answer: which field in KeyValuePair should be used // to order the instances? // By using priority properties. } }; /** * Initializes an empty stack. */ public Stack() { // TODO: Implement constructor N = 0; currentPriority = 0; } /** * Is this stack empty? * @return true if this stack is empty; false otherwise */ public boolean isEmpty() { // TODO: return whether stack is empty or not return pq == null; } /** * 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 return N; } /** * Adds the item to this stack. * @param item the item to add */ public void push(Item item) { // TODO: push a new item on stack Item i = item; counter++; N++; } /** * Removes and returns the item most recently added to this stack. * @return the item most recently added * @throws NoSuchElementException if this stack is empty */ public Item pop() { // TODO: remove and return top item from stack Item var = (Item) pq.delMax(); N--; return var; } /** * Returns (but does not remove) the item most recently added to this stack. * @return the item most recently added to this stack * @throws NoSuchElementException if this stack is empty */ public Item peek() { if (isEmpty()) throw new NoSuchElementException("Stack underflow"); // TODO: return top item (but don't remove) Item var = (Item) pq.delMax(); push(var); return var; } /** * 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)"); } } 

MaxPq

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

/************************************************************************* * 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 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 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)"); } } 

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 KeyValuePair The priority queue wil 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