Pages
Showing posts with label Queue. Show all posts
Showing posts with label Queue. Show all posts

PriorityQueue based on custom Priority setting

 
Just by name "Queue" we can think of big "Q" for Movie tickets booking in our olden days or have read about FIFO order. But here "PriorityQueue" is little different and it follows same Queue functionality with Priority items are out first.
Lets take scenario where there are lot of incoming tickets in support system with multiple priorities (CRITICAL, HIGH, MEDIUM, LOW). Here support team needs to serve all tickets based on their priority than their logged order, like critical priorities first and then high, medium and low priority tickets at last.
Lets see simple example class which takes multiple Tickets along with priority and while we are reading critical tickets 1st, high tickets 2nd, medium tickets 3rd and low priority tickets at last.


Ticket.java

/*
 * Simple Ticket class takes input as ticket number, Ticket details
 * along with priority of each ticket
 */
public class Ticket implements Comparable<Ticket>{
 
 enum Priority{
  CRITICAL, HIGH, MEDIUM, LOW 
 }
 
 private int ticketId;
 private String task;
 private Priority priority;
 
 public Ticket(int ticketId, Priority priority, String task) {
  this.ticketId = ticketId;
  this.task = task;
  this.priority = priority;
 }
 @Override
 public String toString() {
  return ticketId +" : "+task;
 }
 
 @Override
 public int compareTo(Ticket o) {
  return this.priority.compareTo(o.priority) ;
 }
}



PriorityQueueExample.java

import java.util.PriorityQueue;
import java.util.Queue;

import com.pract.Ticket.Priority;

public class PriorityQueueExample {

 public static void main(String[] args) {
  
  // Adding 6 Tickets with different priority 
  Queue<Ticket> ticketQueue = new PriorityQueue<Ticket>();
  ticketQueue.offer(new Ticket(1, Priority.LOW, "Low priority task - Cleanup activity"));
  ticketQueue.offer(new Ticket(2, Priority.MEDIUM, "Medium priority task - Taking dump"));
  ticketQueue.offer(new Ticket(3, Priority.HIGH, "High priority task - Production update"));
  ticketQueue.offer(new Ticket(4, Priority.MEDIUM, "Medium priority task - Testing"));
  ticketQueue.offer(new Ticket(5, Priority.HIGH, "High priority task - Important bug fixing"));
  ticketQueue.offer(new Ticket(6, Priority.CRITICAL, "Critical priority task - Hacker Thread"));
  
  listTicketsBasedOnPriority(ticketQueue);
 }
 
 /*
  * Listing tickets based on priority like 
  * CRITICAL, HIGH, MEDIUM and then LOW tickets.
  */
 private static void listTicketsBasedOnPriority(Queue<Ticket> tickets){
  while (!(tickets.isEmpty()))
   System.out.println(tickets.poll());
 }
}




OUTPUT:

6 : Critical priority task - Hacker Thread
5 : High priority task - Important bug fixing
3 : High priority task - Production update
2 : Medium priority task - Taking dump
4 : Medium priority task - Testing
1 : Low priority task - Cleanup activity

Here in output we can see list of tickets printed by priority order wise.

Implementing Queue in Java

 
Queue is a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first to be removed. Suppose if a queue contains 4 elements and 5th element added at back and if we need to remove that element then we need to remove all front 4 elements first. As like Stack implementation in java we can implement Queue Data Structure and also we have operations in Queue like enqueue(), dequeue(), front(), isempty() etc.,
Implementing Queue in Java

enqueue() - Insert element in front of the Queue.

 dequeue() - Return front element and remove same element from the Queue.

 front() - Same as dequeue() returns front element but same element won't be removed from the Queue.

 clean() - cleans the Queue.

Lets see simple example to implement Queue using ArrayList and using Generics for holding any datatype.

 

import java.util.ArrayList;
import java.util.List;

public class MyQueue <E>{

 private List<E> list = null;
 
 public MyQueue() {
  list = new ArrayList<E>();
 }

 public void enqueue(E val){
  list.add(val);
 }
 
 public E dequeue(){
  E val = null;
  if(list.size() > 0){
   val = list.get(0);
   list.remove(0);
  }  
  return val;
 }
 
 public boolean isEmpty(){
  if(list.size() == 0)return true;
  else return false;
 }
 
 public int size(){
  return list.size();
 }
 
 public E front(){
  E val = null;
  if(list.size() > 0){
   val = list.get(0);
  }  
  return val;
 }
 
 public void clean(){
  list = new ArrayList<E>();
 }
 
 @Override
 public String toString() {
  return list.toString();
 }
}


Our Queue class is ready and we can test with below code.

 
public class TestMyQueue {

