Java Queue

Master the First In First Out (FIFO) data structure - just like waiting in line at a ticket counter, first person in line gets served first!

What is Queue?

Queue is a First In First Out (FIFO) data structure in Java from the java.util package. It's an interface that represents a collection designed for holding elements before processing. Think of it like a line of people waiting at a cinema - the first person who joins the queue is the first one to get a ticket!

Queue is implemented by several classes including LinkedList, PriorityQueue, and ArrayDeque. It's perfect for scenarios like task scheduling, print queue, and breadth-first search algorithms.

  • FIFO Principle: First element added is the first one removed
  • Offer Operation: Add elements to the rear of the queue
  • Poll Operation: Remove and return the front element
  • Peek Operation: View the front element without removing it
  • No Random Access: Elements are accessed only from the front

💡 Real-World Analogy: Queue is like a line at a restaurant, printer queue, or customer service helpline - whoever arrives first gets served first!

Creating and Using Queue

Here's how to create a Queue using LinkedList and perform basic operations:

Example: Queue Basic Operations

import java.util.Queue;
import java.util.LinkedList;

public class QueueExample {
    public static void main(String[] args) {
        // Creating a Queue using LinkedList
        Queue customers = new LinkedList<>();
        
        // Check if queue is empty
        System.out.println("Is queue empty? " + customers.isEmpty());
        
        // Offer - adding elements to queue
        customers.offer("Alice");
        customers.offer("Bob");
        customers.offer("Charlie");
        customers.offer("Diana");
        
        System.out.println("Queue: " + customers);
        
        // Peek - view front element without removing
        System.out.println("Front customer: " + customers.peek());
        System.out.println("Queue after peek: " + customers);
        
        // Poll - remove and return front element
        String served = customers.poll();
        System.out.println("Served: " + served);
        System.out.println("Queue after poll: " + customers);
        
        // Element - retrieves but does not remove front
        System.out.println("Next to be served: " + customers.element());
        
        // Size of queue
        System.out.println("Customers waiting: " + customers.size());
        
        // Serve all customers
        System.out.println("\nServing all customers:");
        while (!customers.isEmpty()) {
            System.out.println("Serving: " + customers.poll());
        }
    }
}
Output: 
Is queue empty? true
Queue: [Alice, Bob, Charlie, Diana]
Front customer: Alice
Queue after peek: [Alice, Bob, Charlie, Diana]
Served: Alice
Queue after poll: [Bob, Charlie, Diana]
Next to be served: Bob
Customers waiting: 3

Serving all customers:
Serving: Bob
Serving: Charlie
Serving: Diana

Explanation:

  • offer(element) - Adds element to the rear of queue, returns true if successful
  • poll() - Removes and returns front element, returns null if empty
  • peek() - Returns front element without removing, returns null if empty
  • element() - Returns front element, throws exception if empty
  • isEmpty() - Checks if queue has any elements
  • size() - Returns the number of elements in the queue

Queue Methods Overview

1. Adding Elements

Insert elements at the rear of the queue.

Methods: offer(element) - Returns false if fails, add(element) - Throws exception if fails

2. Removing Elements

Remove the front element from the queue.

Methods: poll() - Returns null if empty, remove() - Throws exception if empty

3. Examining Elements

Look at the front element without removing it.

Methods: peek() - Returns null if empty, element() - Throws exception if empty

4. Utility Operations

Check queue status and iterate through elements.

Methods: isEmpty(), size(), clear(), contains(element)

Practical Example: Print Queue

Let's simulate a printer queue where documents are printed in the order they were submitted:

Example: Printer Queue System

import java.util.Queue;
import java.util.LinkedList;

public class PrinterQueue {
    
    public static void main(String[] args) {
        Queue printQueue = new LinkedList<>();
        
        System.out.println("=== Printer Queue System ===\n");
        
        // Adding documents to print queue
        System.out.println("Adding documents to queue:");
        addDocument(printQueue, "Report.pdf");
        addDocument(printQueue, "Invoice.docx");
        addDocument(printQueue, "Presentation.pptx");
        addDocument(printQueue, "Letter.pdf");
        
        System.out.println("\nCurrent queue: " + printQueue);
        System.out.println("Documents in queue: " + printQueue.size());
        
        // Processing print queue
        System.out.println("\n--- Starting Print Job ---");
        processQueue(printQueue);
        
        System.out.println("\n✓ All documents printed!");
        System.out.println("Queue is now empty: " + printQueue.isEmpty());
    }
    
