Queue与Deque

import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.ArrayBlockingQueue;
 
public class InsertDemo {
    public static void main(String[] args) {
 
        // ========== 无界队列演示 ==========
        // LinkedList 实现了 Queue 接口，是一个无界队列
        Queue<String> unbounded = new LinkedList<>();
 
        // add() 和 offer() 在无界队列中行为几乎一致
        unbounded.add("Alice");      // 返回 true，插入成功
        unbounded.offer("Bob");      // 返回 true，插入成功
        System.out.println(unbounded); // 输出: [Alice, Bob]
 
        // ========== 有界队列演示 ==========
        // ArrayBlockingQueue 是一个容量固定的有界队列，这里容量设为 2
        Queue<String> bounded = new ArrayBlockingQueue<>(2);
 
        bounded.offer("X");  // 返回 true，当前队列: [X]
        bounded.offer("Y");  // 返回 true，当前队列: [X, Y]
 
        // 队列已满，offer() 优雅地返回 false
        boolean result = bounded.offer("Z");
        System.out.println("offer Z 结果: " + result); // 输出: false
 
        // 队列已满，add() 直接抛出 IllegalStateException
        try {
            bounded.add("Z"); // 这里会抛异常！
        } catch (IllegalStateException e) {
            // 捕获异常，打印错误信息
            System.out.println("add Z 异常: " + e.getMessage());
            // 输出: add Z 异常: Queue full
        }
    }
}

import java.util.LinkedList;
import java.util.Queue;
 
public class RemoveDemo {
    public static void main(String[] args) {
 
        Queue<String> queue = new LinkedList<>();
        // 依次入队三个元素
        queue.offer("First");   // 队列: [First]
        queue.offer("Second");  // 队列: [First, Second]
        queue.offer("Third");   // 队列: [First, Second, Third]
 
        // remove() 移除并返回队头元素
        String r1 = queue.remove();
        System.out.println("remove: " + r1);  // 输出: First（FIFO，先进先出）
        // 此时队列: [Second, Third]
 
        // poll() 同样移除并返回队头元素
        String r2 = queue.poll();
        System.out.println("poll: " + r2);    // 输出: Second
        // 此时队列: [Third]
 
        // 继续取出最后一个
        queue.poll(); // 取出 Third，队列变空
 
        // ========== 队列为空时的差异 ==========
 
        // poll() 对空队列返回 null
        String safe = queue.poll();
        System.out.println("空队列 poll: " + safe);  // 输出: null
 
        // remove() 对空队列抛出 NoSuchElementException
        try {
            queue.remove(); // 这里会抛异常！
        } catch (java.util.NoSuchElementException e) {
            System.out.println("空队列 remove 异常: " + e);
            // 输出: 空队列 remove 异常: java.util.NoSuchElementException
        }
    }
}

import java.util.LinkedList;
import java.util.Queue;
 
public class ExamineDemo {
    public static void main(String[] args) {
 
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(100);  // 队列: [100]
        queue.offer(200);  // 队列: [100, 200]
 
        // element() 查看队头，不移除
        int head1 = queue.element();
        System.out.println("element: " + head1);     // 输出: 100
        System.out.println("队列大小: " + queue.size()); // 输出: 2（元素没有被移除）
 
        // peek() 同样查看队头，不移除
        int head2 = queue.peek();
        System.out.println("peek: " + head2);         // 输出: 100
        System.out.println("队列大小: " + queue.size()); // 输出: 2
 
        // 清空队列
        queue.clear();
 
        // ========== 队列为空时的差异 ==========
 
        // peek() 对空队列返回 null
        Integer safe = queue.peek();
        System.out.println("空队列 peek: " + safe);   // 输出: null
 
        // element() 对空队列抛出 NoSuchElementException
        try {
            queue.element(); // 这里会抛异常！
        } catch (java.util.NoSuchElementException e) {
            System.out.println("空队列 element 异常!");
            // 输出: 空队列 element 异常!
        }
    }
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
 
public class BfsDemo {
 
    // 简单的二叉树节点定义
    static class TreeNode {
        int val;           // 节点值
        TreeNode left;     // 左子节点
        TreeNode right;    // 右子节点
 
        TreeNode(int val) {
            this.val = val; // 构造时赋值
        }
    }
 
