---

上篇：第五章、栈
下篇：第七章、树 — 基础篇

第六章 队列

在上一章中，我们深入学习了栈（Stack）——一种 “后进先出”（LIFO）的数据结构。栈像一摞盘子，后放上去的先取走。但生活中还有一种同样常见的场景：你在奶茶店排队点单，先来的人先点、先拿到奶茶离开——这就是队列（Queue），一种"先进先出"（FIFO，First In First Out）的受限线性结构。

如果说栈是计算机的 “记忆回溯”，那么队列就是计算机的 “时间线推进器”。从操作系统的任务调度、到消息中间件的缓冲池、再到图的广度优先搜索——队列以其简单优雅的 FIFO 原则支撑起了计算机系统的大半个世界。

---

6.1 队列的基本概念与 ADT 定义

6.1.1 什么是队列

队列（Queue）：是一种操作受限的线性表，只允许在表的一端进行插入（入队），在另一端进行删除（出队）。插入端称为队尾（Rear），删除端称为队头（Front）。

队列的核心操作：

• Enqueue（入队）：将元素放入队尾
• Dequeue（出队）：从队头移除元素并返回

此外通常还有一个辅助操作 Peek（窥视）：查看队头元素但不移除。

FIFO 原则：First In, First Out——最先入队的元素最先出队。就像排队买奶茶，先排队的人先买到先离开。

队列的抽象数据类型（ADT）定义如下：

ADT Queue {
数据对象：
D = { a i      ∣      0 ≤ i ≤ n − 1 ,    n ≥ 0 ,    a i 为 E 类型 } D=\left \{ a_{i} \;\;|\;\; 0 \le i \le n-1, \; n \ge 0, \; a_{i} 为 E 类型 \right \} D={ai​∣0≤i≤n−1,n≥0,ai​为E类型}
数据关系：
r = { < a i , a i + 1 >    ∣    a i ,    a i + 1 ∈ D ,    i = 0 , . . . , n − 2 } r=\left \{ <a_{i},a_{i+1}> \;|\; a_{i}, \; a_{i+1} \in D, \; i=0,...,n-2 \right \} r={<ai​,ai+1​>∣ai​,ai+1​∈D,i=0,...,n−2}
基本运算（7个）：
    Queue()：创建一个空队列
    void enqueue(E e)：将元素 e 加入队尾
    E dequeue()：移除并返回队头元素
    E peek()：返回队头元素但不移除
    boolean isEmpty()：判断队列是否为空
    int size()：返回队列中元素个数
    void clear()：清空队列中所有元素
}

---

6.2 顺序队列的手写实现

顺序队列使用数组作为底层存储，用 front 指针标记队头位置，rear 指针标记队尾的下一个空位。入队时元素放入 rear 位置并后移，出队时取出 front 位置并后移。

/**
 * 顺序队列（数组实现）
 * @param <E> 元素类型
 */
@SuppressWarnings("unchecked")
public class SeqQueue<E> {

    /** 默认初始容量 */
    private static final int DEFAULT_CAPACITY = 10;

    /** 底层存储数组 */
    private Object[] data;

    /** 队头指针，指向队头元素 */
    private int front;

    /** 队尾指针，指向队尾元素的下一个空位 */
    private int rear;

    /** 元素个数 */
    private int size;

    public SeqQueue() {
        data = new Object[DEFAULT_CAPACITY];
        front = 0;
        rear = 0;
        size = 0;
    }

