Search This Blog

Sunday 2 June 2013

Queues in Java

I first came across queues in Engineering. The very first chapter in data structures involved stacks and queues. So when I needed to implement one in my java project, I started recollecting the queue's working, recalling important points.I decided to build a generic structure and spend half a day coming up with a Queue interface based in generics. For good practice I decide to check the web and that is when it bombed.
The first link I opened told me that I had wasted half a day. Queues are already implemented in Java Collections framework. More specifically the ubiquitous Linked list implements a Queue.
I decided to try out the API.
public static void main(final String[] args) {
     final Queue<Integer> q = new LinkedList<Integer>();
     q.offer(1);
     q.offer(2);
     q.offer(3);

     System.out.println("Queue Contents : " + q);
     System.out.println("Element removed is " + q.poll());
     System.out.println("Element removed is " + q.poll());
     System.out.println("Element removed is " + q.poll());
     System.out.println("Element removed is " + q.poll());
     System.out.println("Queue Contents : " + q);
}
Here the offer method is used to add elements to the tail of the queue. The poll() method is used to remove an element from the head of the queue. Thus ensuring that FIFO or First In first Out behavior is correctly obeyed.
The output of the code is:
Queue Contents : [1, 2, 3]
Element removed is 1
Element removed is 2
Element removed is 3
Element removed is null
Queue Contents : []
Simple to use, isn't it ? And I was creating my own Queue interface :-|
Interestingly the Queue interface includes several other methods too. One of the interesting ones is peek. This method like poll, returns the head element, but it does not remove it from the queue.(Hence the name peek.)
Queue<Integer> q = new LinkedList<Integer>();
q.offer(1);
System.out.println("Queue Contents : " + q);
System.out.println("Head Element is " + q.peek());
System.out.println("Queue Contents : " + q);
The output is:
Queue Contents : [1]
Head Element is 1
Queue Contents : [1]
As seen element 1 still remains in the Queue.
Equivalent to offer and poll, there are two more methods add and remove. The difference is the way in which they handle boundary conditions. From the java docs:
The offer method inserts an element if possible, otherwise returning false. This 
differs from the Collection.add method, which can fail to add an element only by 
throwing an unchecked exception. The offer method is designed for use when failure 
is a normal, rather than exceptional occurrence, for example, in fixed-capacity 
(or bounded) queues. The remove() and poll() methods differ only in their behavior 
when the queue is empty: the remove() method throws an exception, while the poll() 
method returns null.
Similarly for peek we have the element method.
If we look at the code for LinkedList:
public class LinkedList<E> extends AbstractSequentialList<E> 
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
The class does not implement the Queue interface, instead it implements the Deque interface. A Deque or double ended queue, supports element insertion and removal at both ends.
Consider the below example code:
public static void main(final String[] args) {
      final Deque<Integer> deQ = new ArrayDeque<Integer>();
      deQ.offer(1);// insert at tail
      deQ.offerFirst(2);// insert at head
      deQ.offerLast(3);// insert at tail - normal FIFO behavior
      System.out.println("Queue Contents : " + deQ);

      deQ.poll();// remove from head
      System.out.println("Queue Contents (after poll) : " + deQ);
      deQ.pollLast();// remove from tail
      System.out.println("Queue Contents (after pollLast) : " + deQ);
      deQ.pollFirst();// remove from head -normalFIFO behavior
      System.out.println("Queue Contents (after pollFirst) : " + deQ);
   }
The output indicates the state of the Deque after performing insert and delete operations on both ends.
Queue Contents : [2, 1, 3]
Queue Contents (after poll) : [1, 3]
Queue Contents (after pollLast) : [1]
Queue Contents (after pollFirst) : []
Instead of the ArrayDeque we could also have written the below:
Deque<Integer> deQ = new LinkedList<Integer>();
ArrayDeque has a Resizable-array based implementation. The next in the Queue family is the priority queue. Java provided PriorityQueue is a min priority queue.
public static void main(final String[] args) {
      final Queue<Integer> priorityQ = new PriorityQueue<Integer>();
      priorityQ.offer(100);
      System.out.println("Queue Contents : " + priorityQ);
      priorityQ.offer(12);
      System.out.println("Queue Contents : " + priorityQ);
      priorityQ.offer(323);

      System.out.println("Queue Contents : " + priorityQ);
      priorityQ.poll();
      System.out.println("Queue Contents (after poll) : " + priorityQ);
      priorityQ.poll();
      System.out.println("Queue Contents (after poll) : " + priorityQ);
      priorityQ.poll();
      System.out.println("Queue Contents (after poll) : " + priorityQ);
   }
The output of the code is as below:
Queue Contents : [100]
Queue Contents : [12, 100]
Queue Contents : [12, 100, 323]
Queue Contents (after poll) : [100, 323]
Queue Contents (after poll) : [323]
Queue Contents (after poll) : []
As seen the items are not inserted at the tail. Instead the element with minimum priority is always at the head of the queue. The remove method will always remove from the head. But after a removal the head element will again point to the element with minimum priority.
This Queue has been implemented in java as a min heap. If we want a max heap simply provided a reverse comparator. As comparison is required, ensure that any object implements comparable or has a custom comparator.

No comments:

Post a Comment