    /**
     * 层序遍历二叉树（BFS）
     * 利用队列的 FIFO 特性，逐层访问节点
     */
    static List<List<Integer>> levelOrder(TreeNode root) {
        // 存放最终结果：每一层是一个 List
        List<List<Integer>> result = new ArrayList<>();
 
        // 边界条件：空树直接返回
        if (root == null) return result;
 
        // 创建队列，ArrayDeque 是 Queue 的最佳通用实现
        Queue<TreeNode> queue = new ArrayDeque<>();
        // 根节点入队，作为第一层的起点
        queue.offer(root);
 
        // 只要队列不为空，说明还有节点未处理
        while (!queue.isEmpty()) {
            // 当前层的节点数量（此时队列中恰好全是当前层的节点）
            int levelSize = queue.size();
            // 存放当前层的所有节点值
            List<Integer> currentLevel = new ArrayList<>();
 
            // 逐个处理当前层的每个节点
            for (int i = 0; i < levelSize; i++) {
                // poll() 取出队头节点
                TreeNode node = queue.poll();
                // 将节点值加入当前层结果
                currentLevel.add(node.val);
 
                // 如果左子节点存在，入队（它属于下一层）
                if (node.left != null) {
                    queue.offer(node.left);
                }
                // 如果右子节点存在，入队（它属于下一层）
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 当前层处理完毕，加入结果集
            result.add(currentLevel);
        }
        return result; // 返回所有层的遍历结果
    }
 
    public static void main(String[] args) {
        //       1
        //      / \
        //     2   3
        //    / \   \
        //   4   5   6
        TreeNode root = new TreeNode(1);          // 构建根节点
        root.left = new TreeNode(2);              // 左子节点
        root.right = new TreeNode(3);             // 右子节点
        root.left.left = new TreeNode(4);         // 左子节点的左子节点
        root.left.right = new TreeNode(5);        // 左子节点的右子节点
        root.right.right = new TreeNode(6);       // 右子节点的右子节点
 
        // 执行层序遍历
        List<List<Integer>> levels = levelOrder(root);
        // 输出: [[1], [2, 3], [4, 5, 6]]
        System.out.println(levels);
    }
}

Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.poll();
q.offer(4);
System.out.println(q.peek() + " " + q.size());

// 最基本的使用：默认是小顶堆，每次 poll() 取出最小值
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);  // 入队 30
pq.offer(10);  // 入队 10
pq.offer(20);  // 入队 20
 
System.out.println(pq.poll()); // 输出 10（最小值先出）
System.out.println(pq.poll()); // 输出 20
System.out.println(pq.poll()); // 输出 30

            10              ← 根节点，全局最小
           /  \
         20    30
        /  \
      40    50

// PriorityQueue 内部核心字段（JDK 源码简化）
transient Object[] queue;  // 用数组存储堆元素
int size;                  // 当前元素个数

数组索引:    [0]   [1]   [2]   [3]   [4]
数组内容:     10    20    30    40    50
 
对应的树结构:
                 10          ← index 0
                /  \
              20    30       ← index 1, 2
             /  \
           40    50          ← index 3, 4
 
索引公式（0-based）:
  父节点索引:     parent(i) = (i - 1) / 2
  左子节点索引:   left(i)   = 2 * i + 1
  右子节点索引:   right(i)  = 2 * i + 2

// 模拟 offer(15) 的过程
// 初始状态:
//        10
//       /  \
//     20    30
//    /  \
//  40    50
 
// Step 1: 将 15 放到数组末尾 index=5（即 30 的左子节点）
//        10
//       /  \
//     20    30
//    /  \   /
//  40  50  15    ← 新元素
 
// Step 2: 比较 15 和父节点 30（index=(5-1)/2=2），15 < 30，交换
//        10
//       /  \
//     20    15   ← 上浮到 index=2
//    /  \   /
//  40  50  30
 
// Step 3: 比较 15 和父节点 10（index=(2-1)/2=0），15 > 10，停止
// 最终结果: [10, 20, 15, 40, 50, 30]

// JDK PriorityQueue.siftUp 简化版
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x; // 将元素转为 Comparable
    while (k > 0) {                          // 只要还没到根节点就继续
        int parent = (k - 1) >>> 1;          // 计算父节点索引（无符号右移1位等价于除以2）
        Object e = queue[parent];            // 取出父节点的值
        if (key.compareTo((E) e) >= 0)       // 如果新元素 >= 父节点，堆序性满足
            break;                           // 停止上浮
        queue[k] = e;                        // 否则，将父节点下移到当前位置
        k = parent;                          // 当前位置上移到父节点位置
    }
    queue[k] = key;                          // 最终将新元素放到正确位置
}