    public SeqQueue(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("容量必须大于 0");
        }
        data = new Object[capacity];
        front = 0;
        rear = 0;
        size = 0;
    }

    /**
     * 入队
     * 时间复杂度 O(1)（均摊）
     */
    public void enqueue(E e) {
        // 如果数组已满，先扩容
        if (size == data.length) {
            ensureCapacity();
        }
        data[rear] = e;
        rear = (rear + 1) % data.length; // 循环使用数组
        size++;
    }

    /**
     * 出队
     * 时间复杂度 O(1)
     */
    public E dequeue() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("队列为空");
        }
        E value = (E) data[front];
        data[front] = null; // 帮助 GC
        front = (front + 1) % data.length;
        size--;
        return value;
    }

    /**
     * 查看队头元素（不移除）
     * 时间复杂度 O(1)
     */
    public E peek() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("队列为空");
        }
        return (E) data[front];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void clear() {
        for (int i = 0; i < data.length; i++) {
            data[i] = null;
        }
        front = 0;
        rear = 0;
        size = 0;
    }

    /**
     * 扩容：创建新数组，按顺序拷贝元素
     */
    private void ensureCapacity() {
        int newCap = data.length * 2;
        Object[] newData = new Object[newCap];
        // 从 front 开始，拷贝 size 个元素到新数组的起始位置
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % data.length];
        }
        data = newData;
        front = 0;
        rear = size;
    }
}

注意：上面的实现已经内置了循环使用数组的能力（rear = (rear + 1) % data.length），这其实就是循环队列的思想。如果不用取模运算，顺序队列会出现严重的"假溢出"问题——我们马上会详细讨论。

时间复杂度分析：

操作	时间复杂度	说明
enqueue(e)	O(1) 均摊	不扩容为 O(1)，扩容为 O(n)，均摊 O(1)
dequeue()	O(1)	仅移动 front 指针
peek()	O(1)	数组随机访问
isEmpty() / size()	O(1)	直接判断

---

6.3 链式队列的手写实现

链式队列使用链表作为底层存储。与链式栈不同——链式栈只用头部操作，但队列需要两头操作（队头出队、队尾入队），因此需要同时维护 head（队头）和 tail（队尾）两个指针。

/**
 * 链式队列（链表实现）
 * @param <E> 元素类型
 */
public class LinkedQueue<E> {

    /** 节点定义 */
    private static class Node<E> {
        E data;
        Node<E> next;

        Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    /** 队头指针 */
    private Node<E> head;

    /** 队尾指针 */
    private Node<E> tail;

    /** 元素个数 */
    private int size;

    /**
     * 入队（尾插法）
     * 时间复杂度 O(1)
     */
    public void enqueue(E e) {
        Node<E> newNode = new Node<>(e, null);
        if (isEmpty()) {
            // 空队列：head 和 tail 都指向新节点
            head = tail = newNode;
        } else {
            tail.next = newNode; // 原尾节点指向新节点
            tail = newNode;      // tail 后移
        }
        size++;
    }

    /**
     * 出队（头删法）
     * 时间复杂度 O(1)
     */
    public E dequeue() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("队列为空");
        }
        E value = head.data;
        head = head.next;
        size--;
        // 如果出队后队列为空，tail 也要置为 null
        if (isEmpty()) {
            tail = null;
        }
        return value;
    }

    /**
     * 查看队头元素
     * 时间复杂度 O(1)
     */
    public E peek() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("队列为空");
        }
        return head.data;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public int size() {
        return size;
    }

    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }
}

关键设计：用 head 指向队头（出队端），tail 指向队尾（入队端）。入队是 O(1) 的尾插，出队是 O(1) 的头删——两个指针缺一不可。如果只有 head 没有 tail，入队就需要遍历到尾部（O(n)），那就失去了队列的意义。

6.3.1 顺序队列 vs 链式队列

对比维度	顺序队列（循环数组）	链式队列（链表）
底层结构	数组（连续内存）	链表节点（非连续内存）
enqueue/dequeue	O(1) 均摊	O(1)
空间开销	可能预留多余空间	每个节点额外存储 next 指针
缓存友好性	高（连续内存）	低（节点分散）
动态扩容	需要拷贝数组（偶尔 O(n)）	每次 enqueue 创建新节点
适用场景	容量可预估，高频随机访问	容量不可预估，频繁增删

选型建议：

• 如果队列的最大容量可以预估或相对稳定 → 选择顺序队列（循环数组）
• 如果队列大小变化剧烈 → 选择链式队列
• 实际工程中，ArrayDeque（循环数组实现）在绝大多数场景性能更优

