Java Queue Structure, Features and Examples

In this tutorial, we will learn Queue data structure, Java Queue Interface, its core methods, and practical examples. We will also see various implementation classes for Queue Interface and the use cases for all of these. We will also focus on how to use queues in a multi-threaded environment by making it Thread safe.

1. What is a Queue?

Queue is a linear data structure that stores elements in FIFO (First In, First Out) order. The Queue has two ends, front & rear. The elements are added at the rear and removed from the front.

• Front or Head: the index from where the elements are removed/processed from the queue.
• Rear or Tail: the index from where new elements are added in the queue.

If we want to represent a group of individual objects queued for processing, then Queue is the best choice. Let’s take an example to understand this more clearly,

An email service has to send emails to the configured email-ids of the candidates. The requirement is to send the emails in the order in which they are added to the service. So for this requirement, we can use Queue data structure to maintain all the email-ids which helps us in adding new emails at the end (rear) and pick new emails from the start (front) to send the emails in the same order in which they are added to the queue.

Some of the important characteristics of Queue are as follows:

• We can access both ends of the queue i.e. a queue is open at both ends.
• Queues are fast and flexible to use.
• The operation of adding an element to the rear end of the queue is called Enqueue.
• The operation of removing an element from the front end of the queue is called Dequeue.
• We can use Queues to represent real-life situations like handling website traffic, routers and switches in networking & handling hardware processes or real-time system interrupts.

2. Java Queue Interface

Queue Interface in Java works in a similar way as we discussed the Queue data structure. Let’s explore Java Queue Interface in detail.

2.1. Class Hierarchy

Queue Interface present in java.util package and is the child interface of Collection Interface and has been there since Java version 1.5.

Since Queue is an interface, it can’t be instantiated, and hence there are multiple implementation classes that implement Queue Interface like LinkedList, PriorityQueue, ArrayDeque, etc.

2.2. Core Methods

Along with Collection Interface methods, Queue Interface defines some more methods as well that we can use while working with queues in java. Let’s look at some of the important methods present in Queue Interface,

• boolean offer(Object): To add an object into the Queue.
• Object peek(): To return head element of the Queue. If queue is empty then this method returns null.
• Object element(): To return head element of the Queue. If queue is empty then this method throws NoSuchElementException.
• Object poll(): To remove and return head element of the Queue. If queue is empty then this method return null.
• Object remove(): To remove and return head element of the Queue. If queue is empty then this method throws NoSuchElementException.

3. Different Types of Queues

Some implementation classes that implement Queue Interface directly are LinkedList, PriorityQueue, and ArrayDeque. Also, there are some interfaces that extend the Queue Interface like Deque, BlockingQueue, TransferQueue, etc.

Let’s now look at some of these sub-interfaces and the implementation classes of Queue Interface in detail along with practical use-case and examples.

3.1. BlockingQueue

A BlockingQueue is like another Queue implementation with additional capabilities. It is a concurrent queue that manages the queue operations concurrently. Added in Java version 1.5 and is part of java.util.concurrent package.

public interface BlockingQueue<E> extends Queue<E>

BlockingQueue interface introduces blocking in case it is full or empty. Thus, BlockingQueue is excellent when we want to skip the complexity involved in wait–notify statements and can be used to solve the popular producer-consumer problem.

• When a Thread tries to insert elements in the already full queue, then the Thread blocks until some other Thread creates some space in the queue by removing elements from the queue.
• Similarly, in the case of dequeuing, the operation blocks if the queue is empty until a Thread inserts an element in the queue.

Some of the important features of BlockingQueue are as follows:

• BlockingQueue does not accept null values. If we try to insert a null value then it throws NullPointerException.
• All the methods of BlockingQueue are atomic in nature and use internal locks or other forms of concurrency control internally.
• ArrayBlockingQueue & LinkedBlockingQueue are the implementation classes of BlockingQueue Interface.

Types of BlockingQueue:

• Bounded Queue: In the bounded queue, the capacity of the queue is passed to the constructor of the queue. ArrayBlockingQueue implementation of BlockingQueue is an example of Bounded queue.

BlockingQueue<String> blockingQueue = new ArrayBlockingQueue<>(5);

• Unbounded Queue: In the unbounded queue, we don’t set the capacity of the queue explicitly, and it can grow in size. The capacity sets to Integer.MAX_VALUE. LinkedBlockingQueue implementation of BlockingQueue is an example of an Unbounded queue.

BlockingQueue<String> blockingQueue = new LinkedBlockingDeque<>();

Let’s now look at an example of how to use BlockingQueue.

// create object of ArrayBlockingQueue
 BlockingQueue<String> queue = new ArrayBlockingQueue<String>(5);

 // Add elements to ArrayBlockingQueue using put method
 queue.put("Delhi");
 queue.put("Mumbai");
 queue.put("Pune");
 queue.put("Goa");
 queue.put("Kerala");

 // print Queue
 System.out.println("queue contains " + queue);  // queue contains [Delhi, Mumbai, Pune, Goa, Kerala]

// remove some elements
queue.remove();
queue.remove();

