队列应用：滑动窗口最大值

任务调度器（LeetCode 621）

CPU 冷却时间 n 后才能执行相同任务，求最少执行时间。

贪心：最高频率任务决定框架，其余填充空槽。

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];
    int idleSlots = (maxFreq - 1) * n;
    for (int i = 24; i >= 0; i--) {
        idleSlots -= Math.min(freq[i], maxFreq - 1);
    }
    return tasks.length + Math.max(0, idleSlots);
}

思路：以最高频任务构建 (maxFreq-1) 个桶，每桶 n+1 个位置。

滑动窗口最大值（LeetCode 239）

单调双端队列（deque）：队列存下标，队头始终是窗口最大值的下标。

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++) {
        // 移除过期下标（不在窗口内）
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1)
            deque.pollFirst();
        // 维护单调递减：移除所有比当前元素小的
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            deque.pollLast();
        deque.offerLast(i);
        if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
    }
    return result;
}

前中后队列（LeetCode 1670）

支持 pushFront、pushMiddle、pushBack、popFront、popMiddle、popBack，均 O(1)。

用两个双端队列（front/back），保持 front.size() ≤ back.size() 且差≤1：

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

    private void balance() {
        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);
        // 无需再 balance，已精确插中间
    }
    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;
        int val = (front.size() == back.size()) ? front.pollLast() : back.pollFirst();
        balance(); return val;
    }
}

总结