---

6.4 循环队列 — 解决假溢出问题

6.4.1 什么是假溢出

在普通的顺序队列中（不使用取模运算），当 rear 指针到达数组末尾时，即使数组前面还有空位（因为出队后 front 后移留下的空间），也无法继续入队——这种现象称为假溢出。

解决方案：让数组首尾相连，形成一个环。当 rear 到达数组末尾时，如果数组头部有空位，就让 rear 回到下标 0——这就是循环队列（Circular Queue）。

6.4.2 循环队列的核心原理

循环队列的关键操作全部依赖取模运算：

// 入队时 rear 后移
rear = (rear + 1) % capacity;

// 出队时 front 后移
front = (front + 1) % capacity;

判空与判满是循环队列的精髓。如果直接用 front == rear 判空，那么当队列满时也会出现 front == rear（绕了一圈追上），无法区分。

三种解决方案：

方案	思路	优缺点
浪费一个单元	当 (rear + 1) % cap == front 时认为队列满	实现简单，浪费一个位置
使用 size 字段	用 size == capacity 判满	不浪费空间，多维护一个变量
使用标志位	额外布尔变量标记最后一次操作是入队还是出队	不浪费空间，逻辑稍复杂

以下采用方案二（size 字段），最直观实用：

/**
 * 循环队列（数组实现 + size 判满）
 * @param <E> 元素类型
 */
@SuppressWarnings("unchecked")
public class CircularQueue<E> {

    /** 默认容量 */
    private static final int DEFAULT_CAPACITY = 8;

    /** 底层存储数组 */
    private final Object[] data;

    /** 队头指针 */
    private int front;

    /** 队尾指针（指向下一个空位） */
    private int rear;

    /** 当前元素个数 */
    private int size;

    /** 最大容量 */
    private final int capacity;

    public CircularQueue() {
        this(DEFAULT_CAPACITY);
    }

    public CircularQueue(int capacity) {
        if (capacity <= 1) {
            throw new IllegalArgumentException("容量必须大于 1");
        }
        this.capacity = capacity;
        this.data = new Object[capacity];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    /**
     * 入队
     * 时间复杂度 O(1)
     * @throws IllegalStateException 队列已满
     */
    public void enqueue(E e) {
        if (isFull()) {
            throw new IllegalStateException("队列已满（capacity=" + capacity + "）");
        }
        data[rear] = e;
        rear = (rear + 1) % capacity;
        size++;
    }

    /**
     * 出队
     * 时间复杂度 O(1)
     */
    public E dequeue() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("队列为空");
        }
        E value = (E) data[front];
        data[front] = null; // 帮助 GC
        front = (front + 1) % capacity;
        size--;
        return value;
    }

    /**
     * 查看队头元素
     * 时间复杂度 O(1)
     */
    public E peek() {
        if (isEmpty()) {
            throw new java.util.NoSuchElementException("队列为空");
        }
        return (E) data[front];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }

    public int size() {
        return size;
    }

    public void clear() {
        for (int i = 0; i < capacity; i++) {
            data[i] = null;
        }
        front = 0;
        rear = 0;
        size = 0;
    }

    @Override
    public String toString() {
        if (isEmpty()) return "[]";
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < size; i++) {
            sb.append(data[(front + i) % capacity]);
            if (i < size - 1) sb.append(", ");
        }
        return sb.append("]").toString();
    }
}

循环队列的本质：用取模运算将线性数组的首尾连接成一个逻辑上的环，使得出队后腾出的前端空间可以被复用。它是所有高性能队列（如 ArrayDeque、ArrayBlockingQueue）的底层核心机制。

---

6.5 Java 中的 Queue 接口体系

Java 的队列体系非常丰富，java.util.Queue 接口是 JCF（Java Collections Framework）的重要成员。

6.5.1 Queue 接口的方法设计

Queue 接口提供了两组方法——一组在操作失败时抛出异常，另一组返回特殊值（null/false）：

操作	抛出异常	返回特殊值
入队	add(e)	offer(e)
出队	remove()	poll()
查看队头	element()	peek()

