Queue Interface

The Queue interface in Java represents a First-In-First-Out (FIFO) data structure.
It is part of the Java Collections Framework and is used to hold elements before processing.

📦 Package: java.util
🔑 Element inserted first is removed first (like a line at a ticket counter).

---

✅ Key Features:

Feature	Behavior
Ordering	FIFO – First-In-First-Out
Nulls	❌ Usually not allowed (e.g., ArrayDeque, PriorityQueue)
Thread-safe	❌ Not by default (use ConcurrentLinkedQueue or BlockingQueue variants)
Usage	Task scheduling, message queues, buffers, etc.

🔧 Important Methods in Queue:

Method	Description
add(E e)	Inserts element (throws exception on failure)
offer(E e)	Inserts element (returns false on failure)
remove()	Retrieves & removes head (throws exception if empty)
poll()	Retrieves & removes head (returns null if empty)
element()	Retrieves (but doesn’t remove) head (exception if empty)
peek()	Retrieves (but doesn’t remove) head (returns null if empty)

🧰 Common Implementations of Queue:

Implementation	Characteristics
LinkedList	Can be used as Queue (non-thread-safe)
PriorityQueue	Elements ordered by natural/comparator order
ArrayDeque	Faster than LinkedList, no nulls allowed
ConcurrentLinkedQueue	Thread-safe non-blocking queue
ArrayBlockingQueue	Bounded, thread-safe, used in concurrent scenarios
LinkedBlockingQueue	Thread-safe, optionally bounded

🔍 Example Using Queue:

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        queue.offer("A");
        queue.offer("B");
        queue.offer("C");

        System.out.println(queue.poll()); // A
        System.out.println(queue.peek()); // B (doesn’t remove)
    }
}

🧠 Summary:

Feature	Queue Interface
Ordering	FIFO
Use-case	Scheduling, messaging, buffering
Null handling	Usually not allowed
Common types	PriorityQueue, ArrayDeque, LinkedList
Thread-safe variants	ConcurrentLinkedQueue, BlockingQueue

 

PriorityQueue?

A PriorityQueue in Java is a queue that stores elements in priority order instead of FIFO.

🎯 Elements with higher priority are served first, not necessarily in the order they were added.

It is part of the Java Collections Framework and implements the Queue interface.

---

✅ Key Features:

Feature	Behavior
Ordering	✅ Sorted by natural order or custom comparator
Null elements	❌ Not allowed
Duplicates	✅ Allowed
Thread-safe	❌ Not synchronized
Underlying structure	Min-Heap (by default: smallest element = highest priority)
Type	Unbounded, but backing array resizes dynamically

🔧 Constructor Variants:

Constructor	Description
new PriorityQueue<>()	Uses natural ordering
new PriorityQueue<>(Comparator)	Custom ordering logic
new PriorityQueue<>(Collection)	Creates from another collection

🔍 Example (Natural Order – Min Heap):

import java.util.PriorityQueue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(30);
        pq.add(10);
        pq.add(20);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 10, 20, 30
        }
    }
}

🔀 Example (Custom Order – Max Heap):

---

⚠️ Important Notes:

• Time complexity: O(log n) for add() and poll().
• Iterator does not guarantee sorted order.
• Best for scheduling, job processing, and simulations.

---

🧠 Summary:

Feature	PriorityQueue
Order	Sorted by priority (default: min-heap)
Nulls	❌ Not allowed
Duplicates	✅ Allowed
Performance	O(log n) for insert/remove
Use-case	Job scheduling, task management

 

🔄  ArrayDeque?

ArrayDeque (short for Array Double Ended Queue) is a resizable-array implementation of the Deque interface.
It allows you to add or remove elements from both ends – making it suitable for queue (FIFO) and stack (LIFO) operations.

📦 Package: java.util
🔧 Faster than Stack and LinkedList for stack/queue operations.

---

✅ Key Features:

