Priority Queues implementation in java


In this Data structures tutorial we will learn what is Priority Queues in java with example and program. We will learn how to implement your own Priority Queues in java. We will learn how to insert and remove element from Priority Queues in java.




Priority Queue is Collection of entities or elements in which >
Addition of element is done on basis of priority.
Removal of element is done at FRONT.

Example of Priority Queues in java >
There might be a case where patients are waiting for some regular check up with the doctor, but certainly some patient might come with some emergency, he will surely be given priority as compared to regular patients in java.

Inserting element in Priority Queue in java >


Removing element from Priority Queue in java>


Full Program/Example of Priority Queues implementation in java, insert and remove element from Priority Queues in java >
/**
*Exception to indicate that Queue is full.
*/
class QueueFullException extends RuntimeException {
  
   public QueueFullException(){
       super();
   }
   
   public QueueFullException(String message){
       super(message);
   }
   
}
/**
*Exception to indicate that Queue is empty.
*/
class QueueEmptyException extends RuntimeException {
  
   public QueueEmptyException(){
       super();
   }
   
   public QueueEmptyException(String message){
       super(message);
   }
   
}
/** Copyright (c), AnkitMittal JavaMadeSoEasy.com */
/**
*
* Priority Queue Class
*
*/
class PriorityQueue {
  
   private int[] prioQueueAr;
   private int size;//Size of Queue
   private int number;  //holds number of elements in Priority Queue, initialized with 0 by default
   public PriorityQueue(int size){
          this.size = size;
          prioQueueAr = new int[this.size];
          number = 0;
   }
   /**
   * Insert element in Priority Queue, element will be inserted on basis of priority.
   */
   public void insert(int value){
          int i;
          if(isFull()){
                 throw new QueueFullException("Cannot insert "+value+", Queue is full");
          }                      
          if (number == 0)
                 prioQueueAr[number++] = value; //If no values in PriorityQueue- insert at starting position, i.e. at 0th position.
          else{
                 for (i=number - 1; i>= 0; i--){             
                       if (value > prioQueueAr[i])
                              prioQueueAr[i + 1] = prioQueueAr[i]; //if value is larger, shift elements upward till value is larger.
                       else
                              break;
                 }
                 prioQueueAr[++i] = value; // insert element in space created by upward shift of elements.
                 number++;
          }
   }
   /**
   * Remove elements from Priority Queue
   */
   public int remove(){
          if(isEmpty()){
                 throw new QueueEmptyException("Queue is empty");
          }
          return prioQueueAr[--number];
   }
   /**
   * Returns true if Priority Queue is full
   * @return
   */
   public boolean isFull(){
          return (number == size);
   }
  
   /**
   * Returns true if Priority Queue is empty
   * @return
   */
   public boolean isEmpty(){
          return (number == 0);
   }
  
}
/**
* Main Class
*/
public class PriorityQueueExample {
   public static void main(String[] args) {
          PriorityQueue priorityQueue = new PriorityQueue(10); // Priority Queue holds 10 elements
         
          priorityQueue.insert(81);
          priorityQueue.insert(72);
          priorityQueue.insert(52);
          priorityQueue.insert(61);
         
          System.out.print("Deleted elements from queue: ");
          System.out.print(priorityQueue.remove()+" ");
          System.out.print(priorityQueue.remove()+" ");
          System.out.print(priorityQueue.remove()+" ");
          System.out.print(priorityQueue.remove()+" ");
                
   }
         
}
/** OUTPUT
Deleted elements from queue: 52 61 72 81
*/

If we analyze output of above Priority Queue example, we will find that- element were inserted in queue on basis of priority and removed from the front position.


Complexity of Priority Queues in java >
Insert - O(n) [as we insert element in middle of priority queue on basis of priority]
Remove - O(1) [as we remove element from front of priority queue in java]

In this Data structures tutorial we will learn what is Priority Queues in java with example and program. We will learn how to implement your own Priority Queues in java. We learned how to insert and remove element from Priority Queues in java.



Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.


RELATED LINKS>

Stacks, Queues in java



Some of the tricky and interesting Singly LinkedList implementations in java





Implement Stack, Queue using LinkedList.


No comments:

Post a Comment