    static void addDocument(Queue queue, String document) {
        queue.offer(document);
        System.out.println("Added: " + document);
    }
    
    static void processQueue(Queue queue) {
        int jobNumber = 1;
        
        while (!queue.isEmpty()) {
            String document = queue.poll();
            System.out.println("Job " + jobNumber + ": Printing " + 
                             document + "...");
            
            // Simulate printing time
            try {
                Thread.sleep(500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            
            System.out.println("        ✓ " + document + " printed");
            jobNumber++;
        }
    }
}
Output: 
=== Printer Queue System ===

Adding documents to queue:
Added: Report.pdf
Added: Invoice.docx
Added: Presentation.pptx
Added: Letter.pdf

Current queue: [Report.pdf, Invoice.docx, Presentation.pptx, Letter.pdf]
Documents in queue: 4

--- Starting Print Job ---
Job 1: Printing Report.pdf...
        ✓ Report.pdf printed
Job 2: Printing Invoice.docx...
        ✓ Invoice.docx printed
Job 3: Printing Presentation.pptx...
        ✓ Presentation.pptx printed
Job 4: Printing Letter.pdf...
        ✓ Letter.pdf printed

✓ All documents printed!
Queue is now empty: true

Explanation:

  • Documents are added to the queue in the order they're submitted
  • Printer processes documents in FIFO order
  • First document submitted is the first one printed
  • Perfect for managing tasks that need sequential processing

Breadth-First Search (BFS) Application

Queue is essential for BFS algorithm - exploring level by level:

Example: Level Order Traversal

import java.util.Queue;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;

public class BFSExample {
    
    public static void main(String[] args) {
        // Creating a simple graph using HashMap
        HashMap> graph = new HashMap<>();
        
        graph.put("A", List.of("B", "C"));
        graph.put("B", List.of("A", "D", "E"));
        graph.put("C", List.of("A", "F"));
        graph.put("D", List.of("B"));
        graph.put("E", List.of("B", "F"));
        graph.put("F", List.of("C", "E"));
        
        System.out.println("BFS Traversal starting from 'A':");
        bfs(graph, "A");
    }
    
    static void bfs(HashMap> graph, String start) {
        Queue queue = new LinkedList<>();
        HashSet visited = new HashSet<>();
        
        queue.offer(start);
        visited.add(start);
        
        System.out.println("\nVisit Order:");
        int level = 1;
        
        while (!queue.isEmpty()) {
            String node = queue.poll();
            System.out.println("Level " + level + ": Visiting " + node);
            
            // Add all unvisited neighbors to queue
            for (String neighbor : graph.get(node)) {
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
            level++;
        }
    }
}
Output: 
BFS Traversal starting from 'A':

Visit Order:
Level 1: Visiting A
Level 2: Visiting B
Level 3: Visiting C
Level 4: Visiting D
Level 5: Visiting E
Level 6: Visiting F

Explanation:

  • Queue ensures level-by-level exploration of the graph
  • Each node's neighbors are added to the queue for later processing
  • FIFO nature guarantees visiting nodes in breadth-first order
  • Used in shortest path algorithms and social network analysis

Queue Implementations

Queue is an interface that can be implemented by different classes:

Common Queue Implementations

Implementation       Description                           Best For
─────────────────────────────────────────────────────────────────────────────
LinkedList           Doubly-linked list                 General purpose queue
ArrayDeque           Resizable array (faster)           High-performance queue
PriorityQueue        Heap-based (ordered by priority)   Priority-based ordering

⚡ Performance Tip: Use ArrayDeque for better performance than LinkedList. Use PriorityQueue when elements need to be processed based on priority rather than insertion order.

Queue vs Stack

Understanding the key differences between Queue and Stack:

Comparison Table

Feature              Queue (FIFO)            Stack (LIFO)
───────────────────────────────────────────────────────────────────
Principle            First In First Out       Last In First Out
Insertion            At rear (offer)          At top (push)
Removal              From front (poll)        From top (pop)
Access               Front only               Top only
Real-world           Line/Queue               Stack of plates
Use cases            Task scheduling          Undo functionality
                     BFS algorithm            DFS algorithm
                     Print queue              Expression evaluation

🎯 When to Use Queue: Choose Queue when you need to process items in the order they arrive: task scheduling, breadth-first search, handling requests, buffering, message queues.