dcsimg
May 28, 2017
Hot Topics:

Exploring the Queue Interface in Java

  • March 13, 2017
  • By Manoj Debnath
  • Send Email »
  • More Articles »

The collection library of Java provides classes and interfaces to hold elements according to a specified norm prior to processing. The behavior is defined by the characteristic of the data structure it implements. These classes are built in a manner to hold generic elements; this means it can hold elements of any but the same consecutive type designated at the time of declaration of the collection object. The Queue interface, along with its many variations, is one of them. This article delineates the working concept along with a tinge of API classes working behind the scenes in the Java Collection API library.

Overview

A queue, in its basic sense, is a linear collection of elements that follows a specific store and retrieval behavior called FIFO, or First-in and First-out. This means that the order of store and retrieval of elements in a queue is such that, elements which are stored first are the ones to be retrieved first. This ordering principle can very easily be understood analogically by people standing in a queue to get, say, a bus ticket. The person standing first takes the ticket and gets out of the queue first, whereas the person standing last in the line is the last to be out.

Queuing up
Figure 1: Queuing up

Now, you may have been pondering what their uses may be, especially in computer system. Here are a few of them.

  • Imagine a computer having a single processor. It, therefore, can service only one application at a time. Each application requiring processor time is placed in a queue. The application at the front of the queue get the first chance to be serviced.
  • Queues are also used in print spooling, where print jobs are submitted in a queue. As a result, although more than one print job is submitted, the printer picks up the most recent one from the queue.
  • In a network router, information packets wait in a queue. Each time a packet arrives at a node, it must be routed to the next node along the path until final destination is reached. The routing node routes one packet at a time. As a result, additional nodes are queued up until it can be routed.

This FIFO idea illustrates the predictive ability of the queue in general. This ordering principle is very similar to the LinkedList class that implements the List interface. If we create a queue, slightly altering its behavior to LIFO (Last-in, First-out), it becomes a stack. Apart from this, there are many variations to it, such as priority queues, where elements are ordered according to the natural ordering of the elements or according to a supplied comparator. There, it can be said that a queue typically behaves in a FIFO manner, but not necessarily so.

The Queue Interface

The Queue interface in the Java API library is an extension of the Collection interface. Therefore, it has all the capabilities of a collection and additionally provides operations such as inserting, removing, and inspecting elements in a queue.

The PriorityQueue class is one of the concrete implementations of the Queue interface and is also one of the most commonly used. It orders elements according to the natural ordering of the elements, as specified by Comparable's compareTo() method. We also can supply a Comparator object through the PriorityQueue constructor during its creation. This class provides the facility to insert data according to the underlying data sorted manner. But, any deletion of data occurs from the front as per the behavior of a queue. Adding elements in the PriorityQueue occurs in a priority order such as the highest priority element signified by the supplied value. While removing elements, however, it is the first element that is removed. Inserting any null elements throws ClassCastException. Also, due to its association with Comparator, any value that is not comparable is not allowed in this queue.

The initial size of the PriorityQueue can be provided during its construction but, by default, it is unbounded, in the sense that its capacity grows automatically as elements are inserted; whether we supply the initial capacity or not does not matter.

The most common PriorityQueue operations are as follows:

  • boolean offer(E e): Inserts anelement at the appropriate location depending on the priority order.
  • E poll(): Removes the highest priority element, posited it in the front of the queue.
  • E peek(): Gets a reference to the highest priority element in the queue, but does not remove it.
  • void clear(): Removes all elements from the queue.
  • int size(): Gives the number of elements in the queue, or queue size.

The problem with PriorityQueue is that it is not synchronized; therefore, is it not recommended to be used for access with multiple threads. Java, however, provides another class, called PriorityBlockingQueue, which is synchronized.

A very rudimentary example to illustrate how PriorityQueue works is as follows.

package org.mano.example;

import java.util.PriorityQueue;

public class TestPriorityQueue {

