Data Structures: Queues and Deques in Java

Understanding and implementing Queues and Deques in Java, with example problems demonstrating their uses in Breadth-First Search and other scenarios.

⬅ Previous Next ➡

Queues in Competitive Programming (Java)

Introduction to Queues

Queues are fundamental data structures used in various algorithms and problem-solving scenarios in competitive programming. They are particularly useful for managing data in a specific order, ensuring that elements are processed in the sequence they were added. Think of a queue like a line at a checkout counter - the first person in line is the first person served.

Understanding the Queue Data Structure

FIFO (First-In, First-Out) Principle

The core principle of a queue is FIFO (First-In, First-Out). This means that the element that was added to the queue earliest will be the first element to be removed. This contrasts with other data structures like stacks (LIFO - Last-In, First-Out).

Common Queue Operations

Enqueue: Adding an element to the rear (end) of the queue.
Dequeue: Removing the element from the front of the queue.
Peek: Viewing the element at the front of the queue without removing it.
isEmpty: Checking if the queue is empty.

Queue Implementations in Java

Java provides built-in classes for implementing queues:

java.util.Queue: An interface that defines the basic queue operations.
java.util.LinkedList: Can be used to implement a queue. It implements the Queue interface.
java.util.PriorityQueue: Implements a priority queue where elements are dequeued based on their priority (not necessarily FIFO).
java.util.ArrayDeque: Another efficient implementation, often preferred over LinkedList.

Using `LinkedList` as a Queue

LinkedList is a common choice for implementing queues because it provides efficient add and remove operations at both ends.

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

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

        // Enqueue elements
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);

        System.out.println("Queue: " + queue); // Output: Queue: [10, 20, 30]

        // Dequeue an element
        int dequeuedElement = queue.poll();
        System.out.println("Dequeued element: " + dequeuedElement); // Output: Dequeued element: 10
        System.out.println("Queue after dequeue: " + queue); // Output: Queue after dequeue: [20, 30]

        // Peek at the front element
        int frontElement = queue.peek();
        System.out.println("Front element: " + frontElement); // Output: Front element: 20

        // Check if the queue is empty
        boolean isEmpty = queue.isEmpty();
        System.out.println("Is the queue empty? " + isEmpty); // Output: Is the queue empty? false
    }
}

Using `ArrayDeque` as a Queue

ArrayDeque is a resizable array implementation of the Deque interface, which is more efficient than LinkedList for queue operations in many cases.

 import java.util.ArrayDeque;
import java.util.Queue;

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

        // Enqueue elements
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);

        System.out.println("Queue: " + queue);

        // Dequeue an element
        int dequeuedElement = queue.poll();
        System.out.println("Dequeued element: " + dequeuedElement);
        System.out.println("Queue after dequeue: " + queue);

        // Peek at the front element
        int frontElement = queue.peek();
        System.out.println("Front element: " + frontElement);

        // Check if the queue is empty
        boolean isEmpty = queue.isEmpty();
        System.out.println("Is the queue empty? " + isEmpty);
    }
}

Competitive Programming Examples with Solutions

Example 1: Breadth-First Search (BFS)

Queues are commonly used in BFS algorithms to explore a graph level by level. Here's a simplified example of BFS in a graph represented by an adjacency list.

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

public class BFSExample {

    public static void bfs(int startNode, List<List<Integer>> adj, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(startNode);
        visited[startNode] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : adj.get(node)) {
                if (!visited[neighbor]) {
                    queue.offer(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        int numNodes = 6;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) {
            adj.add(new ArrayList<>());
        }

        // Example graph:  (0) -- (1) -- (2)
        //                  |     |
        //                  (3) -- (4) -- (5)
        adj.get(0).add(1); adj.get(0).add(3);
        adj.get(1).add(0); adj.get(1).add(2); adj.get(1).add(4);
        adj.get(2).add(1);
        adj.get(3).add(0); adj.get(3).add(4);
        adj.get(4).add(1); adj.get(4).add(3); adj.get(4).add(5);
        adj.get(5).add(4);


        boolean[] visited = new boolean[numNodes];
        System.out.print("BFS Traversal: ");
        bfs(0, adj, visited);  // Start BFS from node 0
        System.out.println();
    }
}

Explanation:

The bfs method takes a starting node, an adjacency list representing the graph, and a visited array.
It enqueues the starting node and marks it as visited.
While the queue is not empty, it dequeues a node, prints it, and enqueues all its unvisited neighbors.

Example 2: Print First Negative Integer in Every Window of Size K

Given an array and a window of size k, find the first negative integer in each window.

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

public class FirstNegativeInteger {

    public static List<Integer> findFirstNegative(int[] arr, int k) {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> negIndices = new LinkedList<>(); // Store indices of negative numbers in the window

        // Process the first k elements
        for (int i = 0; i < k; i++) {
            if (arr[i] < 0) {
                negIndices.offer(i);
            }
        }

        // Iterate through the rest of the array, sliding the window
        for (int i = k; i < arr.length; i++) {
            // Check if the first negative integer of the previous window is still valid
            if (!negIndices.isEmpty() && negIndices.peek() <= i - k) {
                negIndices.poll(); // Remove it if it's outside the current window
            }

            // Add the current element to the queue if it is negative
            if (arr[i] < 0) {
                negIndices.offer(i);
            }

            // Get the first negative integer for the current window
            if (!negIndices.isEmpty()) {
                result.add(arr[negIndices.peek()]);
            } else {
                result.add(0); // No negative integer in the current window
            }
        }

        // Add the first negative integer for the initial window
        if (!negIndices.isEmpty()) {
            result.add(0, arr[negIndices.peek()]);
        } else {
            result.add(0, 0);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {12, -1, -7, 8, -15, 30, 16, 28};
        int k = 3;
        List<Integer> result = findFirstNegative(arr, k);
        System.out.println("First negative integers in each window of size " + k + ": " + result);
        //Output: First negative integers in each window of size 3: [-1, -1, -7, -15, -15, 0]
    }
}