// 模拟 poll() 的过程
// 初始状态: [10, 20, 15, 40, 50, 30]
//        10          ← 取走这个（返回值）
//       /  \
//     20    15
//    /  \   /
//  40  50  30
 
// Step 1: 取走根节点 10，将末尾元素 30 放到根
//        30          ← 末尾元素放到根
//       /  \
//     20    15
//    /  \
//  40  50
 
// Step 2: 比较 30 与子节点 20、15，选较小的 15（index=2），30 > 15，交换
//        15
//       /  \
//     20    30       ← 下沉到 index=2
//    /  \
//  40  50
 
// Step 3: 30 在 index=2，无子节点，停止
// 最终结果: [15, 20, 30, 40, 50]，返回 10

// JDK PriorityQueue.siftDown 简化版
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x; // 将元素转为 Comparable
    int half = size >>> 1;                   // 只有索引 < size/2 的节点才有子节点
    while (k < half) {                       // 只要当前节点不是叶子节点
        int child = (k << 1) + 1;            // 左子节点索引 = 2*k + 1
        Object c = queue[child];             // 取左子节点的值
        int right = child + 1;               // 右子节点索引
        if (right < size &&                  // 如果右子节点存在
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) // 且左 > 右
            c = queue[child = right];        // 选择较小的右子节点
        if (key.compareTo((E) c) <= 0)       // 如果当前元素 <= 较小子节点
            break;                           // 堆序性满足，停止下沉
        queue[k] = c;                        // 否则，将较小子节点上移
        k = child;                           // 当前位置下移到子节点位置
    }
    queue[k] = key;                          // 最终将元素放到正确位置
}

┌─────────────┬──────────────┬──────────────────────────────────┐
│   操作       │  时间复杂度   │  说明                            │
├─────────────┼──────────────┼──────────────────────────────────┤
│ offer(e)    │  O(log n)    │  尾部插入 + 上浮                  │
│ poll()      │  O(log n)    │  取根 + 末尾补根 + 下沉            │
│ peek()      │  O(1)        │  直接返回 queue[0]                │
│ remove(o)   │  O(n)        │  线性查找 O(n) + 下沉/上浮 O(log n)│
│ contains(o) │  O(n)        │  线性扫描数组                     │
│ size()      │  O(1)        │  直接返回 size 字段               │
└─────────────┴──────────────┴──────────────────────────────────┘

// JDK 源码简化
private void grow(int minCapacity) {
    int oldCapacity = queue.length;          // 旧容量
    int newCapacity = oldCapacity +          // 新容量 =
        ((oldCapacity < 64) ?                // 如果旧容量 < 64
         (oldCapacity + 2) :                 //   翻倍 + 2（小数组快速增长）
         (oldCapacity >> 1));                //   否则增长 50%（大数组温和增长）
    // ... 边界检查后创建新数组并拷贝
    queue = Arrays.copyOf(queue, newCapacity);
}

// 方式一：使用 Comparator.reverseOrder()（推荐，最简洁）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
 
// 方式二：使用 Lambda 表达式
PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>((a, b) -> b - a);
// ⚠️ 注意：b - a 在极端值时可能溢出，生产代码建议用 Integer.compare(b, a)
 
// 方式三：安全的 Lambda 写法
PriorityQueue<Integer> maxHeap3 = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
 
// 验证
maxHeap.offer(10);  // 入队
maxHeap.offer(30);  // 入队
maxHeap.offer(20);  // 入队
System.out.println(maxHeap.poll()); // 输出 30（最大值先出）
System.out.println(maxHeap.poll()); // 输出 20
System.out.println(maxHeap.poll()); // 输出 10

// 当 b = Integer.MAX_VALUE, a = -1 时
// b - a = Integer.MAX_VALUE - (-1) = Integer.MAX_VALUE + 1 → 溢出为负数！
// 这会导致比较结果错误，堆的排序被破坏
// 所以生产代码务必使用 Integer.compare(b, a)

