IT Certificaions

Google Cloud Platform

Tuesday, September 20, 2011

Priority Queue in Collection in Java 6


Priority Queue:

  • This class has been added in Java 5. Since the LinkedList class has been enhanced to implement the Queue interface, basic queues can be handled with a LinkedList. 
  • The purpose of a PriorityQueue is to create a "priority-in, priority out" not just a typical FIFO queue. 
  • A PriorityQueue's elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a Comparator. In either case, the elements' ordering represents their relative priority.
See Example: 

import java.util.*;

class PriorityQueueTest{
   static class PQsort implements Comparator<Integer> { // inverse sort

      public int compare(Integer one, Integer two) {
         return two - one; // unboxing
      }

   }

   public static void main(String[] args) {
       int[] ia = {1,5,3,7,6,9,8 }; // unordered data

       PriorityQueue<Integer> pq1 =new PriorityQueue<Integer>(); // use natural order

       for(int x : ia) // load queue
    pq1.offer(x);
       
  System.out.print("\n====Priority queue<Integer> after using offer()===== \n");
       for(int x : ia) // review queue
          System.out.print(pq1.poll() + " ");  // The poll() method returns top head of Queue as well as delete it from queue.

  // Now Queue is empty

      System.out.print("\n===================================================== ");
       System.out.println("");
       PQsort pqs = new PQsort(); // get a Comparator

       PriorityQueue<Integer> pq2 =new PriorityQueue<Integer>(10,pqs); // use Comparator ::  Creates a PriorityQueue with the specified initial capacity 10 that orders its elements according to the specified comparator.
       for(int x : ia) // load queue
         pq2.offer(x);

  // Now pq2 ::  9 8 7 6 5 3 1
 
       System.out.println("\n size " + pq2.size());
       System.out.println(" peek " + pq2.peek());    // The peek() method returns top head of Queue not delete it as poll() do both (return head and delete).
       System.out.println(" size " + pq2.size());
       System.out.println(" poll " + pq2.poll());   // poll(): Retrieves and removes the head of this queue, or returns null if this queue is empty.
       System.out.println(" size " + pq2.size());
       for(int x : ia) // review queue
         System.out.print(pq2.poll() + " ");
    }
}