// 抛出异常风格
Queue<String> q = new LinkedList<>();
q.add("A");           // 成功
String v1 = q.remove(); // 成功返回 "A"
String v2 = q.remove(); // 队列空 → 抛出 NoSuchElementException

// 返回特殊值风格
q.offer("B");          // 成功返回 true
String v3 = q.poll();  // 成功返回 "B"
String v4 = q.poll();  // 队列空 → 返回 null
String v5 = q.peek();  // 队列空 → 返回 null

最佳实践：日常开发中推荐使用 offer/poll/peek 三件套，避免不必要的异常处理。只有在确信队列不可能为空的情况下，才使用 add/remove/element。

6.5.2 Queue 接口的继承体系

java.lang.Iterable
    └── java.util.Collection
            └── java.util.Queue
                    ├── java.util.Deque（双端队列）
                    │       ├── ArrayDeque
                    │       └── LinkedList
                    ├── java.util.concurrent.BlockingQueue（阻塞队列）
                    │       ├── ArrayBlockingQueue
                    │       ├── LinkedBlockingQueue
                    │       └── PriorityBlockingQueue
                    └── java.util.AbstractQueue
                            └── PriorityQueue

6.5.3 LinkedList — 链表实现的队列

LinkedList 同时实现了 List 和 Deque 接口，因此它既可以当链表、也可以当队列、还可以当双端队列和栈使用。

/**
 * LinkedList 作为队列使用
 */
Queue<Integer> queue = new LinkedList<>();

// 入队
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println("队列: " + queue); // [1, 2, 3]

// 查看队头
System.out.println("队头: " + queue.peek()); // 1

// 出队
while (!queue.isEmpty()) {
    System.out.print(queue.poll() + " "); // 1 2 3
}

LinkedList 实现队列的优势在于底层是双向链表，入队出队均为 O(1)，且无容量限制。劣势是每个节点额外维护 prev 和 next 两个指针，内存开销大，缓存不友好。

6.5.4 ArrayDeque — 循环数组实现的队列

ArrayDeque 是 JDK 官方推荐的首选队列和栈实现。底层是循环数组，无容量限制（自动扩容），无锁开销，性能优异。

/**
 * ArrayDeque 作为队列使用 — 官方推荐
 */
Queue<Integer> queue = new ArrayDeque<>();

queue.offer(1);
queue.offer(2);
queue.offer(3);

System.out.println("队头: " + queue.peek()); // 1
System.out.println("出队: " + queue.poll()); // 1
System.out.println("剩余: " + queue);        // [2, 3]

ArrayDeque vs LinkedList 作为队列：

对比维度	ArrayDeque	LinkedList
底层实现	循环数组	双向链表
内存占用	紧凑（仅数组 + 头尾指针）	较大（每个节点 3 个引用）
缓存友好性	高	低
扩容开销	偶尔 O(n) 拷贝	无
入队/出队	O(1) 均摊	O(1)
null 元素	不允许	允许
适用场景	通用首选	需要频繁头尾增删且不关心缓存

结论：除非你需要存储 null 元素或同时对 List 特性有强需求，否则一律用 ArrayDeque。

6.5.5 PriorityQueue — 优先队列

PriorityQueue 是一个基于堆（Heap）的优先队列，它不遵循 FIFO 原则，而是每次出队都返回优先级最高的元素。

/**
 * PriorityQueue — 默认小顶堆
 */
PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.offer(5);
pq.offer(2);
pq.offer(8);
pq.offer(1);

// 出队顺序按自然排序：最小先出
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " "); // 1 2 5 8
}

/**
 * PriorityQueue — 自定义比较器（大顶堆）
 */
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(5);
maxHeap.offer(2);
maxHeap.offer(8);

System.out.println(maxHeap.poll()); // 8（最大先出）
System.out.println(maxHeap.poll()); // 5