// 定义任务类
class Task {
    String name;       // 任务名称
    int priority;      // 优先级数值（越小越优先）
    long timestamp;    // 创建时间戳
 
    Task(String name, int priority) {
        this.name = name;                          // 设置任务名
        this.priority = priority;                  // 设置优先级
        this.timestamp = System.nanoTime();        // 记录创建时间
    }
 
    @Override
    public String toString() {
        return name + "(P" + priority + ")";       // 便于打印查看
    }
}
 
// 创建优先级队列：先按 priority 升序，priority 相同则按 timestamp 升序（先来先服务）
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt((Task t) -> t.priority)   // 主排序：优先级数值小的先出
              .thenComparingLong(t -> t.timestamp)     // 次排序：时间戳小的（更早的）先出
);
 
taskQueue.offer(new Task("发送邮件", 3));      // 低优先级任务
taskQueue.offer(new Task("数据库备份", 1));    // 高优先级任务
taskQueue.offer(new Task("日志清理", 3));      // 低优先级任务（与"发送邮件"同级）
taskQueue.offer(new Task("安全扫描", 2));      // 中优先级任务
 
// 按优先级依次处理
while (!taskQueue.isEmpty()) {
    System.out.println("处理: " + taskQueue.poll());
}
// 输出:
// 处理: 数据库备份(P1)
// 处理: 安全扫描(P2)
// 处理: 发送邮件(P3)     ← 同为 P3，但比"日志清理"先入队
// 处理: 日志清理(P3)

// ① Lambda（适合简单逻辑）
Comparator<Task> c1 = (a, b) -> Integer.compare(a.priority, b.priority);
 
// ② 方法引用 + comparingInt（推荐，类型安全且可读性好）
Comparator<Task> c2 = Comparator.comparingInt(Task::getPriority);
 
// ③ 多级排序链式调用（复杂排序的最佳实践）
Comparator<Task> c3 = Comparator
    .comparingInt(Task::getPriority)          // 第一排序键
    .thenComparingLong(Task::getTimestamp)    // 第二排序键
    .thenComparing(Task::getName);            // 第三排序键（字典序）
 
// ④ 反转任意 Comparator
Comparator<Task> c4 = c2.reversed();         // 优先级高（数值大）的先出

/**
 * 找出数组中最大的 K 个元素
 * 核心思路：维护一个大小为 K 的小顶堆
 *   - 堆顶始终是堆中最小的元素
 *   - 遍历完成后，堆中剩下的就是最大的 K 个
 */
public static int[] topK(int[] nums, int k) {
    // 创建小顶堆（默认行为）
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
 
    for (int num : nums) {                    // 遍历每个元素
        if (minHeap.size() < k) {             // 堆还没满
            minHeap.offer(num);               // 直接入堆
        } else if (num > minHeap.peek()) {    // 堆满了，但当前元素比堆顶大
            minHeap.poll();                   // 弹出堆顶（当前堆中最小的）
            minHeap.offer(num);               // 将更大的元素入堆
        }
        // 如果 num <= 堆顶，说明它不可能是 Top-K，直接跳过
    }
 
    // 将堆中元素转为数组返回
    int[] result = new int[k];                // 创建结果数组
    for (int i = k - 1; i >= 0; i--) {        // 从后往前填充（poll 出来是从小到大）
        result[i] = minHeap.poll();           // 依次取出
    }
    return result;                            // 返回结果，已从大到小排列
}
 
// 使用示例
int[] data = {3, 1, 5, 12, 2, 11, 9, 7};
int[] top3 = topK(data, 3);
System.out.println(Arrays.toString(top3));    // 输出 [12, 11, 9]

目标：找最大的 K 个元素
 
方案 A（大顶堆）：全部入堆，然后 poll K 次 → 时间 O(n log n)，空间 O(n)
方案 B（小顶堆）：维护大小为 K 的堆      → 时间 O(n log K)，空间 O(K) ✅
 
当 n 远大于 K 时（比如从 1 亿条数据中找 Top 10），
方案 B 的优势是压倒性的：log(10) vs log(1亿) ≈ 3.3 vs 26.6

/**
 * 合并 K 个升序链表为一个升序链表
 * 思路：用小顶堆维护每个链表的当前头节点，每次取最小的接到结果链表
 */
