Queue Applications: Sliding Window Max and Scheduling

Task Scheduler (LeetCode 621)

Given a CPU cooling time n between two identical tasks, find the minimum execution time.

Greedy Approach: The task with the highest frequency determines the overall framework; other tasks are used to fill the idle slots between them.

public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char c : tasks) freq[c - 'A']++;
    Arrays.sort(freq);
    
    int maxFreq = freq[25];
    // Calculate idle slots assuming only the highest frequency task exists
    int idleSlots = (maxFreq - 1) * n;
    
    // Fill idle slots with other tasks
    for (int i = 24; i >= 0; i--) {
        idleSlots -= Math.min(freq[i], maxFreq - 1);
    }
    
    return tasks.length + Math.max(0, idleSlots);
}

Logic: Build (maxFreq - 1) buckets based on the highest frequency task, where each bucket has n + 1 slots.

Sliding Window Maximum (LeetCode 239)

Using a monotonic double-ended queue (Deque): The queue stores indices, and the head of the queue always points to the current maximum in the window.

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // 1. Remove expired indices that are outside the current window
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        // 2. Maintain monotonic decrease: remove indices of elements smaller than the current one
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        
        // 3. Current window is ready; front is the maximum
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

Front Middle Back Queue (LeetCode 1670)

Supports pushFront, pushMiddle, pushBack, popFront, popMiddle, popBack, all in O(1) time.

Implementation uses two Deques (front and back), maintaining the invariant that front.size() <= back.size() and their difference is at most 1:

class FrontMiddleBackQueue {
    private Deque<Integer> front = new ArrayDeque<>();
    private Deque<Integer> back  = new ArrayDeque<>();

    private void balance() {
        // Ensure |front| <= |back| and difference <= 1
        if (front.size() > back.size()) {
            back.offerFirst(front.pollLast());
        } else if (back.size() > front.size() + 1) {
            front.offerLast(back.pollFirst());
        }
    }

    public void pushFront(int val) { front.offerFirst(val); balance(); }
    public void pushBack(int val)  { back.offerLast(val);   balance(); }
    
    public void pushMiddle(int val) {
        if (front.size() < back.size()) {
            front.offerLast(val);
        } else {
            back.offerFirst(val);
        }
        // No additional balance needed as it's precisely placed in the middle
    }

    public int popFront() {
        if (front.isEmpty() && back.isEmpty()) return -1;
        int val = front.isEmpty() ? back.pollFirst() : front.pollFirst();
        balance(); 
        return val;
    }

    public int popBack() {
        if (back.isEmpty()) return -1;
        int val = back.pollLast(); 
        balance(); 
        return val;
    }

    public int popMiddle() {
        if (front.isEmpty() && back.isEmpty()) return -1;
        // Selection depends on whether total size is even or odd
        int val = (front.size() == back.size()) ? front.pollLast() : back.pollFirst();
        balance(); 
        return val;
    }
}

Summary