Topic 38 of 78
Queue
Overview
A Queue is a linear data structure that operates on the FIFO principle: First In, First Out. Think of a line at a grocery store; the first person who gets in line is the first person served. Queues are essential for scheduling algorithms, breadth-first search (BFS), and managing asynchronous tasks where fairness (processing in the exact order received) is required.
Syntax
Using a Linked List makes building a Queue trivial and dynamic, as you can instantly add to the tail and remove from the head.
Queue using a Linked List
java
public class LinkedQueue {
private Node head; // Dequeue from here (Front of line)
private Node tail; // Enqueue from here (Back of line)
// O(1) Enqueue (Add to back)
public void enqueue(int data) {
Node newNode = new Node(data);
if (tail == null) {
head = tail = newNode;
return;
}
tail.next = newNode;
tail = newNode;
}
// O(1) Dequeue (Remove from front)
public int dequeue() {
if (head == null) throw new NoSuchElementException();
int data = head.data;
head = head.next;
if (head == null) tail = null; // List became empty
return data;
}
}Common Pitfalls
- Using `ArrayList` as a queue base. Every `dequeue` shifts the entire array, ruining performance.
- Not handling the case where both `head` and `tail` need to be set to `null` when the last element is removed.
Interview Tips
- Queues follow the FIFO (First In, First Out) principle, used for task scheduling and Breadth-First Search (BFS).
Real-World Example
Message Brokers (like RabbitMQ or Kafka) and Thread Pools use Queues to hold incoming requests until a worker thread is ready to process them.
example
java
public class PrintSpooler {
// Java provides Thread-Safe queues for backend systems!
private Queue<String> printJobs = new ConcurrentLinkedQueue<>();
public void addJob(String document) {
printJobs.offer(document);
}
public void processNextJob() {
String doc = printJobs.poll(); // Retrieves and removes head
if (doc != null) {
System.out.println("Printing: " + doc);
}
}
}