 public static void main(String[] args) {
  
  MyQueue<String> queue = new MyQueue<String>();
  
  int qSize = queue.size();
  System.out.println("QUEUE SIZE : "+qSize);
  
  //ENQUEUE
  queue.enqueue("one");
  queue.enqueue("two");
  queue.enqueue("three");
  queue.enqueue("four");
  queue.enqueue("five");
  System.out.println("5 ELEMENTS ADDED IN QUEUE");
  qSize = queue.size();
  System.out.println("QUEUE SIZE : "+qSize);
  
  //QUEUE
  System.out.println("QUEUE      : "+queue);
  
  //FRONT
  System.out.println("FRONT       : "+queue.front());
  
  //DEQUEUE
  System.out.println("DEQUEUE        : "+queue.dequeue());
    
  qSize = queue.size();
  System.out.println("QUEUE SIZE : "+qSize);
  
  //FRONT
  System.out.println("FRONT       : "+queue.front());
  
  //ISEMPTY
  System.out.println("EMPTY      : "+queue.isEmpty());
  
  //CLEAN
  queue.clean();
  System.out.println("QUEUE CLEANED");
  
  //ISEMPTY
  System.out.println("EMPTY      : "+queue.isEmpty());
  
 }
}


OUTPUT:

 
QUEUE SIZE     : 0
5 ELEMENTS ADDED IN QUEUE
QUEUE SIZE     : 5
QUEUE             : [one, two, three, four, five]
FRONT             : one
DEQUEUE         : one
QUEUE SIZE      : 4
FRONT             : two
EMPTY             : false
QUEUE CLEANED
EMPTY             : true






PriorityBlockingQueue in Java

 
PriorityBlockingQueue in java

In our last tutorial we have see about PriorityQueue and how its used in Java with simple example. In this tutorial we will see about PriorityBlockingQueue and it works and also the difference between PriorityQueue and PriorityBlockingQueue. 
  • PriorityBlockingQueue uses same unbounded blocking queue that uses the same ordering rules as PriorityQueue and supplies blocking retrieval operations. 
  • PriorityBlockingQueue does not allow null values to be added.
  • PriorityBlockingQueue also uses natural sorting order and will not permit non-comparable objects to be insert which will result in ClassCastException exception.
  • PriorityBlockingQueue uses methods as same as PriorityQueue class except drainTo() and remainingCapacity() methods. 
  • drainTo(Collection<? super E> c) method used remove all available elements from the queue and adds them to the given collection.
  • drainTo(Collection<? super E> c, int maxElements) method used to remove at most the given number of available elements from the queue and adds them to the given collection.
  • remainingCapacity() method used to return Integer.MAX_VALUE because a PriorityBlockingQueue is not capacity constrained.
  • Method iterator() is not guaranteed to traverse the elements of PriorityBlockingQueue in any particular order. We can see this in below example. 

Difference Between PriorityBlockingQueue and PriorityQueue:
  • PriorityQueue is not thread safe, where as PriorityBlockingQueue is thread safe. 
  • PriorityBlockingQueue introduced in JDK 5 which added with concurrent package. 

Now lets see simple example for PriorityBlockingQueue and how its working under multi-threading.

 

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.PriorityBlockingQueue;

public class PriorityBlockingQueueTest {
 
 PriorityBlockingQueue<String> priBlockQ = new PriorityBlockingQueue<String>();
 
 public PriorityBlockingQueueTest(){
  priBlockQ.add("300");
  priBlockQ.add("400");
  priBlockQ.add("100");
  priBlockQ.add("500");
  priBlockQ.add("200");  
 }
 
 public void performTask() {
  // traversing order not guaranteed
  System.out.println("\nQueue iterator() : ");
  Iterator<String> itr = priBlockQ.iterator();
  while (itr.hasNext()) {
   String string = (String) itr.next();
   System.out.print(string+", ");
  }
  
  System.out.println("\n\nList iterator() : ");
  List<String> list = new ArrayList<String>();
  priBlockQ.drainTo(list);
  itr = list.iterator();
  while (itr.hasNext()) {
   String string = (String) itr.next();
   System.out.print(string+", ");
  }
  
  System.out.println("\n\ncontains() : "+priBlockQ.contains("400"));
  System.out.println("\nremainingCapacity() : "+priBlockQ.remainingCapacity());
 }
 
 public static void main(String[] args) {
  new PriorityBlockingQueueTest().performTask();
 }
}


OUTPUT:

 
Queue iterator() : 
100, 200, 300, 500, 400, 

List iterator() : 
100, 200, 300, 400, 500, 

contains() : false

remainingCapacity() : 2147483647








