The Queue interface in Java is a part of the java.util package and extends the Collection interface.
It represents a collection designed for holding elements prior to processing, typically in a FIFO (First-In-First-Out) manner.
The Queue interface provides methods to add, remove, and inspect elements, offering variations of these operations to handle both normal and exceptional conditions.
In this tutorial, we'll cover:
Basic operations of the Queue interface.
Implementations of Queue (such as LinkedList and PriorityQueue).
Code examples demonstrating common queue operations.
Queue Interface Overview
Common Methods in the Queue Interface
add(E e): Inserts the specified element into the queue. Throws an exception if the operation fails (e.g., capacity limits).
offer(E e): Inserts the specified element into the queue. Returns false if the operation fails instead of throwing an exception.
remove(): Retrieves and removes the head of the queue. Throws an exception if the queue is empty.
poll(): Retrieves and removes the head of the queue. Returns null if the queue is empty.
element(): Retrieves, but does not remove, the head of the queue. Throws an exception if the queue is empty.
peek(): Retrieves, but does not remove, the head of the queue. Returns null if the queue is empty.
1. Using a Queue with LinkedList
The LinkedList class implements the Queue interface, allowing you to use it as a queue. Let's look at some examples.
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
// Creating a Queue using LinkedList
Queue queue = new LinkedList<>();
// Adding elements using add() and offer()
queue.add("Alice");
queue.offer("Bob");
queue.offer("Charlie");
System.out.println("Queue: " + queue); // [Alice, Bob, Charlie]
// Accessing the head element using element() and peek()
System.out.println("Head (element): " + queue.element()); // Alice
System.out.println("Head (peek): " + queue.peek()); // Alice
// Removing elements using remove() and poll()
System.out.println("Removed (remove): " + queue.remove()); // Alice
System.out.println("Queue after remove: " + queue); // [Bob, Charlie]
System.out.println("Removed (poll): " + queue.poll()); // Bob
System.out.println("Queue after poll: " + queue); // [Charlie]
// Poll on empty queue returns null
queue.poll(); // Charlie is removed
System.out.println("Empty queue poll: " + queue.poll()); // null
// Element on empty queue throws exception
// System.out.println(queue.element()); // Throws NoSuchElementException
}
}
Explanation:
add() and offer() both insert elements into the queue. The difference is that add() throws an exception if the queue is full, whereas offer() returns false.
remove() and poll() both remove the head element. The difference is that remove() throws an exception if the queue is empty, while poll() returns null.
element() and peek() both return the head element without removing it. element() throws an exception if the queue is empty, while peek() returns null.
2. Using a Queue with PriorityQueue
The PriorityQueue class is another implementation of the Queue interface that orders elements according to their natural ordering or by a Comparator provided at queue construction time. Let's explore how it works.
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueExample {
public static void main(String[] args) {
// Creating a PriorityQueue of integers
Queue priorityQueue = new PriorityQueue<>();
// Adding elements using add() and offer()
priorityQueue.add(15);
priorityQueue.offer(10);
priorityQueue.offer(30);
priorityQueue.offer(25);
System.out.println("PriorityQueue: " + priorityQueue); // [10, 15, 30, 25]
// Accessing the head element using element() and peek()
System.out.println("Head (element): " + priorityQueue.element()); // 10
System.out.println("Head (peek): " + priorityQueue.peek()); // 10
// Removing elements using remove() and poll()
System.out.println("Removed (remove): " + priorityQueue.remove()); // 10
System.out.println("PriorityQueue after remove: " + priorityQueue); // [15, 25, 30]
System.out.println("Removed (poll): " + priorityQueue.poll()); // 15
System.out.println("PriorityQueue after poll: " + priorityQueue); // [25, 30]
}
}
Explanation:
The PriorityQueue orders its elements based on their natural ordering (Comparable) or a custom Comparator.
In this case, smaller numbers have higher priority, so the element 10 is at the head of the queue.
The queue is not necessarily sorted when printed, but the smallest element is always at the head of the queue.
3. Example of Using a PriorityQueue with Custom Comparator
You can also provide a custom comparator to change the order in which elements are processed in a PriorityQueue.
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class CustomPriorityQueueExample {
public static void main(String[] args) {
// Creating a PriorityQueue with a custom comparator for reverse order
Queue priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());
// Adding elements
priorityQueue.offer(15);
priorityQueue.offer(10);
priorityQueue.offer(30);
priorityQueue.offer(25);
System.out.println("PriorityQueue: " + priorityQueue); // [30, 25, 15, 10]
// Accessing the head element (which now has the largest value due to reverse order)
System.out.println("Head (peek): " + priorityQueue.peek()); // 30
// Removing elements
System.out.println("Removed: " + priorityQueue.poll()); // 30
System.out.println("PriorityQueue after poll: " + priorityQueue); // [25, 10, 15]
}
}
Explanation:
We pass a custom comparator (Comparator.reverseOrder()) to the PriorityQueue constructor to create a max-heap. Now, the largest element is always at the head of the queue.
4. Blocking Queues (e.g., LinkedBlockingQueue)
Java also provides blocking queues, which are useful in multithreaded environments. A BlockingQueue blocks a thread trying to add() elements if the queue is full, and it blocks a thread trying to remove() elements if the queue is empty.
Here’s an example of using LinkedBlockingQueue:
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
public class BlockingQueueExample {
public static void main(String[] args) throws InterruptedException {
// Creating a LinkedBlockingQueue
BlockingQueue blockingQueue = new LinkedBlockingQueue<>(3);
// Adding elements
blockingQueue.put("Alice");
blockingQueue.put("Bob");
blockingQueue.put("Charlie");
System.out.println("BlockingQueue: " + blockingQueue); // [Alice, Bob, Charlie]
// Adding one more element will block until there's space
new Thread(() -> {
try {
blockingQueue.put("David");
System.out.println("David added to the queue.");
} catch (InterruptedException e) {
e.printStackTrace();
}
}).start();
// Simulate processing and removing an element
Thread.sleep(1000);
System.out.println("Removed: " + blockingQueue.take()); // Alice
System.out.println("BlockingQueue after take: " + blockingQueue); // [Bob, Charlie]
}
}
Explanation:
LinkedBlockingQueue is an implementation of a blocking queue with a fixed capacity.
The put() method blocks when the queue is full, and the take() method blocks when the queue is empty.
5. Deque Interface (Double-Ended Queue)
The Deque interface extends Queue and allows you to insert and remove elements from both ends of the queue. A common implementation is ArrayDeque.
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeExample {
public static void main(String[] args) {
// Creating a Deque using ArrayDeque
Deque deque = new ArrayDeque<>();
// Adding elements at both ends
deque.addFirst("Alice");
deque.addLast("Bob");
deque.offerFirst("Charlie");
deque.offerLast("David");
System.out.println("Deque: " + deque); // [Charlie, Alice, Bob, David]
// Accessing elements from both ends
System.out.println("First element: " + deque.getFirst()); // Charlie
System.out.println("Last element: " + deque.getLast()); // David
// Removing elements from both ends
System.out.println("Removed first: " + deque.removeFirst()); // Charlie
System.out.println("Removed last: " + deque.removeLast()); // David
System.out.println("Deque after removals: " + deque); // [Alice, Bob]
}
}
Explanation:
addFirst() and addLast(): Add elements to the front or end of the deque.
removeFirst() and removeLast(): Remove elements from the front or end of the deque.
Deque can act as both a stack (LIFO) or a queue (FIFO) depending on how you use the methods.
Conclusion
In this tutorial, we explored the Queue interface in Java and its common implementations:
LinkedList: Used as a queue in FIFO order.
PriorityQueue: Orders elements based on natural ordering or a custom comparator.
BlockingQueue: Useful in multithreading to handle blocking when adding or removing elements.
Deque: A double-ended queue allowing insertions and removals from both ends.
The Queue interface is a powerful tool for managing collections in a specific order, and its variations allow for great flexibility in a variety of use cases.