public ListNode mergeKLists(ListNode[] lists) {
    // 创建小顶堆，按节点值排序
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        Comparator.comparingInt(node -> node.val)       // 按节点值升序
    );
 
    // 将每个链表的头节点入堆
    for (ListNode head : lists) {        // 遍历所有链表
        if (head != null) {              // 跳过空链表
            pq.offer(head);              // 头节点入堆
        }
    }
 
    ListNode dummy = new ListNode(0);    // 哨兵节点，简化链表操作
    ListNode tail = dummy;               // tail 指针指向结果链表的尾部
 
    while (!pq.isEmpty()) {              // 堆不为空就继续
        ListNode min = pq.poll();        // 取出当前最小节点
        tail.next = min;                 // 接到结果链表尾部
        tail = tail.next;               // tail 后移
        if (min.next != null) {          // 如果该节点还有后继
            pq.offer(min.next);          // 后继节点入堆
        }
    }
 
    return dummy.next;                   // 返回哨兵节点的下一个，即真正的头节点
}

// ❌ 坑 1：迭代器遍历不保证顺序！
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(30, 10, 20));
for (int val : pq) {
    System.out.print(val + " ");  // 可能输出 10 30 20，不是 10 20 30！
}
// 堆的数组存储只保证 queue[0] 是最小值，其余位置没有严格排序
// ✅ 如果需要有序遍历，必须反复 poll()
 
// ❌ 坑 2：不允许 null 元素
PriorityQueue<String> pq2 = new PriorityQueue<>();
pq2.offer(null);  // 抛出 NullPointerException！
 
// ❌ 坑 3：不是线程安全的
// 多线程环境请使用 PriorityBlockingQueue（java.util.concurrent 包）
 
// ❌ 坑 4：修改已入堆元素的排序字段后，堆不会自动调整
Task task = new Task("test", 5);
taskQueue.offer(task);
task.priority = 1;    // 直接修改优先级
// 堆结构已经被破坏！poll() 的结果可能不正确
// ✅ 正确做法：先 remove，修改后再 offer
taskQueue.remove(task);       // 先移除
task.priority = 1;            // 修改优先级
taskQueue.offer(task);        // 重新入堆

PriorityQueue<int[]> pq = new PriorityQueue<>(
    (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]
);
pq.offer(new int[]{1, 100});
pq.offer(new int[]{2, 50});
pq.offer(new int[]{1, 200});
pq.offer(new int[]{3, 10});
 
System.out.println(Arrays.toString(pq.poll()));
System.out.println(Arrays.toString(pq.poll()));

// ArrayDeque 核心字段（JDK 源码简化）
transient Object[] elements;  // 存储元素的底层数组
transient int head;           // 指向队列头部元素的索引
transient int tail;           // 指向队列尾部下一个空位的索引

  ┌───────────────────── 物理数组 (length = 8) ─────────────────────┐
  │ Index:   0       1       2       3       4       5       6       7  │
  │        ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐          │
  │ Value: │     │     │  A  │  B  │  C  │  D  │     │     │          │
  │        └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘          │
  │                      ↑                       ↑                      │
  │                    head=2                   tail=6                   │
  └─────────────────────────────────────────────────────────────────────┘
 
  逻辑视图（循环）：
        ┌───┐   ┌───┐   ┌───┐   ┌───┐
  HEAD→ │ A │──→│ B │──→│ C │──→│ D │ ←TAIL
        └───┘   └───┘   └───┘   └───┘

  ┌───────────────────── 插入 Z 到头部后 ───────────────────────────┐
  │ Index:   0       1       2       3       4       5       6       7  │
  │        ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐          │
  │ Value: │     │  Z  │  A  │  B  │  C  │  D  │     │     │          │
  │        └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘          │
  │                 ↑                             ↑                      │
  │               head=1                        tail=6                   │
  └─────────────────────────────────────────────────────────────────────┘

// 传统取模方式（有除法，较慢）
int nextIndex = (index + 1) % elements.length;
 
// ArrayDeque 的位运算方式（极快）
// 当 length 是 2 的幂时，(length - 1) 的二进制全是 1
// 例如 length=8 → length-1=7 → 二进制 0111
// 任何数 & 0111 的效果等同于 % 8
int nextIndex = (index + 1) & (elements.length - 1);