   public static void main(String[] args){
      PriorityQueue<Integer> q=new PriorityQueue<>();
      q.offer(12);
      q.offer(99);
      q.offer(10);
      q.offer(7);
      System.out.println("Polling...");
      while(q.size()>0){
         System.out.println(q.peek());
         q.poll();
      }
   }
}

The PriorityBlockingQueue

The PriorityBlockingQueue class is not a subclass of PriorityQueue, but supplies the same set of functions, including a few additional ones derived from BlockingQueue. This class has blocking retrieval operation imposed by its implementation of the BlockingQueue interface. This means that the blocking effect causes the calling thread to be blocked if the queue is empty. The thread remains blocked until at least one element is added to the queue. Due to this, though, the queue is logically unbounded; an attempt to insert may fail, causing OutOfMemoryError.

The ArrayBlockingQueue

The name provides the clue: The ArrayBlockingQueue uses an array to maintain its elements. The idea that singles out this class from other queue implementations is that, here we are required to provide the capacity of the array during its creation. Also, unlike other queues, this capacity cannot be exceeded once declared. That means, if a thread attempts to add an element to a already full queue, it's blocked until an element is removed to make room for the new one. Due to this inherent thread safety feature, it is defined in the java.util.concurrent package.

The LinkedBlockingQueue

Another queue class, called the LinkedBlockingQueue, acts in a slightly different manner. Firstly, it is implemented as a linked list. Secondly, it can behave in both a bounded and unbounded fashion. It acts bounded, like ArrayBlockingQueue, if capacity is provided during its creation. And, if capacity is not provided at the time of creation, it becomes unbounded. This class is also thread safe, defined in the java.util.concurrent package.

The ConcurrentLinkedQueue

The ConcurrentLinkedQueue is also a thread-safe queue defined in the java.util.concurrent package. The main difference with other queues is that there is no blocking factor associated with the instance of this class.

The SynchronousQueue

The SynchronousQueue is a complete blocking queue in the sense that it blocks all attempts to add an element into the queue unless it also receives a request to retrieve an element from the queue and vice versa. This queue is different from other queue implementations and do not seem very queue-like. It is particularly suitable in a situation where we require a two-way transfer from one thread to another in a synchronized manner. As should be obvious, it is thread safe and is defined in the java.util.concurrent package.

The DelayQueue

The DelayQueue is another interesting queue implementation that allows an element object to be inserted that implements the Delayed interface. Inserted elements are ordered on the basis of the amount of time remaining before it can be removed from the queue. This denotes the expiry time when elements can be removed. The expiry time can be retrieved by the getDelay() method, which returns a value less than or equal to zero. However, the poll() method can be used to remove unexpired elements, but those are treated as normal elements and not of a delayed kind.

A Quick Example

package org.mano.example;

import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;

public class DelayedDemo implements Delayed {

   private String name;
   private long delay;

   public DelayedDemo(String name, long delay) {
      super();
      this.name = name;
      this.delay = delay;
   }

   public String getName() {
      return name;
   }

   @Override
   public int compareTo(Delayed o) {
      return (int)(delay - o.getDelay(TimeUnit.SECONDS));
   }

   @Override
   public long getDelay(TimeUnit unit) {
      return TimeUnit.SECONDS.convert(delay, unit);
   }

   public static void main(String[] args) {
      DelayQueue<DelayedDemo> queue = new DelayQueue<>();
      DelayedDemo d= new DelayedDemo("Wake up in 30 seconds", 30);
      queue.add(d);
      d = new DelayedDemo("Wake up in 40 seconds", 40);
      queue.add(d);
   }
}

Conclusion

The queue classes are some of the many facilities provided by the Java API library. The variety it offers may not be exhaustive, yet it fills an important corner of programming needs. Another important queue class is called Deque, which we have not covered here. It represents a double-ended queue where insertion and retrieval is possible at both ends of the queue.


Tags: Java, array, Queue, Java Collection API Library, FIFO, LIFO




Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

Sitemap | Contact Us

Thanks for your registration, follow us on our social networks to keep up-to-date
Rocket Fuel