Feature	Behavior
Doubly-ended	✅ Add/remove from both front & rear
Null elements	❌ Not allowed (NullPointerException)
Thread-safe	❌ Not synchronized
Backing structure	Resizable circular array
Performance	⚡ Faster than Stack and LinkedList
Type	Non-blocking, non-thread-safe

🔧 Common Methods:

Method	Description
addFirst(e)	Inserts element at the front
addLast(e)	Inserts element at the end
removeFirst()	Removes and returns front element
removeLast()	Removes and returns last element
peekFirst()	Returns front without removing
peekLast()	Returns last without removing
offerFirst(e)	Adds to front (returns false on failure)
offerLast(e)	Adds to end (returns false on failure)

🧪 Example (As Queue – FIFO):

---

🧪 Example (As Stack – LIFO):

---

🧠 Summary:

Feature	ArrayDeque
Ordering	FIFO (queue) or LIFO (stack)
Null support	❌ No
Performance	⚡ Fast for both ends
Thread safety	❌ No
Backing structure	Resizable array
Common uses	Stack, Queue, Deque

 

🔄 ConcurrentLinkedQueue?

ConcurrentLinkedQueue is a thread-safe, non-blocking, FIFO (First-In-First-Out) queue based on a lock-free linked node structure.

✅ It belongs to the java.util.concurrent package and is ideal for high-performance concurrent environments.

---

✅ Key Features:

Feature	Behavior
Thread-safe	✅ Yes – lock-free algorithm using CAS (Compare-And-Swap)
Ordering	✅ FIFO (insertion order)
Blocking?	❌ No – it is non-blocking
Null allowed?	❌ No – NullPointerException on adding null
Performance	⚡ Excellent for frequent concurrent read/write
Backed by	Singly linked list of nodes

🧰 Common Methods:

Method	Description
offer(E e)	Adds an element to the tail
poll()	Removes and returns the head (or null if empty)
peek()	Returns head without removing (or null)
isEmpty()	Checks if the queue is empty
size()	Returns estimated size (not guaranteed exact)

🔍 Example:

---

🧠 Internal Working:

• Each node contains item and reference to next node.
• CAS (Compare-And-Swap) is used to manage node linking without locks.
• Allows multiple threads to safely add/remove elements simultaneously.

---

🚫 Limitations:

• ❌ Not blocking → not suitable if you need threads to wait for data (use BlockingQueue for that).
• ❌ size() is not reliable in concurrent scenarios (returns an estimate).

---

📌 Use Cases:

• Producer-consumer scenarios with non-blocking needs
• High-concurrency systems (e.g., web servers, task schedulers)
• Alternatives to synchronized or Collections.synchronizedQueue

---

✅ Summary:

Feature	ConcurrentLinkedQueue
Type	Non-blocking, thread-safe FIFO Queue
Null allowed?	❌ No
Locking mechanism	Lock-free (CAS-based)
Backing structure	Singly linked list
Use case	High-performance concurrent apps

 

📦 ArrayBlockingQueue?

ArrayBlockingQueue is a bounded, thread-safe, blocking queue backed by an array.

✅ It is part of java.util.concurrent and is used for producer-consumer scenarios where threads must wait (block) when the queue is full or empty.

---

✅ Key Features:

Feature	Description
Thread-safe	✅ Yes – uses internal locks
Blocking	✅ Yes – blocks on full (for put()), or empty (for take())
Bounded	✅ Yes – fixed capacity specified at construction
Nulls allowed?	❌ No – throws NullPointerException
Ordering	✅ FIFO (First-In-First-Out)
Backed by	Array (circular buffer internally)

🔧 Constructor:

You can also provide fairness (optional):

---

🧰 Common Methods:

Method	Description
put(E e)	Inserts element; blocks if full
take()	Retrieves & removes head; blocks if empty
offer(E e)	Inserts element; returns false if full
poll()	Retrieves and removes head; returns null if empty
peek()	Retrieves but doesn't remove head
remainingCapacity()	Returns space left in queue