// 在队列头部插入元素
public void addFirst(E e) {
    if (e == null)                              // ArrayDeque 不允许 null 元素
        throw new NullPointerException();       // 因为 null 被用作内部的"空位"标记
    head = (head - 1) & (elements.length - 1);  // head 左移一位（循环）
    elements[head] = e;                         // 将元素放入新的 head 位置
    if (head == tail)                           // 如果 head 追上了 tail，说明数组满了
        doubleCapacity();                       // 扩容为原来的两倍
}

// 在队列尾部插入元素
public void addLast(E e) {
    if (e == null)                              // 同样禁止 null
        throw new NullPointerException();
    elements[tail] = e;                         // 将元素放入当前 tail 位置
    tail = (tail + 1) & (elements.length - 1);  // tail 右移一位（循环）
    if (tail == head)                           // 满了就扩容
        doubleCapacity();
}

// 从队列头部移除并返回元素
public E pollFirst() {
    final Object[] es = elements;               // 获取底层数组引用
    final int h = head;                         // 缓存 head 索引
    E e = (E) es[h];                            // 取出 head 位置的元素
    if (e != null) {                            // 如果不为 null，说明队列非空
        es[h] = null;                           // 将该位置置为 null（帮助 GC）
        head = (h + 1) & (es.length - 1);       // head 右移一位
    }
    return e;                                   // 队列为空时返回 null
}

// 容量翻倍
private void doubleCapacity() {
    assert head == tail;                        // 断言：只有满了才会调用
    int p = head;                               // 记录旧 head 位置
    int n = elements.length;                    // 旧数组长度
    int r = n - p;                              // head 右侧的元素个数
    int newCapacity = n << 1;                   // 新容量 = 旧容量 × 2（左移一位）
    if (newCapacity < 0)                        // 溢出检查
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];       // 创建新数组
    System.arraycopy(elements, p, a, 0, r);     // 复制 head 右侧部分到新数组开头
    System.arraycopy(elements, 0, a, r, p);     // 复制 head 左侧部分紧随其后
    elements = a;                               // 替换底层数组
    head = 0;                                   // 重置 head 到 0
    tail = n;                                   // tail 指向旧容量位置
}

  扩容前 (length=8, head=5, tail=5 即满):
  ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
  │  E  │  F  │  G  │  H  │     │  A  │  B  │  C  │
  └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
    0      1      2     3     4  ↑  5     6     7
                                 head=tail=4 (假设)
 
  实际假设 head=5, tail=5:
  Index:  0     1     2     3     4     5     6     7
        ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
        │  D  │  E  │  F  │  G  │  H  │  A  │  B  │  C  │
        └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
                                        ↑head              
                                        ↑tail (head==tail → 满)
 
  第一次 arraycopy: 复制 [5,6,7] → 即 A,B,C → 到新数组 [0,1,2]
  第二次 arraycopy: 复制 [0,1,2,3,4] → 即 D,E,F,G,H → 到新数组 [3,4,5,6,7]
 
  扩容后 (length=16, head=0, tail=8):
  Index:  0     1     2     3     4     5     6     7     8    ...   15
        ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬───┬─────┐
        │  A  │  B  │  C  │  D  │  E  │  F  │  G  │  H  │     │...│     │
        └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴───┴─────┘
        ↑head                                              ↑tail

  ┌──────────────┬──────────────────────┬──────────────────────┐
  │    操作类型    │      头部 (First)     │      尾部 (Last)      │
  ├──────────────┼──────────────────────┼──────────────────────┤
  │  插入(异常)   │  addFirst(e)         │  addLast(e)          │
  │  插入(返回值)  │  offerFirst(e)       │  offerLast(e)        │
  ├──────────────┼──────────────────────┼──────────────────────┤
  │  删除(异常)   │  removeFirst()       │  removeLast()        │
  │  删除(返回值)  │  pollFirst()         │  pollLast()          │
  ├──────────────┼──────────────────────┼──────────────────────┤
  │  查看(异常)   │  getFirst()          │  getLast()           │
  │  查看(返回值)  │  peekFirst()         │  peekLast()          │
  └──────────────┴──────────────────────┴──────────────────────┘

// ========== 用 ArrayDeque 替代 Stack ==========
 
// 创建一个"栈"
Deque<String> stack = new ArrayDeque<>();  // 推荐用 Deque 接口声明
 
// 入栈（push）—— 等价于 addFirst
stack.push("第一层");    // 底层调用 addFirst()
stack.push("第二层");    // 新元素压到栈顶
stack.push("第三层");    // 栈顶现在是"第三层"
 
