Implementing Deques in Java for Competitive Programming

In competitive programming, efficiency and the correct data structure choice are paramount. A Deque (Double Ended Queue) is a versatile data structure that allows insertion and deletion from both ends. Java's `java.util.Deque` interface provides a standardized way to work with deques, and implementations like `ArrayDeque` and `LinkedList` offer distinct performance characteristics. This document explores how to implement Deques in Java and demonstrates their application through solved competitive programming problems.

Understanding the java.util.Deque Interface

The `java.util.Deque` interface extends the `Queue` interface and provides methods for adding, removing, and examining elements from both the head and tail of the queue. Key methods include:

• addFirst(E e): Inserts the specified element at the front of this deque. Throws an exception if the deque is full and cannot accept more elements immediately.
• addLast(E e): Inserts the specified element at the end of this deque. Throws an exception if the deque is full and cannot accept more elements immediately.
• offerFirst(E e): Inserts the specified element at the front of this deque, returning true if successful, or false if space is not currently available.
• offerLast(E e): Inserts the specified element at the end of this deque, returning true if successful, or false if space is not currently available.
• removeFirst(): Retrieves and removes the first element of this deque. Throws NoSuchElementException if this deque is empty.
• removeLast(): Retrieves and removes the last element of this deque. Throws NoSuchElementException if this deque is empty.
• pollFirst(): Retrieves and removes the first element of this deque, or returns null if this deque is empty.
• pollLast(): Retrieves and removes the last element of this deque, or returns null if this deque is empty.
• getFirst(): Retrieves, but does not remove, the first element of this deque. Throws NoSuchElementException if this deque is empty.
• getLast(): Retrieves, but does not remove, the last element of this deque. Throws NoSuchElementException if this deque is empty.
• peekFirst(): Retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty.
• peekLast(): Retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty.
• isEmpty(): Returns true if this deque contains no elements.
• size(): Returns the number of elements in this deque.

Deque Implementations: ArrayDeque vs. LinkedList

Java provides two primary implementations of the `Deque` interface:

• ArrayDeque: This is a resizable array implementation. It is generally faster than `LinkedList` for most operations, especially when accessing elements by index. It avoids the overhead of node creation and manipulation. It's the recommended choice when you don't need linked-list specific features and performance is critical. It does not allow null elements.
• LinkedList: This is a doubly-linked list implementation. It provides constant-time insertion and removal at both ends. It's suitable when you require frequent insertions and deletions, especially in the middle of the collection (although deque operations are focused on the ends). It allows null elements.

The choice between `ArrayDeque` and `LinkedList` depends on the specific problem requirements. `ArrayDeque` is often preferred for its better performance in most common scenarios.

Examples and Solutions

Problem 1: Palindrome Checker

Problem Statement: Given a string, determine if it is a palindrome (reads the same forwards and backward), ignoring case and non-alphanumeric characters.

 Input: "A man, a plan, a canal: Panama"
Output: true

Input: "race a car"
Output: false 

 import java.util.Deque;
import java.util.ArrayDeque;

public class PalindromeChecker {

    public static boolean isPalindrome(String s) {
        s = s.toLowerCase().replaceAll("[^a-z0-9]", "");
        if (s.isEmpty()) {
            return true;
        }

        Deque<Character> deque = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            deque.addLast(c);
        }

        while (deque.size() > 1) {
            if (deque.removeFirst() != deque.removeLast()) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        String s1 = "A man, a plan, a canal: Panama";
        String s2 = "race a car";

        System.out.println("\"" + s1 + "\" is palindrome: " + isPalindrome(s1)); // true
        System.out.println("\"" + s2 + "\" is palindrome: " + isPalindrome(s2)); // false
    }
} 

Problem 2: Sliding Window Maximum

Problem Statement: Given an array of integers `nums` and an integer `k`, representing the size of the sliding window, find the maximum value in each sliding window as it moves from the left to the right of the array.

 Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Explanation:
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7 

 import java.util.Deque;
import java.util.ArrayDeque;

public class SlidingWindowMaximum {

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        int n = nums.length;
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // Remove elements out of the window
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // Remove smaller elements than the current element to maintain decreasing order
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }

            deque.offerLast(i); // Add current element's index to the deque

            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()]; // The first element in the deque is the index of the maximum element
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        int[] result = maxSlidingWindow(nums, k);

        System.out.print("Sliding Window Maximum: ");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }
        System.out.println();
    }
} 

Problem 3: Implement Stack using Deque

Problem Statement: Implement stack data structure using the Deque interface in Java.

 push(x) -- Push element x onto stack.
    pop() -- Removes the element on top of the stack.
    top() -- Get the top element.
    empty() -- Return whether the stack is empty. 

 import java.util.Deque;
        import java.util.ArrayDeque;

        class MyStack {
            private Deque deque;

            public MyStack() {
                deque = new ArrayDeque<>();
            }

            public void push(int x) {
                deque.addFirst(x); // Adding at the beginning simulates pushing onto the stack.
            }

            public int pop() {
                if (empty()) {
                   throw new IllegalStateException("Stack is empty.");
                }
                return deque.removeFirst(); // Removing from the beginning simulates popping the stack.
            }

            public int top() {
                if (empty()) {
                    throw new IllegalStateException("Stack is empty.");
                }
                return deque.peekFirst(); // Peeking at the beginning simulates getting the top element.
            }

            public boolean empty() {
                return deque.isEmpty();
            }

            public static void main(String[] args) {
                MyStack stack = new MyStack();
                stack.push(1);
                stack.push(2);
                System.out.println("Top: " + stack.top()); // Output: Top: 2
                System.out.println("Pop: " + stack.pop()); // Output: Pop: 2
                System.out.println("Empty: " + stack.empty()); // Output: Empty: false
            }

        } 

Conclusion

Deques are a powerful data structure in Java, especially useful in competitive programming scenarios where efficient manipulation of elements from both ends of a collection is required. Understanding the `java.util.Deque` interface and the performance characteristics of `ArrayDeque` and `LinkedList` is crucial for selecting the right implementation for a given problem. The example problems demonstrate how Deques can be used to solve a variety of algorithmic challenges.