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 Queue?
1.1. The Queue Data Structure
Queue is a linear data structure that stores elements in FIFO (First In, First Out) order. The element that is added first to the queue will be the first one to be removed.
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.
1.2. When to use a Queue?
The queues are used in scenarios where the order of processing or handling is critical and follows the principle of “first come, first served”. 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
The Queue interface is part of the Java collections framework and provides the functionality of the queue data structure. Let’s explore the Java Queue interface in detail.
Queue Interface present in java.util package and is the child interface of Collection Interface and has been there since Java version 1.5.
public interface Queue<E> extends Collection<E> {
//...
}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.
There are few interfaces that extend the Queue interface and provide the extended functionalities:
- Deque
- BlockingQueue
- BlockingDeque
3. Common Operations on Queues
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.
3.1. Add an Element
When we add an element, it is added to the rear of the queue. Queue interface provides the following two methods for adding new elements:
- boolean add(e): inserts the specified element into the queue. It returns true if the operation is successful, else throws an exception.
- boolean offer(e): inserts the specified element into the queue. It returns true if the operation is successful, else false.
Queue<String> messageQueue = new LinkedList<>();
messageQueue.add("message-1");
messageQueue.offer("message-2");3.2. Enquire an Element
We can enquire about the next element from the queue without removing it from the queue. The following methods help in examining the head element:
- E element(): retrieves, but does not remove, the head of this queue, or throws NoSuchElementException if this queue is empty.
- E peek(): retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
System.out.println( messageQueue.element() ); // "message-1"
System.out.println( messageQueue.peek() ); // "message-1"3.3. Remove an Element
When we want to retrieve the element for processing such that it is removed from the queue, we can use the following methods:
- E poll(): To remove and return the head element of the Queue. If the queue is empty, then this method returns null.
- E remove(): To remove and return the head element of the Queue. If the queue is empty then this method throws NoSuchElementException.
System.out.println( messageQueue.poll() ); // "message-1"
System.out.println( messageQueue.remove() ); // "message-2"
System.out.println( messageQueue.remove() ); // Exception in thread "main" java.util.NoSuchElementExceptionDifferent Types of Queues in Java
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.
4. BlockingQueue
A BlockingQueue is like the Queue implementation with additional capabilities. A BlockingQueue is a concurrent queue that manages the queue operations concurrently. It was added in Java version 1.5 and is part of java.util.concurrent package.
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.
4.1. The Blocking Nature
Note that BlockingQueue introduces the blocks the add or remove operations 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 will be blocked until some other thread creates some space in the queue by removing elements from the queue.
- Similarly, in the case of removing the elements, the operation blocks if the queue is empty until another thread inserts an element in the queue.
4.2. Types of BlockingQueue
Generally, blocking queues are of two categories:
- 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 a 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<>();4.3. An Example using ArrayBlockingQueue
In the following example, we are using ArrayBlockingQueue which is a bounded blocking queue backed by an array.
Once created, its capacity cannot be changed. An attempt to put an element into a full queue results in the operation blocking. Similarly, an attempt to take an element from an empty queue will also block.
In the following program, the producer thread adds 5 items to the queue, but the size of the queue is 2 so it needs to wait for the consumer thread to remove a few items.
ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<>(2);
// Producer Thread adding 5 items
Thread producerThread = new Thread(() -> {
for (int i = 1; i <= 5; i++) {
try {
queue.put(i);
System.out.println("Producer added: " + i);
} catch (InterruptedException e) {
System.out.println("Producer Thread interrupted.");
}
}
});
// Consumer Thread
Thread consumerThread = new Thread(() -> {
for (int i = 1; i <= 5; i++) {
try {
Thread.sleep(200);
int element = queue.take();
System.out.println("Consumer removed: " + element);
} catch (InterruptedException e) {
System.out.println("Consumer Thread interrupted.");
}
}
});
producerThread.start();
consumerThread.start();Program output. Note that the print statements can appear in different order for each run, but the concept remains same.
Producer added: 1
Producer added: 2
Producer added: 3
Consumer removed: 1
Consumer removed: 2
Producer added: 4
Consumer removed: 3
Producer added: 5
Consumer removed: 4
Consumer removed: 55. 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>5.1. Features of TransferQueue
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.
5.2. Example of TransferQueue
Let’s now look at an example of TransferQueue using LinkedTransferQueue class.
The producer thread uses the transfer() method to add elements to the queue, which performs a direct handoff to a waiting consumer (if any). If no consumer is ready to receive, the producer will block until a consumer is available to take the element.
The consumer thread uses the take() method to remove elements from the queue, which blocks if the queue is empty. In this case, the consumer will wait for a producer to transfer an element.
Both threads operate asynchronously, with the producer transferring elements and the consumer receiving them in the same order.
LinkedTransferQueue<Integer> transferQueue = new LinkedTransferQueue<>();
// Producer Thread
Thread producerThread1 = new Thread(() -> {
for (int i = 1; i <= 5; i++) {
try {
System.out.println("Producer is transferring: " + i);
transferQueue.transfer(i);
System.out.println("Producer transferred: " + i);
} catch (InterruptedException e) {
System.out.println("Producer Thread interrupted.");
}
}
});
// Consumer Thread
Thread consumerThread1 = new Thread(() -> {
for (int i = 1; i <= 5; i++) {
try {
System.out.println("Consumer is waiting to receive...");
int element = transferQueue.take();
System.out.println("Consumer received: " + element);
} catch (InterruptedException e) {
System.out.println("Consumer Thread interrupted.");
}
}
});
producerThread1.start();
consumerThread1.start();The program output may print the statements in random order in each run.
Consumer is waiting to receive...
Producer is transferring: 1
Producer transferred: 1
Consumer received: 1
Consumer is waiting to receive...
Producer is transferring: 2
Producer transferred: 2
Producer is transferring: 3
Consumer received: 2
Consumer is waiting to receive...
Consumer received: 3
Consumer is waiting to receive...
Producer transferred: 3
Producer is transferring: 4
Producer transferred: 4
Consumer received: 4
Consumer is waiting to receive...
Producer is transferring: 5
Producer transferred: 5
Consumer received: 56. Deque
Deque is a double-ended queue where we can add or remove 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.
6.1. Features of Deque
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 classes of the Deque Interface.
6.2. Deque Example
Let’s now look at an example of using Deque,
Deque<Integer> deque = new ArrayDeque<>();
// Adding elements to the front of the Deque
deque.offerFirst(10);
deque.offerFirst(20);
deque.offerFirst(30);
// Adding elements to the back of the Deque
deque.offerLast(40);
deque.offerLast(50);
System.out.println("Deque elements: " + deque); // [30, 20, 10, 40, 50]
// Peeking elements at both ends of the Deque
System.out.println("Peek First (Front): " + deque.peekFirst()); // 30
System.out.println("Peek Last (Back): " + deque.peekLast()); // 50
// Removing elements from both ends of the Deque
System.out.println("Popped First (Front): " + deque.pollFirst()); // 30
System.out.println("Popped Last (Back): " + deque.pollLast()); // 50
System.out.println("Deque elements: " + deque); // [20, 10, 40]7. PriorityQueue
Usually, the elements in a Queue follow 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 SerializableThe 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.
7.1. PriorityQueue Features
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.
7.2. PriorityQueue Example
Let’s now look at an example of using PriorityQueue. We have a Task record type with a field priority. The number value of priority represents the priority of the task in the queue. A bigger number means a bigger priority.
record Task(long id, String name, int priority) implements Comparable<Task> {
@Override
public int compareTo(Task other) {
return Integer.compare(other.priority, this.priority);
}
}When we add tasks with random priorities in the queue, they are removed from the queue based on higher priority orders.
PriorityQueue<Task> priorityQueue = new PriorityQueue<>();
priorityQueue.add(new Task(10001, "Task 1", 5));
priorityQueue.add(new Task(10002, "Task 2", 1));
priorityQueue.add(new Task(10003, "Task 3", 10));
System.out.println(priorityQueue);
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}The program output:
Task[id=10003, name=Task 3, priority=10]
Task[id=10001, name=Task 1, priority=5]
Task[id=10002, name=Task 2, priority=1]8. Thread Safety
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.
9. 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 !!
Comments