操作	时间复杂度	说明
offer(e)	O(log n)	插入后上浮
poll()	O(log n)	移除堆顶后下沉
peek()	O(1)	直接返回堆顶
remove(Object)	O(n)	线性查找 + O(log n) 调整

PriorityQueue 是第 9 章"堆与优先队列"的主角，届时我们将手写堆并深度分析其源码。本章仅作概览。

队列实现	底层机制	顺序保证	容量限制	null 支持
LinkedList	双向链表	FIFO	无限制	允许
ArrayDeque	循环数组	FIFO	自动扩容	不允许
PriorityQueue	二叉堆	优先级	自动扩容	不允许
ArrayBlockingQueue	循环数组	FIFO	有界（固定）	不允许
LinkedBlockingQueue	单向链表	FIFO	可选有界	不允许

---

6.6 经典实战

6.6.1 用栈实现队列（LeetCode 232）

问题：使用两个栈实现一个队列，支持 push（入队）、pop（出队）、peek（查看队头）、empty（判空）。

核心思路：用两个栈——**输入栈（inStack）和输出栈（outStack）**协同工作。

• push 时：直接压入 inStack
• pop/peek 时：如果 outStack 为空，就把 inStack 中的所有元素依次弹出并压入 outStack（这样顺序就反过来了），然后从 outStack 弹出

/**
 * 用栈实现队列 — 双栈法
 * 时间复杂度：push O(1)，pop/peek 均摊 O(1)
 * 空间复杂度 O(n)
 */
public class MyQueue {

    private final Deque<Integer> inStack;  // 输入栈
    private final Deque<Integer> outStack; // 输出栈

    public MyQueue() {
        inStack = new ArrayDeque<>();
        outStack = new ArrayDeque<>();
    }

    /**
     * 入队 — 直接压入输入栈
     */
    public void push(int x) {
        inStack.push(x);
    }

    /**
     * 出队 — 如果输出栈为空，先倒入
     */
    public int pop() {
        pourIfNeeded();
        return outStack.pop();
    }

    /**
     * 查看队头 — 如果输出栈为空，先倒入
     */
    public int peek() {
        pourIfNeeded();
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    /**
     * 当输出栈为空时，将输入栈所有元素倒入输出栈
     */
    private void pourIfNeeded() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}

均摊分析：每个元素最多被 push 两次（一次进 inStack，一次进 outStack），最多被 pop 两次。所以 n 个元素的总操作次数 ≤ 4n，均摊 O(1)。

---

6.6.2 用队列实现栈（LeetCode 225）

问题：使用队列实现栈的 push、pop、top、empty 操作。

方法一：两个队列

核心思路：每次 push 新元素时，先放入一个临时队列，再把主队列中所有元素依次出队并追加到临时队列后面，最后交换引用。

/**
 * 用队列实现栈 — 双队列法
 * 时间复杂度：push O(n)，pop/peek O(1)
 */
public class MyStack_TwoQueues {

    private Queue<Integer> mainQueue;
    private Queue<Integer> tempQueue;

    public MyStack_TwoQueues() {
        mainQueue = new LinkedList<>();
        tempQueue = new LinkedList<>();
    }

    /**
     * 入栈：新元素放入 tempQueue，
     * 再把 mainQueue 中所有元素依次转入 tempQueue，
     * 最后交换引用
     */
    public void push(int x) {
        tempQueue.offer(x);
        while (!mainQueue.isEmpty()) {
            tempQueue.offer(mainQueue.poll());
        }
        // 交换引用
        Queue<Integer> swap = mainQueue;
        mainQueue = tempQueue;
        tempQueue = swap;
    }

    public int pop() {
        return mainQueue.poll();
    }

    public int top() {
        return mainQueue.peek();
    }

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

方法二：单个队列

核心思路：每次 push 新元素后，将队列中它之前的所有元素依次出队再入队（即"轮转"），让新元素跑到队头。

/**
 * 用队列实现栈 — 单队列法（更优雅）
 * 时间复杂度：push O(n)，pop/peek O(1)
 */
public class MyStack_SingleQueue {

    private final Queue<Integer> queue;

    public MyStack_SingleQueue() {
        queue = new LinkedList<>();
    }

    /**
     * 入栈：加入队尾后，将之前的所有元素轮转到队尾
     * 这样新元素就变到了队头（即栈顶）
     */
    public void push(int x) {
        int size = queue.size();
        queue.offer(x);
        // 将新元素之前的所有元素依次移到队尾
        for (int i = 0; i < size; i++) {
            queue.offer(queue.poll());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

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

两种实现对比：单队列法代码更简洁，但轮转次数和双队列法相同（都是 size 次）。push O(n) 是这类"用队列模拟栈"算法的固有代价——因为队列的 FIFO 特性与栈的 LIFO 特性本质矛盾。

---

6.6.3 滑动窗口最大值（LeetCode 239）— 单调队列

问题：给定数组 nums 和大小为 k 的滑动窗口，窗口从数组最左侧滑动到最右侧，返回每个窗口中的最大值。

核心思路：维护一个单调递减队列，队头始终是当前窗口的最大值。队列中存储的是下标（不是值），当队头下标滑出窗口范围时移除。

/**
 * 滑动窗口最大值 — 单调递减队列
 * 时间复杂度 O(n)，空间复杂度 O(k)
 * 每个元素最多入队一次、出队一次
 */
public 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++) {
        // 1. 移除窗口外的元素（队头下标 < i - k + 1）
        if (!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;
}

单调队列 vs 单调栈：单调栈解决的是"下一个更大/更小元素"（区间性质的查找），单调队列解决的是"滑动窗口内的最值"（带淘汰机制的区间维护）。队列在头部淘汰过期元素，栈在头部没有淘汰——这是二者最本质的区别。

---

6.6.4 BFS 广度优先搜索中的队列应用

BFS（Breadth-First Search，广度优先搜索）是队列最经典的应用场景。BFS 的核心思想是按层遍历——先访问距离起点为 1 的所有节点，然后是距离为 2 的，以此类推。

二叉树的层序遍历（LeetCode 102）

/**
 * 二叉树的层序遍历 — BFS + 队列
 * 时间复杂度 O(n)，空间复杂度 O(n)
 */
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // 当前层的节点数（关键！）
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);

            // 将下一层节点入队
            if (node.left != null)  queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

关键技巧：在每层开始处理前，用 levelSize = queue.size() 记录当前层的节点数。这样 for 循环只处理当前层的节点，新入队的子节点留到下一层处理。

图的 BFS — 岛屿数量（LeetCode 200）

/**
 * 岛屿数量 — BFS 解法
 * 时间复杂度 O(m × n)，空间复杂度 O(min(m, n))
 */
public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;

    int rows = grid.length;
    int cols = grid[0].length;
    int count = 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '1') {
                count++;
                // BFS 标记整个岛屿
                Queue<int[]> queue = new LinkedList<>();
                queue.offer(new int[]{i, j});
                grid[i][j] = '0'; // 标记已访问

                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    for (int[] dir : dirs) {
                        int nr = cell[0] + dir[0];
                        int nc = cell[1] + dir[1];
                        if (nr >= 0 && nr < rows
                                && nc >= 0 && nc < cols
                                && grid[nr][nc] == '1') {
                            queue.offer(new int[]{nr, nc});
                            grid[nr][nc] = '0'; // 标记已访问
                        }
                    }
                }
            }
        }
    }
    return count;
}

BFS 的核心模式：初始化队列（放入起点）→ 循环（出队一个节点，将其所有未访问的邻居入队）→ 直到队列为空。这个模式几乎适用于所有 BFS 问题。

---

6.7 双端队列（Deque）及其应用

6.7.1 Deque 接口

Deque（Double Ended Queue，双端队列）是 Queue 的子接口，允许在两端进行插入和删除。它可以同时扮演队列和栈的角色：

