

Priority Queue introduction and Java implementation
A priority queue is an abstract data type, it is like a regular queue or stack data structure, but where
additionally each element has a priority associated with it. In a priority queue, an element with high priority is
served before an element with low priority. If two elements have the same priority, they are served according to their
order in the queue.
There are a variety of simple ways to implement a priority queue. For instance, one can keep all the elements
in an unsorted list. Whenever the highestpriority element is requested, search through all elements for the one with the
highest priority. In big O notation: O(1) insertion time, O(n) pull time due to search.
Below example shows basic implementation of priority queue. The condition here is, the element to be inserted
should implement Comparable interface, we have taken Integer object, which is already implementing this interface.
package com.java2novice.ds.queue;
public class PriorityQueueImpl {
@SuppressWarnings("rawtypes")
private Comparable[] pQueue;
private int index;
public PriorityQueueImpl(int capacity){
pQueue = new Comparable[capacity];
}
public void insert(Comparable item ){
if(index == pQueue.length){
System.out.println("The priority queue is full!! can not insert.");
return;
}
pQueue[index] = item;
index++;
System.out.println("Adding element: "+item);
}
@SuppressWarnings("unchecked")
public Comparable remove(){
if(index == 0){
System.out.println("The priority queue is empty!! can not remove.");
return null;
}
int maxIndex = 0;
// find the index of the item with the highest priority
for (int i=1; i<index; i++) {
if (pQueue[i].compareTo (pQueue[maxIndex]) > 0) {
maxIndex = i;
}
}
Comparable result = pQueue[maxIndex];
System.out.println("removing: "+result);
// move the last item into the empty slot
index;
pQueue[maxIndex] = pQueue[index];
return result;
}
public static void main(String a[]){
PriorityQueueImpl pqi = new PriorityQueueImpl(5);
pqi.insert(34);
pqi.insert(23);
pqi.insert(5);
pqi.insert(87);
pqi.insert(32);
pqi.remove();
pqi.remove();
pqi.remove();
pqi.remove();
pqi.remove();
}
}


Output: 
Adding element: 34
Adding element: 23
Adding element: 5
Adding element: 87
Adding element: 32
removing: 87
removing: 34
removing: 32
removing: 23
removing: 5





List of Queue Data Structure Examples
 Queue introduction & array based implementation
 Dynamic Queue implementation using arrays
 Doubleended queue (Decue) Implementation
 Doubleended queue (Decue) implementation using Doubly linked list
 Priority Queue introduction and Java implementation



What is wrapper class?
Everything in java is an object, except primitives. Primitives are
int, short, long, boolean, etc. Since they are not objects, they cannot
return as objects, and collection of objects. To support this, java provides
wrapper classes to move primitives to objects. Some of the wrapper classes
are Integer, Long, Boolean, etc.
It is easier to fight for one’s principles than to live up to them.
 Alfred Adler
