Queues in Java for Competitive Programming

Queues are fundamental data structures in computer science, following the First-In, First-Out (FIFO) principle. In competitive programming, queues are invaluable for solving a wide range of problems, especially those involving breadth-first search (BFS), simulation, and task scheduling.

Implementing Queues in Java

Java provides a built-in java.util.Queue interface, making it straightforward to implement and use queues. This interface extends the Collection interface and provides methods for adding, removing, and inspecting elements in a queue.

Using the java.util.Queue Interface

The Queue interface defines essential methods for queue operations:

• offer(element): Adds an element to the tail of the queue. Returns true if successful, false if the queue is full (for capacity-restricted queues).
• poll(): Removes and returns the element at the head of the queue. Returns null if the queue is empty.
• peek(): Returns the element at the head of the queue without removing it. Returns null if the queue is empty.
• remove(): Removes and returns the element at the head of the queue. Throws a NoSuchElementException if the queue is empty.
• element(): Returns the element at the head of the queue without removing it. Throws a NoSuchElementException if the queue is empty.
• add(element): Adds an element to the tail of the queue. Throws an IllegalStateException if the queue is full.

Common Queue Implementations in Java

Several classes implement the Queue interface, each with its own characteristics and performance trade-offs. Two commonly used implementations are:

• java.util.LinkedList: A versatile implementation based on a doubly-linked list. It's generally a good choice for general-purpose queue operations.
• java.util.PriorityQueue: A priority queue that orders elements based on their natural ordering or a provided Comparator. It's useful for scenarios where elements need to be processed in a specific order based on priority.

Exploring Various Ways to Implement Queues

1. Using LinkedList

LinkedList is a popular choice for implementing queues because it offers efficient insertion and removal at both ends. It is generally preferred over ArrayDeque when thread-safety is not a primary concern, and it needs to be extended.

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

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

        queue.offer(10);
        queue.offer(20);
        queue.offer(30);

        System.out.println("Queue: " + queue); // Output: Queue: [10, 20, 30]
        System.out.println("Poll: " + queue.poll());  // Output: Poll: 10
        System.out.println("Queue after poll: " + queue); // Output: Queue after poll: [20, 30]
        System.out.println("Peek: " + queue.peek()); // Output: Peek: 20
    }
} 

2. Using PriorityQueue

PriorityQueue implements a min-heap data structure. Elements are ordered based on their natural ordering or a custom Comparator. It's suitable for scenarios where you need to retrieve the smallest (or largest, depending on the comparator) element efficiently.

 import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Comparator;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // Natural ordering (min-heap)
        Queue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(30);
        minHeap.offer(10);
        minHeap.offer(20);

        System.out.println("Min Heap: " + minHeap); // Unpredictable order for direct printing, elements are extracted correctly though
        System.out.println("Poll (Min): " + minHeap.poll()); // Output: Poll (Min): 10
        System.out.println("Poll (Min): " + minHeap.poll()); // Output: Poll (Min): 20
        System.out.println("Poll (Min): " + minHeap.poll()); // Output: Poll (Min): 30


        // Custom Comparator (max-heap)
        Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.offer(30);
        maxHeap.offer(10);
        maxHeap.offer(20);

        System.out.println("Max Heap: " + maxHeap); // Unpredictable order for direct printing, elements are extracted correctly though
        System.out.println("Poll (Max): " + maxHeap.poll()); // Output: Poll (Max): 30
        System.out.println("Poll (Max): " + maxHeap.poll()); // Output: Poll (Max): 20
        System.out.println("Poll (Max): " + maxHeap.poll()); // Output: Poll (Max): 10
    }
} 

Queues in Competitive Programming: Examples and Solutions

Example 1: Breadth-First Search (BFS)

BFS is a graph traversal algorithm that uses a queue to explore nodes level by level. This is useful to find the shortest path in an unweighted graph.

Problem: Given a graph represented as an adjacency list, find the shortest path from a starting node to a target node.

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

public class BFSExample {
    static class Graph {
        int vertices;
        ArrayList<ArrayList<Integer>> adj;

        Graph(int vertices) {
            this.vertices = vertices;
            adj = new ArrayList<ArrayList<Integer>>(vertices);
            for (int i = 0; i < vertices; i++) {
                adj.add(new ArrayList<Integer>());
            }
        }

        void addEdge(int u, int v) {
            adj.get(u).add(v);
            adj.get(v).add(u);  // Assuming an undirected graph
        }
    }


    public static int bfs(Graph graph, int start, int target) {
        boolean[] visited = new boolean[graph.vertices];
        int[] distance = new int[graph.vertices]; // Store the distance from the start node

        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        distance[start] = 0; // Distance from start to itself is 0
        queue.offer(start);

        while (!queue.isEmpty()) {
            int u = queue.poll();

            if (u == target) {
                return distance[target];
            }

            for (int v : graph.adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    distance[v] = distance[u] + 1;  // Update the distance
                    queue.offer(v);
                }
            }
        }

        return -1; // Target not reachable
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 5);
        graph.addEdge(4, 5);

        int startNode = 0;
        int targetNode = 5;
        int shortestDistance = bfs(graph, startNode, targetNode);

        if (shortestDistance != -1) {
            System.out.println("Shortest distance from " + startNode + " to " + targetNode + " is: " + shortestDistance); // Output: Shortest distance from 0 to 5 is: 2
        } else {
            System.out.println("Target node is not reachable from the start node.");
        }
    }
} 

Example 2: Simulation with Priority Queue

Imagine you need to simulate a hospital emergency room where patients are treated based on the severity of their condition. A priority queue efficiently keeps track of patients and allows you to select the highest-priority one for treatment.

Problem: Simulate an emergency room scenario where patients are assigned priorities (1 being the highest). Process patients based on priority until the queue is empty.

 import java.util.PriorityQueue;
import java.util.Comparator;

public class EmergencyRoom {

    static class Patient {
        String name;
        int priority;

        public Patient(String name, int priority) {
            this.name = name;
            this.priority = priority;
        }

        @Override
        public String toString() {
            return name + " (Priority: " + priority + ")";
        }
    }

    public static void main(String[] args) {
        // Use a priority queue with a custom comparator to prioritize based on the 'priority' field.
        PriorityQueue<Patient> erQueue = new PriorityQueue<>(Comparator.comparingInt(p -> p.priority));

        erQueue.offer(new Patient("Alice", 3));
        erQueue.offer(new Patient("Bob", 1)); // Highest priority
        erQueue.offer(new Patient("Charlie", 2));
        erQueue.offer(new Patient("David", 3));

        System.out.println("Emergency Room Queue:");

        while (!erQueue.isEmpty()) {
            Patient nextPatient = erQueue.poll();
            System.out.println("Treating: " + nextPatient);
        }
    }
} 

These are just a couple of examples, and the use of queues in competitive programming extends to many other problem types. Understanding the properties of different queue implementations and when to use them is crucial for writing efficient and correct solutions.