PriorityQueue in Java

 
PriorityQueue in Java

PriorityQueue is unbounded priority queue based on priority heap. 
  • Basically PriorityQueue are ordered according to natural ordering or by a Comparator provided at queue construction time, depending on which constructor is used. 
  • Another important that PriorityQueue won't take null value as input. 
  • Since PriorityQueue reply on natural ordering it won't take non-comparable object as input which will throw ClassCastException. 
  • Internally memory size will be managed automatically as and when elements added to the PriorityQueue.
  • By using Iterator interface its not guaranteed to traverse the elements of the PriorityQueue in any particular order. For ordered traversal need to use Arrays.sort(pq.toArray()). 
  • By implementation PriorityQueue is not synchronized and non-thread safe. Suppose if we need synchronized/thread-safe Queue then we need to go for PriorityBlockingQueue class instead of PriorityQueue.

Lets see list of constructors and methods in PriorityQueue class.

 Constructors:

 PriorityQueue()
          Default constructor which orders the elements in natural ordering.

 PriorityQueue(Collection<? extends E> c)
          PriorityQueue will be created containing the elements in the specified collection.
 
PriorityQueue(int initialCapacity)
 PriorityQueue will be created with the initial size specified and orders its elements according to their natural ordering.

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
 PriorityQueue will be created with the initial size specified and orders its elements according to the specified comparator

PriorityQueue(PriorityQueue<? extends E> c)
          PriorityQueue will be created with containing the elements in the specified priority queue.

 PriorityQueue(SortedSet<? extends E> c)
          PriorityQueue will be created with containing the elements in the specified sorted set.
Methods:

 boolean add(E e) 
Inserts the Element into PriorityQueue.

 void clear()
Removes all elements from PriorityQueue.

 Comparator<? super E> comparator()
Return Comparator used to order the elements in queue, or returns null if its ordered the queue in natural ordering. 

 boolean contains(Object o) 
Return true if particular Object present in the queue else false.

 Iterator<E> iterator() 
Used to iterate over the elements in the queue.

 boolean offer(E e) 
Its same as add() method inserts the Elements into PriorityQueue.

 Element peek()
Retrieves the Element from the head of queue else return null if queue is empty.

 Element poll()
Retrieves and removes the Element from the head of queue else return null if queue is empty.

 boolean remove() 
Retrieves and removes head of this queue.

 boolean remove(Object o) 
Removes given Object from the queue if its present in the queue.

 int size()
Returns the queue size. 

 Object[] toArray()
Returns Object array containing all of the elements in this queue.

  <T> T[] toArray(T[] a)
Returns an array containing all of the elements in this queue; the run-time type of the returned array is that of the specified array and returned array elements are in no particular order.

Now lets see simple program using PriorityQueue class

 
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueTest {

 public static void main(String[] args) {
  
  Queue<String> pq = new PriorityQueue<String>();
  
  pq.add("java");
  pq.add("servlet");
  pq.add("hibernate");
  
  pq.offer(".net");
  pq.offer("c");
  pq.offer("Pascal");
  
  System.out.println("\nPriorityQueue size() : "+pq.size());
  
  System.out.println("\nPriorityQueue peek() : "+pq.peek());
  
  System.out.println("\nIerating Queue Elements : ");
  Iterator<String> itr = pq.iterator();
  while (itr.hasNext()) {
   String string = (String) itr.next();
   System.out.print(string+", ");
  }
  
  System.out.println("\n\nPriorityQueue poll() : "+pq.poll());
  
  System.out.println("\nPriorityQueue size() : "+pq.size());
  
  System.out.println("\nPriorityQueue remove() : "+pq.remove());
  
  System.out.println("\nPriorityQueue remove(\".net\") : "+pq.remove(".net"));
  
  System.out.println("\nPriorityQueue contains() : "+pq.contains("java"));
  
  System.out.println("\nPriorityQueue toArray() : ");
  Object[] array = pq.toArray();
  for (Object object : array) {
   System.out.print(object.toString()+", ");
  }
 }
}


OUTPUT:

 
PriorityQueue size() : 6

PriorityQueue peek() : .net

Ierating Queue Elements : 
.net, c, Pascal, servlet, hibernate, java, 

PriorityQueue poll() : .net

PriorityQueue size() : 5

PriorityQueue remove() : Pascal

PriorityQueue remove(".net") : false

PriorityQueue contains() : true

PriorityQueue toArray() : 
c, hibernate, java, servlet,








Get updates in your email box

Complete the form below, and we'll send you our recent update.

Deliver via FeedBurner
© Copyright 2015 Java Discover. Designed by Bloggertheme9 | Distributed By Gooyaabi Templates. Powered by Blogger.