/**

* Book: Data Structures and Algorithms in Java, by Robert LaFore

* Chapter 4:

* priorityQ.java

* demonstrates priority queue

* to compile this code: javac priorityQ.java

* to run this program: java PriorityQApp

*/

class PriorityQ {

// array in sorted order, from max at 0 to min at size-1

private int maxSize;

private long[] queArray;

private int nItems;

public PriorityQ(int s) { // constructor

maxSize = s;

queArray = new long[maxSize];

nItems = 0;

}

public void insert(long item) { // insert item

int j;

if (nItems == 0) // if no items,

queArray[nItems++] = item; // insert at 0

else { // if items,

for (j=nItems-1; j>=0; j--) { // start at end,

if (item > queArray[j]) // if new item larger,

queArray[j+1] = queArray[j]; // shift upward

else // if smaller,

break; // done shifting

}

queArray[j+1] = item; // insert it

nItems++;

}

} // end insert()

public long remove() { // remove minimum item

return queArray[--nItems];

}

public long peekMin() { // peek at minimum item

return queArray[nItems-1];

}

public boolean isEmpty() { // true if queue is empty

return (nItems == 0);

}

public boolean isFull() { // true if queue is full

return (nItems == maxSize);

}

} // end class PriorityQ

class PriorityQApp {

public static void main(String[] args) {

PriorityQ thePQ = new PriorityQ(5);

thePQ.insert(30);

thePQ.insert(50);

thePQ.insert(10);

thePQ.insert(40);

thePQ.insert(20);

while(!thePQ.isEmpty()) {

long item = thePQ.remove();

System.out.print(item + " "); // 10, 20, 30, 40, 50

}

System.out.println("");

}

} // end class PriorityQApp