The Queue interface is present in java.util package and extends the Collection interface . It is used to hold the elements about to be processed in FIFO(First In First Out) order. Queues typically order elements in a FIFO (First-In-First-Out) manner, where elements are added at the end and removed from the beginning.
Elements are processed in the order they are added. The element added first is the first one to be removed.
Use-Cases: Queues are useful for managing tasks where the order of execution is critical. Algorithms like BFS (Breadth-First-Search) use queues to explore nodes layer by layer.
Common Methods
boolean add(E e): Adds the specified element to the queue. Throws an exception if the operation fails.
boolean offer(E e): Adds the specified element to the queue. Returns true if successful, false otherwise.
E remove(): Removes and returns the head of the queue. Throws an exception if the queue is empty.
E poll(): Removes and returns the head of the queue. Returns null if the queue is empty.
E element(): Retrieves, but does not remove, the head of the queue. Throws an exception if the queue is empty.
E peek(): Retrieves, but does not remove, the head of the queue. Returns null if the queue is empty.
int size(): Returns the number of elements in the queue.
boolean isEmpty(): Returns true if the queue is empty, false otherwise.
void clear(): Removes all elements from the queue.
Iterator<E> iterator(): Returns an iterator over the elements in the queue.
boolean contains(Object o): Returns true if the queue contains the specified element.
boolean remove(Object o): Removes the first occurrence of the specified element from the queue.
boolean removeAll(Collection<?> c): Removes all elements in the queue that are also in the specified collection.
Implementation Classes
- LinkedList: Implemented as a doubly-linked list. Supports both FIFO (First-In-First-Out) and LIFO (Last-In-First-Out) operations. Dynamic in size, allowing for efficient insertion and deletion at both ends. Offers O(1) time complexity for enqueue (add) and dequeue (remove) operations at both ends. Suitable for applications where flexibility in adding or removing elements from both ends is required. Maintains elements in the order they were added.
- ArrayDeque: Implemented as a resizable array. Supports dynamic resizing, allowing efficient insertion and deletion from both ends (front and back). Provides O(1) time complexity for enqueue (add) and dequeue (remove) operations at both ends. Maintains elements in the order they were added, allowing efficient insertion and removal from both ends.
- PriorityQueue: Implemented as a priority heap. Elements are ordered either by their natural ordering (if they implement Comparable) or by a Comparator provided at queue creation time. Supports priority-based ordering where elements with higher priority are dequeued first. Provides O(log n) time complexity for enqueue (add) and dequeue (remove) operations. Suitable for scenarios where elements need to be processed based on priority rather than insertion order.
LinkedList
Implemented as a doubly-linked list where each element is stored as a separate object called a “node.” Each node contains data and two references (or links) to the next and previous nodes in the sequence. LinkedList can be used as a Queue by adding elements at the end (enqueue operation) and removing elements from the beginning (dequeue operation).
import java.util.LinkedList;
import java.util.Queue;
// Custom class for using as an element in Queue
class Customer {
private String name;
private int id;
public Customer(String name, int id) {
this.name = name;
this.id = id;
}
// Getters, setters, equals, and hashCode methods
public String getName() {
return name;
}
public int getId() {
return id;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Customer customer = (Customer) o;
return id == customer.id && name.equals(customer.name);
}
@Override
public int hashCode() {
return name.hashCode() + id;
}
@Override
public String toString() {
return "Customer{" +
"name='" + name + '\'' +
", id=" + id +
'}';
}
}
public class QueueExample {
public static void main(String[] args) {
// Creating a LinkedList to use as a Queue
Queue<Customer> queue = new LinkedList<>();
// Offer operations (adding elements)
queue.offer(new Customer("Alice", 1001));
queue.offer(new Customer("Bob", 1002));
queue.offer(new Customer("Charlie", 1003));
System.out.println("Queue after offer operations: " + queue);
// Peek operation (retrieves, but does not remove, the head of the queue)
Customer peekedCustomer = queue.peek();
if (peekedCustomer != null) {
System.out.println("Peeked customer: " + peekedCustomer);
}
System.out.println("Queue after peek: " + queue);
// Poll operation (removes and retrieves the head of the queue)
Customer polledCustomer = queue.poll();
if (polledCustomer != null) {
System.out.println("Polled customer: " + polledCustomer);
}
System.out.println("Queue after poll: " + queue);
// Adding more elements
queue.offer(new Customer("David", 1004));
queue.offer(new Customer("Eva", 1005));
System.out.println("Queue after adding more elements: " + queue);
// Removing all elements using poll until empty
while (!queue.isEmpty()) {
Customer removedCustomer = queue.poll();
System.out.println("Removed customer: " + removedCustomer);
}
System.out.println("Queue after removing all elements: " + queue);
}
}
ArrayDeque
Implemented as a resizable array. Provides dynamic resizing to accommodate varying numbers of elements efficiently. Supports both FIFO (First-In-First-Out) and LIFO (Last-In-First-Out) operations. Efficiently adds elements at the end and removes elements from the front for queue-like behavior.
Offers O(1) time complexity for enqueue (add) and dequeue (remove) operations at both ends. Efficient memory usage due to its array-based implementation and dynamic resizing.
import java.util.ArrayDeque;
import java.util.Queue;
// Custom class for using as an element in ArrayDeque
class Customer {
private String name;
private int id;
public Customer(String name, int id) {
this.name = name;
this.id = id;
}
// Getters, setters, equals, and hashCode methods
public String getName() {
return name;
}
public int getId() {
return id;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Customer customer = (Customer) o;
return id == customer.id && name.equals(customer.name);
}
@Override
public int hashCode() {
return name.hashCode() + id;
}
@Override
public String toString() {
return "Customer{" +
"name='" + name + '\'' +
", id=" + id +
'}';
}
}
public class ArrayDequeQueueExample {
public static void main(String[] args) {
// Creating an ArrayDeque to use as a Queue
Queue<Customer> queue = new ArrayDeque<>();
// Offer operations (adding elements)
queue.offer(new Customer("Alice", 1001));
queue.offer(new Customer("Bob", 1002));
queue.offer(new Customer("Charlie", 1003));
System.out.println("Queue after offer operations: " + queue);
// Peek operation (retrieves, but does not remove, the head of the queue)
Customer peekedCustomer = queue.peek();
if (peekedCustomer != null) {
System.out.println("Peeked customer: " + peekedCustomer);
}
System.out.println("Queue after peek: " + queue);
// Poll operation (removes and retrieves the head of the queue)
Customer polledCustomer = queue.poll();
if (polledCustomer != null) {
System.out.println("Polled customer: " + polledCustomer);
}
System.out.println("Queue after poll: " + queue);
// Adding more elements
queue.offer(new Customer("David", 1004));
queue.offer(new Customer("Eva", 1005));
System.out.println("Queue after adding more elements: " + queue);
// Removing all elements using poll until empty
while (!queue.isEmpty()) {
Customer removedCustomer = queue.poll();
System.out.println("Removed customer: " + removedCustomer);
}
System.out.println("Queue after removing all elements: " + queue);
}
}
PriorityQueue
Implemented as a priority heap. Elements are ordered either by their natural ordering (if they implement Comparable) or by a Comparator provided at queue creation time.
Supports insertion of elements with priority and removal of elements based on priority. Elements with higher priority are dequeued first (min heap or max heap depending on the ordering).
import java.util.PriorityQueue;
import java.util.Queue;
// Custom class for using as an element in PriorityQueue
class Customer implements Comparable<Customer> {
private String name;
private int id;
public Customer(String name, int id) {
this.name = name;
this.id = id;
}
// Getters, setters, equals, and hashCode methods
public String getName() {
return name;
}
public int getId() {
return id;
}
@Override
public int compareTo(Customer other) {
// Comparing customers based on their ID for priority
return Integer.compare(this.id, other.id);
}
@Override
public String toString() {
return "Customer{" +
"name='" + name + '\'' +
", id=" + id +
'}';
}
}
public class PriorityQueueExample {
public static void main(String[] args) {
// Creating a PriorityQueue to use as a Queue
Queue<Customer> queue = new PriorityQueue<>();
// Offer operations (adding elements with priority)
queue.offer(new Customer("Alice", 1001));
queue.offer(new Customer("Bob", 1002));
queue.offer(new Customer("Charlie", 1003));
System.out.println("Queue after offer operations: " + queue);
// Peek operation (retrieves, but does not remove, the head of the queue)
Customer peekedCustomer = queue.peek();
if (peekedCustomer != null) {
System.out.println("Peeked customer: " + peekedCustomer);
}
System.out.println("Queue after peek: " + queue);
// Poll operation (removes and retrieves the head of the queue)
Customer polledCustomer = queue.poll();
if (polledCustomer != null) {
System.out.println("Polled customer: " + polledCustomer);
}
System.out.println("Queue after poll: " + queue);
// Adding more elements
queue.offer(new Customer("David", 1004));
queue.offer(new Customer("Eva", 1005));
System.out.println("Queue after adding more elements: " + queue);
// Removing all elements using poll until empty
while (!queue.isEmpty()) {
Customer removedCustomer = queue.poll();
System.out.println("Removed customer: " + removedCustomer);
}
System.out.println("Queue after removing all elements: " + queue);
}
}