操作方向	方法（抛异常/返回特殊值）	等价于
队头入队	addFirst(e) / offerFirst(e)	—
队头出队	removeFirst() / pollFirst()	Queue 的 remove() / poll()
队头查看	getFirst() / peekFirst()	Queue 的 element() / peek()
队尾入队	addLast(e) / offerLast(e)	Queue 的 add(e) / offer(e)
队尾出队	removeLast() / pollLast()	—
队尾查看	getLast() / peekLast()	—
入栈	push(e)（等价于 addFirst）	Stack 的 push
出栈	pop()（等价于 removeFirst）	Stack 的 pop
窥栈	peek()（等价于 peekFirst）	Stack 的 peek

/**
 * Deque 的多种身份演示
 */
public class DequeDemo {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        // === 作为双端队列 ===
        deque.offerFirst(1);  // 队头入: [1]
        deque.offerLast(2);   // 队尾入: [1, 2]
        deque.offerFirst(0);  // 队头入: [0, 1, 2]
        System.out.println("双端队列: " + deque); // [0, 1, 2]

        System.out.println("队头出: " + deque.pollFirst()); // 0
        System.out.println("队尾出: " + deque.pollLast());  // 2

        // === 作为栈 ===
        deque.push(10);  // 入栈: [10, 1]
        deque.push(20);  // 入栈: [20, 10, 1]
        System.out.println("栈顶: " + deque.peek()); // 20
        System.out.println("出栈: " + deque.pop());  // 20

        // === 作为队列 ===
        deque.offer(100); // 入队: [10, 1, 100]
        System.out.println("队头: " + deque.peek()); // 10
        System.out.println("出队: " + deque.poll()); // 10
    }
}

6.7.2 双端队列的经典应用

回文检测（双端队列两端同时比较）

/**
 * 使用 Deque 检测回文字符串
 * 时间复杂度 O(n)，空间复杂度 O(n)
 */
public boolean isPalindrome(String s) {
    Deque<Character> deque = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        deque.offerLast(c);
    }
    while (deque.size() > 1) {
        // 队头和队尾同时取出比较
        if (deque.pollFirst() != deque.pollLast()) {
            return false;
        }
    }
    return true;
}

LRU 缓存的近似实现（Deque 维护访问顺序）

/**
 * 使用 LinkedHashMap 实现简单的 LRU（其后是 Deque 的思想）
 * LinkedHashMap 底层用双向链表维护插入/访问顺序
 */
public class SimpleLRU<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public SimpleLRU(int capacity) {
        // accessOrder=true 按访问顺序排序
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

LinkedHashMap 的访问顺序链表本质上就是一个双端队列——最近访问的元素移到队尾，最老的元素在队头。当容量超限时，从队头移除。

---

总结与预告

本章我们从队列的 FIFO 特性出发，深入讲解了顺序队列和链式队列的手写实现。循环队列解决了顺序队列中最棘手的"假溢出"问题——它用取模运算将数组首尾相连，是 ArrayDeque 等高性能实现的基石。

在 Java 标准库部分，我们梳理了庞大的 Queue 接口体系：LinkedList 和 ArrayDeque 作为通用队列，PriorityQueue 作为优先级队列。核心结论是——日常开发优先使用 ArrayDeque。

经典实战部分，双栈实现队列和单队列实现栈展示了栈与队列之间的奇妙转换关系；单调队列在线性时间内解决了滑动窗口最值问题；BFS 则让队列在图的层序遍历中大放异彩。最后，双端队列 Deque 将队列的能力拓展到两端操作，成为 Java 集合框架中最通用的线性容器之一。

核心收获：队列是 FIFO 原则的化身，从 CPU 任务调度到消息队列中间件，从 BFS 到滑动窗口——队列以其简单优雅的"先来先服务"哲学，支撑起了计算机系统的"时间秩序"。理解队列，就是理解系统如何管理"等待"的艺术。

下一章我们将正式进入非线性数据结构的世界，迎来第一棵"树"——二叉树。我们将学习树的递归定义、四种遍历方式（前序/中序/后序/层序）、二叉树的存储与构建，以及 Morris 遍历等高级技巧。

---

上篇：第五章、栈
下篇：第七章、树 — 基础篇