Priority Queues/Stack

Goodrich Book, Chapter 9, Priority Queues

Question C-9.26: Show how to implement the stack ADT using only a priority queue and one additional integer instance variable.

Link: https://git.charlesreid1.com/cs/java/src/master/priority-queues/UseAsStack.java

First, we can review the Stacks data structure, and revisit what it is for. The stack data structure provides fast, last-in, first-out access. It accumulates items in a stack structure that allows insertion and access at the same end.

Here is some test code for what an eventual StackPQ object should look like:

public class UseAsStack { 
	public static void main(String[] args) { 
		StackPQ<String> q = new StackPQ<String>();
		q.push("hello");
		q.push("world");
		q.push("this");
		q.push("is");
		q.push("the");
		q.push("earth");
		while(!q.isEmpty()) {
			System.out.println(q.pop());
		}
	}
}

Note that this should take only ONE generic type argument, not two, even though our priority queue takes two types. Note that this is because Priority Queue objects need to specify the type of both the keys and the values. Here, the user of the Stack object is only using the values. Behind the scenes, the Stack specifies details of the keys.

To implement a stack using a priority queue, it is key to recognize that the most recent item to be added to the stack should always be the minimum. The keys should be ordered in such a way that as items are added to the stack, the keys will descend.

This is simple to do using negative integers. The keys start at -1, and work their way down as the index of each item moves up: -1, -2, -3, -4, etc.

When we define the StackPQ class, we have one generic type for the values (type of data) being stored in the Stack. The key types of both the priority queue interface and the concrete sorted priority queue class are hard-coded as Integer types.

// NOTE: extends should go before implements
class StackPQ<V> extends SortedPQ<Integer,V> implements PriorityQueue<Integer,V> { 

	// Stack can implement a priority queue
	// by adding items and assigning keys 
	// based on order of insertion.
	// Keys should be a negative counter,
	// to keep them in reverse order added.
	int counter;

	/** Start with an empty stack. */
	public StackPQ(){ counter = 0; }

	// Stack ADT methods:

	public void push(V v) {
		counter++; // start at 1
		this.insert(new Integer(-1*counter), v);
	}

	public V pop() {
		counter--;
		return removeMin();
	}

}

If we print out the stack as we are removing items from it, we see the following output:

[(earth), (the), (is), (this), (world), (hello)]
earth
[(the), (is), (this), (world), (hello)]
the
[(is), (this), (world), (hello)]
is
[(this), (world), (hello)]
this
[(world), (hello)]
world
[(hello)]
hello
[]