// 查看栈顶（peek）—— 等价于 peekFirst
String top = stack.peek();               // 返回"第三层"，不移除
System.out.println("栈顶: " + top);      // 输出: 栈顶: 第三层
 
// 出栈（pop）—— 等价于 removeFirst
String popped = stack.pop();             // 移除并返回"第三层"
System.out.println("弹出: " + popped);   // 输出: 弹出: 第三层
 
// 此时栈内容: [第二层, 第一层]（从顶到底）
System.out.println("剩余大小: " + stack.size());  // 输出: 剩余大小: 2

// ========== 用 ArrayDeque 作为 FIFO 队列 ==========
 
Queue<String> queue = new ArrayDeque<>();  // 用 Queue 接口声明
 
// 入队（enqueue）—— 从尾部添加
queue.offer("任务A");    // 底层调用 offerLast()
queue.offer("任务B");    // 排在 A 后面
queue.offer("任务C");    // 排在 B 后面
 
// 查看队首
String front = queue.peek();              // 返回"任务A"，不移除
System.out.println("队首: " + front);     // 输出: 队首: 任务A
 
// 出队（dequeue）—— 从头部移除
String first = queue.poll();              // 移除并返回"任务A"
System.out.println("出队: " + first);     // 输出: 出队: 任务A
 
// 此时队列: [任务B, 任务C]
System.out.println("队列大小: " + queue.size());  // 输出: 队列大小: 2

  ArrayDeque 内存布局（连续数组）:
  ┌──────────────────────────────────────────────┐
  │  [ref0] [ref1] [ref2] [ref3] [ref4] [ref5]  │  ← 一块连续内存
  └──────────────────────────────────────────────┘
  CPU 预取 (prefetch) 可以一次性加载相邻元素到缓存行 (cache line)
 
  LinkedList 内存布局（散落的节点对象）:
  ┌──────────┐     ┌──────────┐     ┌──────────┐
  │ Node@A03 │────→│ Node@F71 │────→│ Node@2B9 │
  │ prev     │     │ prev     │     │ prev     │
  │ item     │     │ item     │     │ item     │
  │ next  ───┼────→│ next  ───┼────→│ next     │
  └──────────┘     └──────────┘     └──────────┘
    堆中随机位置       堆中随机位置       堆中随机位置
  每次访问下一个节点都可能触发 cache miss

public class BracketChecker {
 
    /**
     * 检查字符串中的括号是否匹配
     * 支持 (), [], {} 三种括号
     */
    public static boolean isValid(String s) {
        // 使用 ArrayDeque 作为栈
        Deque<Character> stack = new ArrayDeque<>();
 
        // 遍历字符串中的每个字符
        for (char c : s.toCharArray()) {
            // 遇到左括号，压入对应的右括号（技巧：方便后续直接比较）
            if (c == '(') {
                stack.push(')');          // 期望后续遇到 ')'
            } else if (c == '[') {
                stack.push(']');          // 期望后续遇到 ']'
            } else if (c == '{') {
                stack.push('}');          // 期望后续遇到 '}'
            } else {
                // 遇到右括号时：
                // 1. 栈为空 → 没有匹配的左括号 → 无效
                // 2. 栈顶不等于当前字符 → 括号类型不匹配 → 无效
                if (stack.isEmpty() || stack.pop() != c) {
                    return false;         // 不匹配，直接返回
                }
            }
        }
 
        // 遍历结束后，栈必须为空（所有左括号都被匹配了）
        return stack.isEmpty();
    }
 
    public static void main(String[] args) {
        System.out.println(isValid("({[]})"));   // true  —— 完美嵌套
        System.out.println(isValid("([)]"));     // false —— 交叉嵌套
        System.out.println(isValid("(("));       // false —— 左括号多余
    }
}

public class SlidingWindowMax {
 