// Again print Queue
System.out.println("queue contains " + queue);  // queue contains [Pune, Goa, Kerala]

3.2. TransferQueue

TransferQueue is a concurrent blocking queue implementation in which producers may wait for the receipt of messages by consumers. Added in Java version 1.7 and is part of java.util.concurrent package.

public interface TransferQueue<E> extends BlockingQueue<E>

We can use TransferQueue in message-passing applications in which producers sometimes (use method transfer()) await receipt of elements by consumers invoking take or poll, while at other times enqueue elements (via method put()) without waiting for receipt.

Some of the important features of TransferQueue are as follows:

• TransferQueue doesn’t allow null values. If we try to insert a null value then it throws NullPointerException.
• All the methods of the TransferQueue are Thread-safe.
• LinkedTransferQueue is one of the implementation class for the TransferQueue Interface.

Let’s now look at an example of using TransferQueue,

// Initializing the queue
TransferQueue<Integer> queue = new LinkedTransferQueue<Integer>();

// Adding elements to this queue
for (int i = 1; i <= 5; i++){
      queue.add(i);
}

// Print queue
System.out.println("queue contains " + queue);        // queue contains [1, 2, 3, 4, 5]

// remove some elements
queue.remove(1);
queue.remove(5);

// Again Print queue
System.out.println("queue contains " + queue);      // queue contains [2, 3, 4]

3.3. Deque

Deque is a double-ended queue where we can add or remove the elements from the queue at both ends. It uses as a Queue and follows FIFO (First In, First Out) order or as a Stack and follows LIFO (Last In, First Out). Added in Java version 1.6 and is part of java.util package.

public interface Deque<E> extends Queue<E> 

We can use Deque as both Stack and Queue, so it is helpful in use cases like maintaining a web browser’s history, to maintain a list of undo operations in an application, Job scheduling algorithms, etc.

Some of the important features of Deque are as follows:

• We can use a doubly LinkedList to implement Deque.
• It is not Thread-safe and not suitable to use in multi-threaded applications.
• It won’t allow null values, and throws NullPointerException.
• ArrayDeque is one of the implementation class of Deque Interface.

Let’s now look at an example of using Deque,

// Creating ArrayDeque Object
Deque<Integer> deque = new ArrayDeque<>();

// Add at last
deque.add(1);
// Add at first
deque.addFirst(3);
// Add at last
deque.addLast(2);

// Remove at first
deque.removeFirst();
deque.forEach(a -> System.out.print(a + " -> "));         // 1 -> 2

3.4. PriorityQueue

Usually, the elements in a Queue follows FIFO order, but sometimes we need to process the elements of the queue based on the priority and that’s when Priority Queue comes into play. Added in Java version 1.5 and is part of java.util package.

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

The PriorityQueue is based on the priority heap. The elements of the priority queue are ordered based on the default natural sorting order, or customized sorting order defined by a Comparator provided at the time of queue creation.

We can use PriorityQueue in Artificial Intelligence(A* Search algorithm), in Heap Sort implemented using Heap, in Prim’s algorithm, and in data compression techniques as well.

Some of the important features of PriorityQueue are as follows:

• We can’t insert a null value in PriorityQueue. If we try to insert a null value, then it throws NullPointerException.
• Duplicate elements are not allowed in PriorityQueue.
• PriorityQueue is not thread-safe. We can use PriorityBlockingQueue for thread-safe operations instead.
• If we insert the elements based on the default natural sorting order then we can add only homogeneous and comparable elements in the PriorityQueue, otherwise, it will throw ClassCastException.
• If we insert the elements based on Comparator’s customized sorting then the elements need not be homogeneous or comparable.

Let’s now look at an example on using PriorityQueue,

// Creating PriorityQueue Object
PriorityQueue<Integer> queue = new PriorityQueue<>();

// Adding elements
for(int i=1;i<5;i++){
    queue.offer(i);
}

System.out.println(queue);               // [1,2,3,4]
System.out.println(queue.poll());       // 1
System.out.println(queue);                // [2,3,4]

4. Thread Safe Queues

A major drawback with most of the Queue implementations like PriorityQueue, LinkedList is that they are not thread-safe making it difficult to work with queues in a multi-threaded application. While the shareability of Queues makes them great for multi-threaded processes, multiple threads attempting to perform read operations on a single queue may cause resource contention and reduced write speeds.

Java offers classes like ConcurrentLinkedQueue, ArrayBlockingQueue, and ConcurrentLinkedDeque which are thread-safe and perfect for multi-threaded programs. Creating a single writer thread with a BlockingQueue can alleviate this issue and lead to vastly improved write speeds.

By implementing a blocking queue, write operations wait until the queue has available space while read operations wait for a non-empty queue before attempting element retrieval or removal.

Therefore, Queue interface supports safe multithreading while enforcing memory efficiency, making it ideal for many business cases that demand optimized data structures and related processes.

5. Conclusion

We have learned about Queue data structure along with Java Queue Interface, the class hierarchy and its core methods of it. We have also seen various implementation classes and sub-interfaces of Queue interface and their practical use cases, along with their main features and examples of how to use them in our code.

Happy Learning !!