

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



When to use LinkedList or ArrayList?
Accessing elements are faster with ArrayList, because it is index based.
But accessing is difficult with LinkedList. It is slow access. This is
to access any element, you need to navigate through the elements one by
one. But insertion and deletion is much faster with LinkedList, because
if you know the node, just change the pointers before or after nodes.
Insertion and deletion is slow with ArrayList, this is because, during
these operations ArrayList need to adjust the indexes according to
deletion or insetion if you are performing on middle indexes. Means,
an ArrayList having 10 elements, if you are inserting at index 5, then
you need to shift the indexes above 5 to one more.
It is amazing what you can accomplish if you do not care who gets the credit.
 Harry Truman