🔍 Example:

import java.util.concurrent.ArrayBlockingQueue;

public class ArrayBlockingQueueDemo {
    public static void main(String[] args) throws InterruptedException {
        ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<>(3);

        queue.put("A");
        queue.put("B");
        queue.put("C");

        System.out.println(queue.take()); // A
        System.out.println(queue.peek()); // B
    }
}

🧠 When to Use?

• When you need a fixed-size, blocking queue
• In producer-consumer problems
• When thread coordination is needed (one thread waits until space/data is available)

---

⚖️ Comparison with Other Queues:

Feature	ArrayBlockingQueue	LinkedBlockingQueue	ConcurrentLinkedQueue
Thread-safe	✅ Yes	✅ Yes	✅ Yes
Blocking	✅ Yes	✅ Yes	❌ No
Bounded	✅ Yes	Optional	❌ Unbounded
Backing structure	Array	Linked list	Linked list
Fair ordering option	✅ Optional	✅ Optional	❌

✅ Summary:

Property	Value
Type	Bounded, blocking, thread-safe
Ordering	FIFO
Blocking behavior	On full (put), on empty (take)
Use case	Producer-consumer problems
Null support	❌ Not allowed

 

🔄 LinkedBlockingQueue?

LinkedBlockingQueue is a thread-safe, optionally bounded, blocking queue based on a linked list.

✅ Ideal for producer-consumer scenarios, especially when you want higher throughput and flexible size control.

---

✅ Key Features:

Feature	Description
Thread-safe	✅ Yes – uses separate locks for put and take
Blocking	✅ Yes – threads block on put() if full, or take() if empty
Bounded?	✅ Optional (default = Integer.MAX_VALUE)
Ordering	✅ FIFO (First-In-First-Out)
Nulls allowed?	❌ No – throws NullPointerException
Backed by	Linked nodes (not an array)

🧰 Constructor Options:

// Unbounded (max size = Integer.MAX_VALUE)
LinkedBlockingQueue<String> queue = new LinkedBlockingQueue<>();

// Bounded
LinkedBlockingQueue<String> queue = new LinkedBlockingQueue<>(100); // max 100 elements

---

🔧 Common Methods:

Method	Description
put(E e)	Inserts element; blocks if queue is full
take()	Retrieves and removes head; blocks if queue is empty
offer(E e)	Inserts if possible; returns false if full
poll()	Retrieves and removes head; returns null if empty
peek()	Returns head without removing it
remainingCapacity()	Returns number of remaining slots

🔍 Example:

import java.util.concurrent.*;

public class LinkedBlockingQueueDemo {
    public static void main(String[] args) throws InterruptedException {
        LinkedBlockingQueue<String> queue = new LinkedBlockingQueue<>(3);

        queue.put("A");
        queue.put("B");
        queue.put("C");

        System.out.println(queue.take()); // A
        System.out.println(queue.peek()); // B
    }
}

---

⚙️ Internal Architecture:

• Uses a linked list of nodes to store elements.
• Maintains two separate locks (one for producers, one for consumers) for better performance in concurrent access.
• Avoids global lock like ArrayBlockingQueue, improving throughput.

---

🧠 When to Use?

• For high-concurrency producer-consumer scenarios
• When you want optional size limitation
• When blocking behavior is required and performance is a concern

---

🔁 Comparison with Other Blocking Queues:

Feature	LinkedBlockingQueue	ArrayBlockingQueue	SynchronousQueue
Backing structure	Linked list	Array	No storage (handoff)
Bounded	Optional	Required	Always 0 capacity
Blocking	✅ Yes	✅ Yes	✅ Yes
Thread separation	✅ Producer/Consumer	❌ Single lock	✅ Direct thread transfer

✅ Summary:

Property	Value
Type	Blocking, optionally bounded queue
Order	FIFO
Thread-safe	✅ Yes
Null support	❌ Not allowed
Use case	High-throughput producer-consumer