    /**
     * 给定数组 nums 和窗口大小 k，返回每个窗口中的最大值
     * 使用单调递减队列（Monotonic Deque）实现 O(n) 时间复杂度
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];                    // 边界检查
        }
 
        int n = nums.length;                      // 数组长度
        int[] result = new int[n - k + 1];        // 结果数组，共有 n-k+1 个窗口
        // 双端队列存储的是索引（不是值），方便判断元素是否过期
        Deque<Integer> deque = new ArrayDeque<>();
 
        for (int i = 0; i < n; i++) {
            // 步骤1：移除队首过期元素（超出窗口范围）
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();                // 队首索引已不在窗口内，移除
            }
 
            // 步骤2：维护单调递减性 —— 移除队尾所有比当前元素小的索引
            // 因为这些元素不可能成为任何后续窗口的最大值
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();                 // 队尾元素比当前小，永远不会被选中
            }
 
            // 步骤3：将当前索引加入队尾
            deque.offerLast(i);
 
            // 步骤4：当窗口形成后（i >= k-1），记录结果
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()]; // 队首始终是窗口最大值
            }
        }
 
        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);
        // 输出: [3, 3, 5, 5, 6, 7]
        System.out.println(java.util.Arrays.toString(result));
    }
}

// 预估需要存储约 1000 个元素
// ArrayDeque 会自动向上取整到最近的 2 的幂次方，即 1024
Deque<String> deque = new ArrayDeque<>(1000);

Deque<String> deque = new ArrayDeque<>(List.of("A", "B", "C"));
 
// 错误示范：迭代时直接修改集合
for (String s : deque) {
    if ("B".equals(s)) {
        deque.remove(s);   // 抛出 ConcurrentModificationException!
    }
}
 
// 正确做法：使用迭代器的 remove 方法
Iterator<String> it = deque.iterator();  // 获取迭代器
while (it.hasNext()) {                   // 逐个遍历
    String s = it.next();                // 取出当前元素
    if ("B".equals(s)) {
        it.remove();                     // 通过迭代器安全移除
    }
}

// 当作栈使用 → 声明为 Deque
Deque<Integer> stack = new ArrayDeque<>();
 
// 当作普通队列使用 → 声明为 Queue
Queue<Integer> queue = new ArrayDeque<>();
 
// 需要双端操作 → 声明为 Deque
Deque<Integer> deque = new ArrayDeque<>();
 
// 不推荐：直接声明为 ArrayDeque（暴露了实现细节）
ArrayDeque<Integer> bad = new ArrayDeque<>();

Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(1);
deque.offerFirst(2);
deque.offerLast(3);
deque.offerFirst(4);
System.out.println(deque.pollLast());
System.out.println(deque.peekFirst());
System.out.println(deque.size());

// 错误示范：迭代器不保证有序
PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 3, 2, 4));
for (int val : pq) {
    // 输出顺序可能是 1, 2, 3, 5, 4 —— 并非严格升序！
    System.out.print(val + " ");
}
 
System.out.println();
 
// 正确做法：逐个 poll 才能得到有序序列
while (!pq.isEmpty()) {
    // 每次 poll 都会触发 siftDown，保证取出的是当前最小值
    System.out.print(pq.poll() + " "); // 输出：1 2 3 4 5
}

// ArrayDeque 循环数组的核心索引计算原理（简化示意）
// 假设数组长度为 8（二进制 1000），则 length - 1 = 7（二进制 0111）
int length = 8;
int mask = length - 1; // 0b0111 = 7
 
// 正向移动（tail 前进）
int tail = 5;
tail = (tail + 1) & mask; // (5+1) & 7 = 6 & 7 = 6  正常前进
tail = (tail + 1) & mask; // (6+1) & 7 = 7 & 7 = 7  到达末尾
tail = (tail + 1) & mask; // (7+1) & 7 = 8 & 7 = 0  自动绕回数组头部！
 
// 反向移动（head 后退）
int head = 1;
head = (head - 1) & mask; // (1-1) & 7 = 0 & 7 = 0  正常后退
head = (head - 1) & mask; // (0-1) & 7 = -1 & 7 = 7  自动绕回数组尾部！
// 这里 -1 的补码是全 1，与 0111 做 & 运算得到 0111 = 7

ArrayDeque<Integer> deque = new ArrayDeque<>();
deque.offer(1);      // 队尾入队
deque.offer(2);      // 队尾入队
deque.push(3);       // 栈顶压入（等价于 addFirst）
deque.offerFirst(4); // 队首入队
 
System.out.println(deque.poll());   // 第一次出队
System.out.println(deque.pop());    // 第一次弹栈
System.out.println(deque.peek());   // 查看队首
System.out.println(deque.peekLast());// 查看队尾