Queue Interface
The Queue interface is an integral part of the Java Collections Framework, extending the Collection interface. It serves as a representation of a collection of elements that follow a specific order for processing, adhering to the "first-in, first-out" (FIFO) principle. Duplicate values are allowed in a Queue. The fundamental characteristic of a Queue is that elements are stored in a specific order, similar to a line of people waiting their turn, and you can access and manipulate elements primarily through operations such as adding elements to the end (enqueue) and removing elements from the front (dequeue). It is particularly useful for scenarios where you need to manage elements in a sequential manner, such as task scheduling or processing items in a predictable order.
Common Implementations of Queue
LinkedList:
Java's
LinkedListclass can be used to implement a Queue, it also implements List interface. It provides a doubly-linked list implementation, which is well-suited for implementing a basic FIFO queue.Ordered Collection: It maintains the order of elements and allows duplicates, just like any other
Listimplementation.Indexed Access: You can access elements by their index, making it possible to retrieve, modify, or remove elements efficiently.
List-Specific Methods: It provides all the methods specified by the
Listinterface, includingadd,get,set,remove,indexOf, and more. These methods operate in a manner consistent with the characteristics of a linked list.Synchronization: Not synchronized by default (not thread-safe).
Queue Characteristics: It follows the FIFO (First-In-First-Out) principle for enqueue (addition) and dequeue (removal) operations.
Deque Characteristics: It supports both stack-like behaviour (LIFO - Last-In-First-Out) and queue-like behaviour, providing methods like
offer,poll,peek,push,pop, and more.Queue-Specific Methods: It provides all the methods specified by the
Queueinterface, includingoffer,poll,peek, andelement.import java.util.LinkedList; public class Test { public static void main(String[] args) { // Create a LinkedList LinkedList<String> linkedList = new LinkedList<>(); // Adding elements to the list linkedList.add("Apple"); // Add at the end linkedList.add("Banana"); linkedList.add("Cherry"); linkedList.add("Date"); // Display the list System.out.println("Original LinkedList: " + linkedList); // Queue methods: offer, poll, peek linkedList.offer("Elderberry"); // Add to the end (enqueue) String removedItem = linkedList.poll(); // Remove from the front (dequeue) String frontItem = linkedList.peek(); // Peek at the front System.out.println("After offer, poll, and peek: " + linkedList); System.out.println("Removed item: " + removedItem); System.out.println("Front item: " + frontItem); // Stack methods: push, pop linkedList.push("Fig"); // Add to the front (push) String poppedItem = linkedList.pop(); // Remove from the front (pop) System.out.println("After push and pop: " + linkedList); System.out.println("Popped item: " + poppedItem); // List methods: add, get, set, remove, indexOf linkedList.add(2, "Grape"); // Insert at a specific index String getItem = linkedList.get(3); // Get element at index 3 linkedList.set(1, "Blueberry"); // Set element at index 1 linkedList.remove(4); // Remove element at index 4 int index = linkedList.indexOf("Cherry"); // Find the index of "Cherry" System.out.println("After list operations: " + linkedList); System.out.println("Get item at index 3: " + getItem); System.out.println("Index of 'Cherry': " + index); } }
By extending
ListandQueue, aLinkedListin Java combines the features of these interfaces with the underlying linked list data structure, providing flexibility and efficiency for various use cases. Depending on your needs, you can choose the appropriate interface to use with yourLinkedList.
ArrayDeque:
Java's
ArrayDequeclass provides a double-ended queue implementation, which can also be used as a Queue. It offers constant-time (amortized) operations for adding or removing elements from both ends.ArrayDequeinternally uses a dynamic array to store elements, which can grow or shrink in size as needed.Double-Ended: It supports adding and removing elements from both the front and rear of the deque. This makes it suitable for various use cases, including implementing stacks and queues.
Constant-Time Operations: Most common operations such as adding or removing elements from the front or rear of the deque have constant-time complexity on average, making it efficient for dynamic data manipulation.
Random Access: Unlike linked lists,
ArrayDequeprovides constant-time random access to elements using indices.ArrayDequeallows null elements, meaning you can storenullvalues in the deque.ArrayDequedoes not have a fixed capacity. It dynamically resizes its internal array as needed to accommodate additional elements.ArrayDequeis a versatile data structure suitable for implementing various data manipulation tasks such as:Implementing both stacks (LIFO) and queues (FIFO).
Maintaining a sliding window of elements efficiently.
Storing and managing elements where fast insertion and removal at both ends are required.
Methods:
addFirst(E e)andaddLast(E e): Add elements to the front and rear of the deque, respectively.offerFirst(E e)andofferLast(E e): Similar toaddFirstandaddLast, but return a boolean indicating success.removeFirst()andremoveLast(): Remove and return elements from the front and rear of the deque, respectively.pollFirst()andpollLast(): Similar toremoveFirstandremoveLast, but returnnullif the deque is empty.getFirst()andgetLast(): Get the first and last elements of the deque without removing them.peekFirst()andpeekLast(): Similar togetFirstandgetLast, but returnnullif the deque is empty.size(): Returns the number of elements in the deque.isEmpty(): Returnstrueif the deque is empty.clear(): Removes all elements from the deque.
ArrayDequeis not thread-safe for concurrent access by multiple threads. If thread safety is required, consider usingjava.util.concurrentclasses likeConcurrentLinkedDeque.import java.util.ArrayDeque; import java.util.Deque; public class Test { public static void main(String[] args) { // Create an ArrayDeque Deque<String> deque = new ArrayDeque<>(); // Add elements to the front and rear of the deque deque.addFirst("A"); // Adds "A" to the front deque.addLast("B"); // Adds "B" to the rear // Offer elements to the front and rear with a return value boolean offeredFront = deque.offerFirst("C"); // Adds "C" to the front boolean offeredRear = deque.offerLast("D"); // Adds "D" to the rear System.out.println("After adding elements: " + deque); System.out.println("Offered to front: " + offeredFront); System.out.println("Offered to rear: " + offeredRear); // Remove elements from the front and rear of the deque String removedFront = deque.removeFirst(); // Removes and returns "C" from the front String removedRear = deque.removeLast(); // Removes and returns "D" from the rear System.out.println("Removed from front: " + removedFront); System.out.println("Removed from rear: " + removedRear); System.out.println("After removals: " + deque); // Poll elements from the front and rear with possible null return String polledFront = deque.pollFirst(); // Polls and returns "A" from the front String polledRear = deque.pollLast(); // Polls and returns "B" from the rear System.out.println("Polled from front: " + polledFront); System.out.println("Polled from rear: " + polledRear); System.out.println("After polls: " + deque); deque.addFirst("A"); // Adds "A" to the front deque.addLast("B"); // Adds "B" to the rear // Get elements from the front and rear without removal String frontElement = deque.getFirst(); // Retrieves, but does not remove, the front element String rearElement = deque.getLast(); // Retrieves, but does not remove, the rear element System.out.println("Front element: " + frontElement); System.out.println("Rear element: " + rearElement); System.out.println("Deque after retrieval: " + deque); // Check if the deque is empty boolean isEmpty = deque.isEmpty(); // Returns false because there are elements in the deque System.out.println("Is the deque empty? " + isEmpty); // Clear the deque deque.clear(); // Removes all elements from the deque System.out.println("After clearing the deque: " + deque); // Check if the deque is empty isEmpty = deque.isEmpty(); // Returns false because there are elements in the deque System.out.println("Is the deque empty? " + isEmpty); } }
PiorityQueue:
PriorityQueueis an implementation of a priority queue data structure.Elements in a
PriorityQueueare ordered based on their natural ordering (if elements are comparable) or by a specified comparator.The element with the highest priority is dequeued first.
Elements can be added to a PriorityQueue using the
add()oroffer()methods.To remove and retrieve the highest-priority element, you can use the
poll()method. Thepoll()method removes and returns the element with the highest priority. If the PriorityQueue is empty, it returnsnull.To retrieve the highest-priority element without removing it, use the
peek()method. Thepeek()method returns the element with the highest priority without removing it. If the PriorityQueue is empty, it returnsnull.You can specify a custom comparator to order elements in the PriorityQueue. For example, to create a PriorityQueue that orders elements in descending order.
You can iterate over the elements of a PriorityQueue using an enhanced for loop or by converting it to an array.
To check if the PriorityQueue is empty, use the
isEmpty()method.Inserting an element into a PriorityQueue takes O(log n) time.
Retrieving the highest-priority element (using
poll()orpeek()) takes O(1) time.PriorityQueue is not thread-safe by default. If you need a thread-safe priority queue, consider using
PriorityBlockingQueuefrom thejava.util.concurrentpackage.
PriorityQueue is a versatile data structure that can be used in various scenarios where you need to prioritize and process elements based on their priority order. It is particularly useful in algorithms like Dijkstra's shortest path algorithm and A* search algorithm.
import java.util.*;
public class PriorityQueueExample {
public static void main(String[] args) {
// 1. Declaration and Initialization
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 2. Adding Elements
priorityQueue.add(5);
priorityQueue.offer(10);
priorityQueue.add(2);
// 3. Removing Elements
int highestPriority = priorityQueue.poll();
System.out.println("Removed element with highest priority: " + highestPriority);
// 4. Peeking
int peekedElement = priorityQueue.peek();
System.out.println("Peeked element with highest priority: " + peekedElement);
// 5. Custom Comparator (Descending Order)
PriorityQueue<Integer> descendingQueue = new PriorityQueue<>(Collections.reverseOrder());
descendingQueue.addAll(Arrays.asList(5, 10, 2));
System.out.println("Elements in descending order:");
while (!descendingQueue.isEmpty()) {
System.out.println(descendingQueue.poll());
}
// 6. Initial Capacity and Custom Comparator (Descending Order)
PriorityQueue<Integer> customQueue = new PriorityQueue<>(10, Comparator.reverseOrder());
customQueue.addAll(Arrays.asList(5, 10, 2));
System.out.println("Elements in custom descending order:");
while (!customQueue.isEmpty()) {
System.out.println(customQueue.poll());
}
// 7. Iterating Over Elements
priorityQueue.addAll(Arrays.asList(5, 10, 2));
System.out.println("Iterating over elements:");
for (int element : priorityQueue) {
System.out.println(element);
}
// 8. Size and Empty Check
int size = priorityQueue.size();
System.out.println("Size of the PriorityQueue: " + size);
boolean isEmpty = priorityQueue.isEmpty();
System.out.println("Is the PriorityQueue empty? " + isEmpty);
}
}
This is all about the Queue interface, in the next blog we will learn about implementations of the Map Interface.
My Other Blogs: