Deque in Java — Sliding Window O(n) and Monotonic Patterns

package io.thecodeforge.deque;

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

public class DequeCoreBehavior {

    public static void main(String[] args) {

        // ArrayDeque is the go-to Deque implementation in Java.
        // It's backed by a resizable circular array — fast and cache-friendly.
        Deque<String> taskQueue = new ArrayDeque<>();

        // --- addLast: normal enqueue, like a regular queue ---
        taskQueue.addLast("render-homepage");   // rear -> [render-homepage]
        taskQueue.addLast("send-email");         // rear -> [render-homepage, send-email]
        taskQueue.addLast("resize-image");       // rear -> [render-homepage, send-email, resize-image]

        System.out.println("Initial task queue: " + taskQueue);
        // Output: [render-homepage, send-email, resize-image]

        // --- addFirst: urgent task jumps to the FRONT ---
        // This is the operation no plain Queue can do without rebuilding itself.
        taskQueue.addFirst("URGENT-payment-gateway");
        System.out.println("After urgent task injected at front: " + taskQueue);
        // Output: [URGENT-payment-gateway, render-homepage, send-email, resize-image]

        // --- peekFirst / peekLast: look without removing ---
        System.out.println("Next task to process: " + taskQueue.peekFirst());  // URGENT-payment-gateway
        System.out.println("Last task in line:    " + taskQueue.peekLast());   // resize-image

        // --- removeFirst: process tasks from the front ---
        String processed = taskQueue.removeFirst();
        System.out.println("Processed: " + processed);
        System.out.println("Remaining tasks: " + taskQueue);
        // Output: [render-homepage, send-email, resize-image]

        // --- removeLast: cancel the last-added task (like an undo) ---
        String cancelled = taskQueue.removeLast();
        System.out.println("Cancelled (last task removed): " + cancelled);
        System.out.println("Final queue: " + taskQueue);
        // Output: [render-homepage, send-email]
    }
}

package io.thecodeforge.deque;

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

public class DequeAsStackAndQueue {

    // ── Using Deque as a STACK (LIFO) ────────────────────────────────────────
    // Real use case: parsing nested brackets in a code editor
    static boolean isBracketsBalanced(String sourceCode) {
        Deque<Character> bracketStack = new ArrayDeque<>();

        for (char ch : sourceCode.toCharArray()) {
            // Opening bracket: push onto the top of our stack
            if (ch == '(' || ch == '{' || ch == '[') {
                bracketStack.addFirst(ch);  // addFirst = push
            }
            // Closing bracket: check if it matches the last opened bracket
            else if (ch == ')' || ch == '}' || ch == ']') {
                if (bracketStack.isEmpty()) {
                    return false; // Closed something that was never opened
                }
                char lastOpened = bracketStack.removeFirst(); // removeFirst = pop
                if (!isMatchingPair(lastOpened, ch)) {
                    return false; // Mismatch: { closed by ) for example
                }
            }
        }
        // If stack is empty, every opened bracket was closed correctly
        return bracketStack.isEmpty();
    }

    static boolean isMatchingPair(char open, char close) {
        return (open == '(' && close == ')')
            || (open == '{' && close == '}')
            || (open == '[' && close == ']');
    }

    // ── Using Deque as a QUEUE (FIFO) ────────────────────────────────────────
    // Real use case: print job spooler — jobs processed in arrival order,
    // but a SYSTEM job can jump to the front.
    static void simulatePrintSpooler() {
        Deque<String> printQueue = new ArrayDeque<>();

        // Normal jobs arrive at the back
        printQueue.addLast("user-invoice.pdf");     // addLast = enqueue
        printQueue.addLast("user-report.pdf");
        printQueue.addLast("user-photo.png");

        // System diagnostic needs to print NOW — inject at the front
        printQueue.addFirst("SYSTEM-diagnostic.pdf");

        System.out.println("Print spooler order:");
        while (!printQueue.isEmpty()) {
            System.out.println("  Printing: " + printQueue.removeFirst()); // removeFirst = dequeue
        }
    }

    public static void main(String[] args) {
        // ── Stack mode: bracket validation ──
        System.out.println("Bracket check '{[()]}':   " + isBracketsBalanced("{[()]}"));  // true
        System.out.println("Bracket check '({[})':    " + isBracketsBalanced("({[})"));    // false
        System.out.println("Bracket check '((()))':   " + isBracketsBalanced("((()))"));  // true
        System.out.println();

        // ── Queue mode: print spooler ──
        simulatePrintSpooler();
    }
}

package io.thecodeforge.deque;

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

public class SlidingWindowMaximum {

    /**
     * Finds the maximum value in every sliding window of size windowSize.
     *
     * The Deque stores INDICES (not values) of candidate maximum elements.
     * Invariant: elements in the Deque are always in decreasing order of their
     * corresponding values in the input array.
     *
     * @param temperatures  The input array (e.g., daily temperature readings)
     * @param windowSize    Number of days in each sliding window
     * @return              Array of maximum temperatures per window
     */
    static int[] slidingWindowMax(int[] temperatures, int windowSize) {
        if (temperatures == null || temperatures.length == 0 || windowSize <= 0) {
            return new int[0];
        }

        int totalDays = temperatures.length;
        int[] windowMaxima = new int[totalDays - windowSize + 1]; // one max per window
        int resultIndex = 0;

        // The Deque holds indices into the temperatures array.
        // Front = index of current window's maximum.
        // Back  = index of the smallest 'candidate' we haven't discarded yet.
        Deque<Integer> candidateIndices = new ArrayDeque<>();

        for (int currentDay = 0; currentDay < totalDays; currentDay++) {

            // STEP 1: Evict from the BACK — remove any past candidates whose
            // temperature is <= today's. They can NEVER be a future window max
            // while today's value is still inside the window.
            while (!candidateIndices.isEmpty()
                    && temperatures[candidateIndices.peekLast()] <= temperatures[currentDay]) {
                candidateIndices.removeLast(); // this candidate is useless now
            }

            // STEP 2: Add today's index as the newest candidate at the BACK
            candidateIndices.addLast(currentDay);

            // STEP 3: Evict from the FRONT — if the front index is outside
            // the current window's left boundary, it's no longer valid.
            int windowLeftBoundary = currentDay - windowSize + 1;
            if (candidateIndices.peekFirst() < windowLeftBoundary) {
                candidateIndices.removeFirst(); // slid out of the window
            }

            // STEP 4: Once we've filled the first window, record the max.
            // The front of the Deque is always the index of the window's max.
            if (currentDay >= windowSize - 1) {
                windowMaxima[resultIndex++] = temperatures[candidateIndices.peekFirst()];
            }
        }

        return windowMaxima;
    }

    public static void main(String[] args) {
        // Scenario: 10 days of temperature readings, window = 3 days
        int[] dailyTemperatures = {31, 27, 34, 22, 19, 35, 28, 30, 24, 33};
        int windowSize = 3;

        System.out.println("Daily temperatures: " + Arrays.toString(dailyTemperatures));
        System.out.println("Window size: " + windowSize + " days\n");

        int[] maxPerWindow = slidingWindowMax(dailyTemperatures, windowSize);

        System.out.println("Max temperature in each 3-day window:");
        for (int i = 0; i < maxPerWindow.length; i++) {
            int windowStart = i;
            int windowEnd   = i + windowSize - 1;
            System.out.printf("  Days %d-%d %s  →  Max: %d°C%n",
                windowStart + 1,
                windowEnd   + 1,
                Arrays.toString(Arrays.copyOfRange(dailyTemperatures, windowStart, windowEnd + 1)),
                maxPerWindow[i]);
        }

        // Edge case: window size = 1 (each element is its own max)
        System.out.println();
        int[] singleDayWindow = slidingWindowMax(dailyTemperatures, 1);
        System.out.println("Window size 1 (sanity check): " + Arrays.toString(singleDayWindow));

        // Edge case: window = full array (single max of entire array)
        int[] fullWindow = slidingWindowMax(dailyTemperatures, dailyTemperatures.length);
        System.out.println("Window = full array:           " + Arrays.toString(fullWindow));
    }
}