Java PQ stack In this assignment you will practice using pri

Java PQ stack

In this assignment you will practice using priority queues. Download the attached base file, then rename it, and the class inside, to include your last name instead of \"Base\". The other files are interfaces and a priority queue implementation.

Despite outward appearances, Stacks and Queues are both related to sorting. This can be illustrated with the help of Priority Queues. Use a priority queue to implement a stack. Your PQStack should not use a separate array or list to store data - just a priority queue.

BasePQStack.java:

MaxPQ.java:

PriorityQueue.java:

Stack.java:

I have implemented PQStack.java class. Please let me know in comments if you have any issues: -

MaxPQ.java

/**
* An array based implementation of a priority queue.
*
*/
public class MaxPQ<Key> implements PriorityQueue<Key> {
private Key[] pq;
private int N = 0;

public MaxPQ() {
this(100);
}

public MaxPQ(int maxN) {
pq = (Key[]) new Comparable[maxN+1];
}

@Override
public boolean isEmpty() {
return N == 0;
}

@Override
public int size() {
return N;
}

@Override
public void insert(Key v) {
pq[++N] = v;
swim(N);
}

@Override
public Key max() {
return pq[1];
}

@Override
public Key delMax() {
Key max = pq[1];
exch(1, N--);
pq[N+1] = null;
sink(1);
return max;
}

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 <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}

private boolean less(int i, int j) {
return ((Comparable) pq[i]).compareTo(pq[j]) < 0;
}

private void exch(int i, int j) {
Key swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
}

/*
public void sort(Comparable[] a) {

int N = a.length;
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
while (N > 1) {
exch(a, 1, N--);
sink(a, 1, N);
}
}
*/
}

PriorityQueue.java

public interface PriorityQueue<Key> {

/**
* Adds an element.
*
* @param value value to insert
*/
public void insert(Key value);

/**
* Returns the maximum element.
*
* @return maximum element
* @throws NoSuchElementException
*/
public Key max() throws NoSuchElementException;

/**
* Returns and removes the maximum element.
*
* @return
* @throws NoSuchElementException
*/
public Key delMax() throws NoSuchElementException;

/**
* Checks if the PQ is empty.
*
* @return
*/
public boolean isEmpty();

/**
* Number of elements in the PQ.
*
* @return size
*/
public int size();
}

Stack.java

/**

* A simple stack interface.

public interface Stack<Item> {

/**

* Add an item.

* @param item

* an item

public void push(Item item);

/**

* Remove the most recently added item.

* @return an item

public Item pop() throws NoSuchElementException;

/**

* Return, but do not remove, the most recently added item.

* @return an item

public Item peek() throws NoSuchElementException;

/**

* Is the queue empty?

* @return if empty

public boolean isEmpty();

/**

* Number of items in the queue.

* @return number of items

public int size();

}

PQStack.java

public class PQStack<E> implements Stack<E> {

private PriorityQueue<E> p;

public PQStack() {

p = new MaxPQ<>();

}

// TODO: implement this object.

/**

* entry point for sample output..

* @param args

public static void main(String[] args) {

Stack<Integer> S = new PQStack<Integer>();

S.push(new Integer(2));

S.push(new Integer(7));

Integer W = S.pop();

S.push(new Integer(8));

S.push(new Integer(5));

Integer X = S.pop();

Integer Y = S.peek();

S.push(new Integer(3));

Integer Z = S.pop();

System.out.println(\"Testing: \");

System.out.println(W);

System.out.println(X);

System.out.println(Y);

System.out.println(Z);

}

@Override

public void push(E item) {