本文还有配套的精品资源，点击获取

简介：数据结构与算法是IT领域的编程基石，直接影响程序性能与优化能力。本资源“数据结构与算法代码详解JAVA版”系统讲解了使用Java语言实现各类核心数据结构与经典算法的方法。涵盖数组、链表、栈、队列、树、图、哈希表等数据结构，以及排序、查找、最短路径、动态规划、贪心算法等关键算法，并通过“AlgorithmPresentation”文件提供可运行的Java代码示例，帮助读者深入理解其工作原理并应用于实际开发中。该资源适合各阶段开发者学习与实践，助力提升编程能力、面试表现和问题解决效率。

1. 数据结构基础概述与Java实现

数据结构的基本概念与分类

数据结构是程序设计中组织、存储和管理数据的方式，直接影响算法效率与系统性能。从逻辑结构角度看，数据结构可分为线性结构（如数组、链表）和非线性结构（如树、图）；从物理存储角度，则涉及顺序存储（连续内存）与链式存储（分散内存通过引用连接）。Java通过对象引用机制天然支持复杂数据结构的构建，结合泛型（ <T> ）可实现类型安全的通用容器。

// 示例：泛型节点类体现ADT思想
public class Node<T> {
    T data;
    Node<T> next;
    public Node(T data) {
        this.data = data;
    }
}

该设计体现了抽象数据类型（ADT）的核心理念——将数据与操作封装，为后续集合框架（如 ArrayList 基于动态数组， LinkedList 基于双向链表）提供实现基础。理解这些概念是掌握高效编程的关键第一步。

2. 数组与链表的设计与操作

在现代编程实践中，数据结构的选择直接决定了程序的性能表现和可维护性。作为最基础、最常用的两种线性数据结构， 数组 与 链表 构成了几乎所有高级数据结构的底层支撑。它们虽然都用于存储有序元素集合，但在内存布局、访问方式、插入删除效率等方面存在本质差异。理解这些差异并掌握其Java实现机制，是构建高效算法系统的关键一步。

本章将深入剖析数组与链表的设计原理，从理论到实践全面展开。首先探讨数组的连续内存特性及其对访问速度的影响，分析静态与动态数组的本质区别；随后进入链表世界，详细讲解单向链表、双向链表以及循环链表的节点设计与引用链接逻辑；接着通过时间复杂度实测与缓存局部性分析，对比两者在不同场景下的性能优劣；最后以一个完整的学生信息管理系统为案例，展示如何根据实际需求选择合适的数据结构进行工程化实现。

2.1 数组的理论基础与内存布局

数组是一种具有固定大小（或可扩展）的线性数据结构，其核心特征在于所有元素在内存中 连续存放 。这种物理上的连续性带来了极高的随机访问效率，但也限制了它的动态扩展能力。在Java中，数组不仅是语言内置的基本类型之一，更是 ArrayList 、 StringBuilder 等常用容器类的底层实现基础。

2.1.1 静态数组与动态数组的概念辨析

“静态数组”通常指在编译期就确定长度且运行期间不可更改的数组，而“动态数组”则允许在运行时自动扩容。尽管Java中所有数组在创建后长度固定，但开发者可以通过封装机制模拟出动态行为，例如 java.util.ArrayList 正是基于此思想构建。

特性	静态数组	动态数组
内存分配时机	编译/运行初期	运行期按需分配
长度变化	不可变	可自动增长
访问效率	O(1)	O(1)
插入/删除效率	O(n)	O(n)，扩容时额外开销
典型实现	Java原生 int[] arr = new int[10]	ArrayList<E>

从上表可以看出，动态数组本质上是对静态数组的封装增强。当内部数组空间不足时，会创建一个更大的新数组，并将旧数据复制过去——这一过程称为 扩容（Resizing） 。

下面是一个简化版动态整型数组的Java实现：

public class DynamicArray {
    private int[] data;
    private int size;         // 当前元素个数
    private int capacity;     // 当前容量

    public DynamicArray(int initialCapacity) {
        this.capacity = initialCapacity;
        this.data = new int[capacity];
        this.size = 0;
    }

    // 添加元素
    public void add(int value) {
        if (size == capacity) {
            resize();  // 扩容
        }
        data[size++] = value;
    }

    // 获取指定索引元素
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index);
        }
        return data[index];
    }

    // 修改指定位置元素
    public void set(int index, int value) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index);
        }
        data[index] = value;
    }

    // 移除最后一个元素
    public int remove() {
        if (size == 0) {
            throw new IllegalStateException("Array is empty");
        }
        return data[--size];
    }

    // 扩容逻辑：容量翻倍
    private void resize() {
        capacity *= 2;
        int[] newData = new int[capacity];
        System.arraycopy(data, 0, newData, 0, size);  // 复制原有数据
        data = newData;
    }

    public int size() { return size; }
    public int capacity() { return capacity; }
}

代码逻辑逐行解读：

• 第3–7行 ：定义私有字段，包括存储数据的数组 data 、当前元素数量 size 和最大容量 capacity 。
• 第9–13行 ：构造函数初始化数组，默认容量由用户传入。
• 第16–20行 ： add() 方法检查是否需要扩容，若已满则调用 resize() ，然后添加元素并递增 size 。
• 第23–28行 ： get() 方法进行边界检查，防止越界访问。
• 第31–36行 ： set() 支持修改已有位置的值，同样做范围校验。
• 第39–44行 ： remove() 仅支持尾部删除（常用于栈结构），简单递减 size 即可。
• 第47–51行 ： resize() 采用两倍扩容策略，使用 System.arraycopy() 高效迁移数据。
• 第53–54行 ：提供公共接口获取当前状态。

⚠️ 注意：虽然 System.arraycopy() 是本地方法（native），性能较高，但频繁扩容仍会导致O(n)级别的摊还成本。一般建议预估初始容量以减少重分配次数。

2.1.2 连续内存分配原理及其访问效率分析

数组之所以能实现O(1)时间复杂度的随机访问，根本原因在于其 连续内存布局 和 地址计算公式 。

假设数组起始地址为 baseAddress ，每个元素占用 elementSize 字节，则第 i 个元素的物理地址可通过如下公式快速定位：
\text{Address}[i] = \text{baseAddress} + i \times \text{elementSize}

这个计算过程只需要一次乘法和一次加法，在CPU层面几乎瞬时完成，无需遍历。

graph LR
    A[Base Address: 0x1000] --> B["Index 0 → 0x1000 + 0×4 = 0x1000"]
    A --> C["Index 1 → 0x1000 + 1×4 = 0x1004"]
    A --> D["Index 2 → 0x1000 + 2×4 = 0x1008"]
    A --> E["Index 3 → 0x1000 + 3×4 = 0x100C"]
    style A fill:#f9f,stroke:#333
    style B fill:#bbf,stroke:#333,color:#fff
    style C fill:#bbf,stroke:#333,color:#fff
    style D fill:#bbf,stroke:#333,color:#fff
    style E fill:#bbf,stroke:#333,color:#fff

如上图所示，对于一个 int[4] 类型的数组（每个int占4字节），只要知道起始地址，就可以通过简单的算术运算直接跳转到任意元素位置。

相比之下，链表由于节点分散在堆内存各处，必须从头节点开始逐个遍历指针才能到达目标位置，因此访问时间为O(n)。

此外，连续内存还带来显著的 缓存局部性优势 。现代CPU利用多级缓存（L1/L2/L3）来加速内存访问。当程序读取某个数组元素时，相邻元素也会被预加载进缓存行（Cache Line，通常64字节）。这意味着后续访问 nearby 元素几乎不产生额外延迟，极大提升了批量处理效率。

例如，以下循环遍历数组的操作具有良好的空间局部性：

int sum = 0;
for (int i = 0; i < arr.length; i++) {
    sum += arr[i];  // 高概率命中缓存
}

而链表遍历则可能频繁触发缓存未命中（Cache Miss），因为节点地址不连续，无法有效利用预取机制。

2.1.3 Java中数组的声明、初始化与边界检查机制

Java中的数组属于对象类型，即使基本类型数组（如 int[] ）也继承自 Object 类。这使得数组具备垃圾回收、类型检查等特性。

声明与初始化方式

Java支持多种数组声明语法：

// 方式一：先声明后初始化
int[] arr1;
arr1 = new int[5];

// 方式二：声明同时初始化（指定长度）
int[] arr2 = new int[10];

// 方式三：声明并赋初值（隐式长度）
int[] arr3 = {1, 2, 3, 4, 5};

// 方式四：匿名数组
printArray(new int[]{6, 7, 8});

void printArray(int[] a) {
    for (int x : a) System.out.println(x);
}

其中，第三种写法 {} 只能在声明时使用，不能用于后续赋值。

多维数组的特殊性

Java中的多维数组实际上是“数组的数组”，并非真正的矩形结构。例如二维数组：

int[][] matrix = new int[3][4];  // 3行4列的规则矩阵

// 也可以是非规则的“锯齿数组”
int[][] jagged = {
    {1, 2},
    {3, 4, 5},
    {6}
};

每行可以独立分配，灵活性高但失去严格的行列一致性。

边界检查机制

Java虚拟机在运行时会对所有数组访问执行 边界检查 ，确保不会发生缓冲区溢出。例如：

int[] arr = new int[5];
System.out.println(arr[5]);  // 抛出 ArrayIndexOutOfBoundsException

JVM会在每次访问前插入类似如下伪代码的判断：

if (index < 0 || index >= array.length)
    throw new ArrayIndexOutOfBoundsException();

虽然这带来轻微性能开销，但极大地增强了安全性，避免了C/C++中常见的内存破坏问题。

此外，Java还提供了 Arrays 工具类用于常见操作：

import java.util.Arrays;

int[] nums = {5, 2, 8, 1};
Arrays.sort(nums);           // 排序: [1,2,5,8]
Arrays.fill(nums, 0);        // 填充: [0,0,0,0]
boolean equals = Arrays.equals(nums, new int[]{0,0,0,0});  // true
String str = Arrays.toString(nums);  // "[0, 0, 0, 0]"

这些方法封装了底层循环逻辑，提升开发效率的同时保证了正确性。

2.2 单向链表与双向链表的Java实现

链表是一种非连续存储的线性结构，通过节点间的引用链接形成逻辑序列。与数组相比，它牺牲了随机访问能力，换来了高效的插入与删除操作。特别是在频繁修改的场景下，链表表现出更强的适应性。

2.2.1 节点类的设计与引用链接机制

链表的核心是 节点（Node） ，每个节点包含两部分：数据域和指针域。以单向链表为例：

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

• val 存储实际数据；
• next 指向下一个节点，末尾节点的 next 为 null 。

整个链表仅需保存头节点引用即可访问全部元素：

graph LR
    H((Head)) --> N1[Node(1)]
    N1 --> N2[Node(2)]
    N2 --> N3[Node(3)]
    N3 --> null

双向链表在此基础上增加前驱指针：

class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;

    public DoublyListNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

结构示意如下：

graph LR
    H((Head)) --> N1[Node(1)]
    N1 <--> N2[Node(2)]
    N2 <--> N3[Node(3)]
    N3 --> T((Tail))

双向链表支持双向遍历，便于实现Deque等结构，但占用更多内存且维护更复杂。

2.2.2 插入、删除、查找操作的核心逻辑编码

以下实现一个完整的单向链表类，包含增删查功能：

public class SinglyLinkedList {
    private ListNode head;
    private int size;

    public SinglyLinkedList() {
        this.head = null;
        this.size = 0;
    }

    // 头插法
    public void addFirst(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
        size++;
    }

    // 尾插法
    public void addLast(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
        } else {
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    // 指定位置插入
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException();
        }
        if (index == 0) {
            addFirst(val);
            return;
        }
        ListNode newNode = new ListNode(val);
        ListNode current = head;
        for (int i = 0; i < index - 1; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
        size++;
    }

    // 删除头节点
    public int removeFirst() {
        if (head == null) throw new IllegalStateException("Empty list");
        int val = head.val;
        head = head.next;
        size--;
        return val;
    }

    // 查找值是否存在
    public boolean contains(int val) {
        ListNode current = head;
        while (current != null) {
            if (current.val == val) return true;
            current = current.next;
        }
        return false;
    }

    // 获取指定索引值
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
        ListNode current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.val;
    }

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

关键操作说明：

• 头插法 addFirst ：时间复杂度O(1)，只需更新 newNode.next 和 head 。
• 尾插法 addLast ：需遍历至末尾，时间复杂度O(n)。
• 按索引插入 ：先找到前一个节点，再调整指针，注意边界处理。
• 删除操作 ：Java依赖GC自动回收无引用对象，无需手动释放内存。
• 查找操作 ：必须逐个遍历，平均时间O(n)。

2.2.3 循环链表与双向循环链表的扩展实现

循环链表的特点是最后一个节点指向头节点，形成闭环，适用于周期性任务调度等场景。

public class CircularLinkedList {
    private ListNode head;
    private int size;

    public void addToTail(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
            head.next = head;  // 自环
        } else {
            ListNode tail = head;
            while (tail.next != head) {
                tail = tail.next;
            }
            tail.next = newNode;
            newNode.next = head;
        }
        size++;
    }

    public void traverse(int count) {
        if (head == null) return;
        ListNode curr = head;
        for (int i = 0; i < count; i++) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

双向循环链表结合了双向与循环特性，常用于实现LRU缓存：

class Node {
    int key, val;
    Node prev, next;
    Node(int k, int v) { key = k; val = v; }
}

class DoublyCircularList {
    private Node sentinel;

    public DoublyCircularList() {
        sentinel = new Node(-1, -1);
        sentinel.next = sentinel;
        sentinel.prev = sentinel;
    }

    public void addFirst(Node node) {
        node.next = sentinel.next;
        node.prev = sentinel;
        sentinel.next.prev = node;
        sentinel.next = node;
    }

    public void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

该结构可在O(1)时间内完成任意节点的插入与删除，是 LinkedHashMap 实现LRU的核心机制。

2.3 数组与链表的操作性能对比

2.3.1 时间复杂度在不同场景下的实测分析

操作	数组（静态）	ArrayList（动态数组）	单向链表
访问 get(i)	O(1)	O(1)	O(n)
头部插入 add(0,x)	O(n)	O(n)	O(1)
尾部插入 add(x)	O(1)	摊还O(1)	O(n)
中间插入 add(i,x)	O(n)	O(n)	O(n)
删除 remove(i)	O(n)	O(n)	O(n)
内存占用	紧凑	略高（预留空间）	高（含指针）

测试代码示例（测量尾部插入10万次耗时）：

long start = System.nanoTime();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 100_000; i++) {
    list.add(i);
}
long time = System.nanoTime() - start;
System.out.println("ArrayList add time: " + time / 1e6 + " ms");

结果显示，在合理初始容量下， ArrayList 接近线性增长；而链表在频繁头部插入时优势明显。

2.3.2 内存使用效率与缓存局部性的影响

数组因连续存储，单位元素开销最小。链表每个节点额外携带1~2个引用（8或16字节），空间利用率低。

更重要的是 缓存命中率 。实验表明，在大规模顺序访问中，数组性能通常是链表的3~5倍，主因即为缓存友好性。

2.4 实践案例：基于数组与链表的学生信息管理系统

（略，保留至下一章节输出）

3. 栈与队列的Java实现（LIFO与FIFO）

在计算机科学中，栈（Stack）与队列（Queue）是两种最基础且应用广泛的数据结构。它们分别遵循后进先出（LIFO, Last In First Out）和先进先出（FIFO, First In First Out）的原则，构成了许多复杂算法与系统机制的核心组件。无论是函数调用堆栈、表达式求值、括号匹配，还是任务调度、消息传递、广度优先搜索等场景，都离不开栈与队列的支持。本章将深入剖析这两种结构的抽象定义、存储实现方式及其在Java中的具体编码实践，并通过多种扩展形式如最小栈、双端队列、循环队列等展示其灵活性与实用性。

3.1 栈的抽象定义与应用场景

栈是一种受限的线性数据结构，只允许在一端进行插入（push）和删除（pop）操作，这一端被称为“栈顶”（Top），而另一端称为“栈底”。由于所有操作均集中于栈顶，因此新元素总是位于最上方，最早进入的元素被压在底部，只有当上面的所有元素都被弹出后才能访问到底部元素——这正是LIFO原则的本质体现。

3.1.1 后进先出（LIFO）原则的数学描述

从集合论的角度来看，栈可以被形式化地定义为一个有序对 $ S = (D, f) $，其中 $ D $ 是元素的有限集合，$ f $ 表示一种偏序关系，满足：对于任意两个元素 $ a, b \in D $，若 $ a $ 在 $ b $ 之后入栈，则 $ a <_f b $ 不成立，即 $ a $ 的访问优先级高于 $ b $。这种偏序关系决定了出栈顺序必须严格逆于入栈顺序。

更直观地说，设有一个入栈序列 $ I = [x_1, x_2, …, x_n] $，则合法的出栈序列 $ O $ 必须满足以下条件：
- 对任意 $ i < j < k $，若 $ x_i < x_k < x_j $，则 $ x_k $ 不可能出现在 $ x_j $ 之前但 $ x_i $ 之后（经典栈排列约束）。
该性质可用于判断某个排列是否可通过单一栈生成，常用于面试题或编译器中间代码优化分析。

下面以一个简单的例子说明：

import java.util.Stack;

public class LIFOExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        while (!stack.isEmpty()) {
            System.out.println(stack.pop()); // 输出：3 → 2 → 1
        }
    }
}

逻辑分析与参数说明：
- Stack<Integer> 使用泛型确保类型安全，避免强制转换错误；
- push() 方法将元素添加到栈顶，时间复杂度为 $O(1)$；
- pop() 移除并返回栈顶元素，若栈为空则抛出 EmptyStackException ；
- isEmpty() 判断栈是否为空，防止非法操作；
- 整个程序体现了典型的 LIFO 特性：最后压入的 3 最先输出。

此例虽简单，却揭示了栈的核心行为模型：所有操作集中在单一端点，形成严格的反向输出流。

3.1.2 基于数组与链表的两种栈实现方式

尽管 Java 提供了内置的 java.util.Stack 类，但它继承自过时的 Vector ，存在同步开销，不推荐在高并发环境下使用。更优的做法是自行封装基于数组或链表的栈结构，以获得更好的性能控制与内存效率。

数组实现栈（固定容量）

public class ArrayStack<T> {
    private T[] data;
    private int top;
    private int capacity;

    @SuppressWarnings("unchecked")
    public ArrayStack(int initialCapacity) {
        this.capacity = initialCapacity;
        this.data = (T[]) new Object[capacity];
        this.top = -1;
    }

    public void push(T item) {
        if (isFull()) throw new RuntimeException("Stack Overflow");
        data[++top] = item;
    }

    public T pop() {
        if (isEmpty()) throw new RuntimeException("Stack Underflow");
        return data[top--];
    }

    public T peek() {
        if (isEmpty()) return null;
        return data[top];
    }

    public boolean isEmpty() { return top == -1; }
    public boolean isFull() { return top == capacity - 1; }
    public int size() { return top + 1; }
}

逐行解读分析：
- 第4~6行：定义内部数组 data 存储元素， top 指针指向当前栈顶索引，初始为-1表示空栈；
- 第9行：构造函数接受初始容量，创建泛型数组需强制转型并抑制警告；
- 第15行： push() 先检查是否满栈，再递增指针并赋值，保证原子性；
- 第20行： pop() 返回当前元素后递减指针，模拟“弹出”动作；
- 第25行： peek() 仅查看栈顶值而不移除，适合预览操作；
- 时间复杂度： push , pop , peek 均为 $O(1)$；空间复杂度为 $O(n)$。

链表实现栈（动态扩容）

public class LinkedStack<T> {
    private Node<T> head;
    private int size;

    private static class Node<T> {
        T data;
        Node<T> next;
        Node(T data) { this.data = data; }
    }

    public void push(T item) {
        Node<T> newNode = new Node<>(item);
        newNode.next = head;
        head = newNode;
        size++;
    }

    public T pop() {
        if (head == null) throw new RuntimeException("Stack Underflow");
        T data = head.data;
        head = head.next;
        size--;
        return data;
    }

    public T peek() {
        return head == null ? null : head.data;
    }

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

逻辑分析与参数说明：
- 内部类 Node 封装数据与指针，构成单向链表节点；
- push() 将新节点指向原头节点，并更新头指针，相当于在链表头部插入；
- pop() 保存旧头数据后将其跳过，完成删除；
- 无需预分配空间，天然支持动态增长，适合不确定数据量的场景；
- 缺点是每个节点额外占用引用空间（约8字节），相比数组略耗内存。

实现方式	时间复杂度（push/pop）	空间效率	扩展能力	适用场景
数组	$O(1)$	高	固定容量，可扩容	元素数量已知、追求缓存友好
链表	$O(1)$	中	动态无限	数据量未知、频繁增删

3.1.3 栈溢出与下溢的异常处理策略

在实际开发中，必须妥善处理栈的边界情况。常见的异常包括：

• 栈溢出（Stack Overflow） ：当栈已满仍尝试 push ，通常发生在数组实现中；
• 栈下溢（Stack Underflow） ：空栈执行 pop 或 peek ，导致非法访问。

异常处理设计对比表

处理方式	描述	优点	缺点
抛出运行时异常	如 RuntimeException ，便于调试	简洁、符合JVM习惯	可能中断程序流程
返回特殊值	如 null 或布尔标志	不打断调用链	易引发空指针，语义模糊
使用 Optional	Optional<T> pop()	类型安全、显式处理缺失值	增加调用复杂度
自定义异常类	继承 Exception ，提供详细上下文信息	可追溯、利于日志记录	需额外维护异常体系

推荐做法是在关键业务逻辑中采用自定义异常，例如：

public class StackOverflowException extends RuntimeException {
    public StackOverflowException(String message) {
        super(message);
    }
}

// 在 push 中调用：
if (isFull()) throw new StackOverflowException("Maximum capacity reached: " + capacity);

此外，在 JVM 层面，“栈溢出”也指线程调用栈过深导致的 java.lang.StackOverflowError ，常见于无限递归。此类错误无法捕获，只能通过优化递归逻辑或增大 -Xss 参数缓解。

3.2 队列的结构特性与Java编码实现

队列是另一种重要的线性结构，强调数据按到达顺序处理，即先进先出（FIFO）。它广泛应用于多线程任务调度、打印服务、消息中间件、BFS 图遍历等场景。与栈不同，队列的操作分布在两端：一端用于入队（enqueue），称为“队尾”（rear）；另一端用于出队（dequeue），称为“队首”（front）。

3.2.1 先进先出（FIFO）机制的模拟与优化

最基本的队列可以用数组或链表实现。以下是基于数组的简单队列实现：

public class ArrayQueue<T> {
    private T[] data;
    private int front, rear, size, capacity;

    @SuppressWarnings("unchecked")
    public ArrayQueue(int cap) {
        capacity = cap;
        data = (T[]) new Object[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    public void enqueue(T item) {
        if (isFull()) throw new RuntimeException("Queue is full");
        rear = (rear + 1) % capacity; // 循环利用
        data[rear] = item;
        size++;
    }

    public T dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        T value = data[front];
        front = (front + 1) % capacity;
        size--;
        return value;
    }

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

代码逻辑分析：
- 使用模运算 (rear + 1) % capacity 实现逻辑上的“循环移动”，避免数组空间浪费；
- front 和 rear 指针共同维护有效区域， size 辅助判断满/空状态；
- 所有操作均为 $O(1)$，具备良好性能表现。

graph LR
    A[Enqueue A] --> B[Enqueue B]
    B --> C[Enqueue C]
    C --> D[Dequeue → A]
    D --> E[Dequeue → B]
    style A fill:#eef,stroke:#69f
    style B fill:#eef,stroke:#69f
    style C fill:#eef,stroke:#69f
    style D fill:#fee,stroke:#f66
    style E fill:#fee,stroke:#f66

上图展示了 FIFO 行为流程：A 最先进入，最先离开；C 最晚进入，最后离开。

3.2.2 循环队列的设计避免假溢出问题

传统顺序队列存在“假溢出”问题：即使数组未满，但由于 rear 已达末尾而无法继续插入。解决方法是采用 循环队列 （Circular Queue），通过取模操作使指针回绕。

关键设计要点：

• 判空条件： front == rear
• 判满条件： (rear + 1) % capacity == front
• 注意：牺牲一个单元空间以区分满与空状态

public boolean isFull() {
    return (rear + 1) % capacity == front;
}

public boolean isEmpty() {
    return front == rear;
}

这种方式使得空间利用率接近 100%，非常适合嵌入式系统或资源受限环境。

3.2.3 双端队列（Deque）的接口扩展与实现

双端队列（Double-ended Queue）允许在两端进行插入和删除操作，兼具栈与队列的功能。Java 提供了 Deque 接口，常用实现有 ArrayDeque 和 LinkedList 。

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

public class DequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        deque.offerFirst("A"); // ← A
        deque.offerLast("B");  // ← A → B
        deque.offerFirst("C"); // ← C → A → B

        System.out.println(deque.pollLast()); // B
        System.out.println(deque.pollFirst()); // C
        System.out.println(deque.peekFirst()); // A
    }
}

操作方法	方向	等效结构
offerFirst()	队首入队	栈 push
pollLast()	队尾出队	栈 pop
offerLast()	队尾入队	队列入队
pollFirst()	队首出队	队列出队

这表明 Deque 是通用容器，可用于模拟栈或普通队列，具有极高灵活性。

3.3 特殊栈与队列的应用实践

3.3.1 最小栈（Min Stack）的设计思路与代码实现

最小栈要求在常数时间内获取当前栈中的最小元素。直接遍历显然效率低下（$O(n)$），需借助辅助结构。

解法一：双栈法（主栈 + 辅助栈）

import java.util.Stack;

public class MinStack {
    private Stack<Integer> mainStack;
    private Stack<Integer> minStack;

    public MinStack() {
        mainStack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int val) {
        mainStack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (mainStack.isEmpty()) return;
        int val = mainStack.pop();
        if (val == minStack.peek()) {
            minStack.pop();
        }
    }

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

    public int getMin() {
        return minStack.peek();
    }
}

参数说明与逻辑分析：
- mainStack 存储原始数据；
- minStack 仅保存递减序列的候选最小值；
- push() 时若新值 ≤ 当前最小值，则同步压入 minStack ；
- pop() 时若弹出的是最小值，则 minStack 也同步弹出；
- 所有操作保持 $O(1)$ 时间复杂度，空间复杂度最坏为 $O(n)$。

3.3.2 用栈模拟队列与用队列模拟栈的互转技巧

用两个栈模拟队列（LeetCode #232）

public class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

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

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.peek();
    }

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

核心思想：
- 所有入队操作进入 inStack ；
- 出队时，若 outStack 为空，则将 inStack 全部倒入 outStack ，实现反转；
- 此操作摊还时间复杂度为 $O(1)$。

flowchart TD
    A[Push 1,2,3] --> B[inStack: [3,2,1]]
    B --> C{Pop?}
    C -- Yes --> D[Transfer to outStack]
    D --> E[outStack: [1,2,3]]
    E --> F[Pop → 1]

同理，可用两个队列模拟栈，原理类似：始终保持一个队列为空，入栈时放入非空队列，出栈时将前 $n-1$ 个元素转移到另一个队列，留下最后一个作为栈顶。

3.4 综合应用：表达式求值中的栈运用

3.4.1 中缀转后缀表达式的算法流程

中缀表达式（如 3 + 4 * 2 ）含有运算符优先级和括号，难以直接计算。后缀表达式（逆波兰表示法）无歧义，可直接用栈求值。

转换规则（Dijkstra 调度场算法）：

1. 遍历中缀表达式；
2. 操作数直接输出；
3. 运算符按优先级压栈，低优先级入栈前弹出高优先级；
4. 左括号入栈，右括号触发弹出直到遇到左括号；
5. 结束后弹出剩余运算符。

import java.util.*;

public class InfixToPostfix {
    private Map<Character, Integer> precedence;

    public InfixToPostfix() {
        precedence = new HashMap<>();
        precedence.put('+', 1); precedence.put('-', 1);
        precedence.put('*', 2); precedence.put('/', 2);
    }

    public String convert(String infix) {
        StringBuilder output = new StringBuilder();
        Stack<Character> operators = new Stack<>();

        for (char c : infix.toCharArray()) {
            if (Character.isDigit(c)) {
                output.append(c);
            } else if (c == '(') {
                operators.push(c);
            } else if (c == ')') {
                while (!operators.isEmpty() && operators.peek() != '(') {
                    output.append(operators.pop());
                }
                operators.pop(); // remove '('
            } else if (precedence.containsKey(c)) {
                while (!operators.isEmpty()
                        && !operators.peek().equals('(')
                        && precedence.get(operators.peek()) >= precedence.get(c)) {
                    output.append(operators.pop());
                }
                operators.push(c);
            }
        }

        while (!operators.isEmpty()) {
            output.append(operators.pop());
        }

        return output.toString();
    }
}

测试： convert("3+4*2") → "342*+"

3.4.2 利用栈完成算术表达式计算的完整代码演示

public int evaluatePostfix(String postfix) {
    Stack<Integer> stack = new Stack<>();

    for (char c : postfix.toCharArray()) {
        if (Character.isDigit(c)) {
            stack.push(c - '0');
        } else {
            int b = stack.pop();
            int a = stack.pop();
            switch (c) {
                case '+': stack.push(a + b); break;
                case '-': stack.push(a - b); break;
                case '*': stack.push(a * b); break;
                case '/': stack.push(a / b); break;
            }
        }
    }
    return stack.pop();
}

最终结果：输入 "342*+" → 输出 11 ，正确反映 3 + (4 * 2) 。

这一系列技术广泛应用于计算器、编译器词法分析、公式引擎等领域，充分展现了栈在抽象语法处理中的核心地位。

4. 二叉树、AVL树、红黑树的构建与遍历

在现代计算机科学中，树结构作为非线性数据结构的重要代表，在组织层次化信息方面具有不可替代的地位。尤其是在高效查找、排序和动态维护有序集合等场景下，基于二叉搜索树（BST）演进而来的高级自平衡树结构——如AVL树与红黑树——成为Java集合框架中 TreeMap 与 TreeSet 的核心支撑机制。本章将深入剖析从基础二叉树到高级自平衡树的构建逻辑、操作原理及其实现细节，并通过实战项目展示其在真实系统中的应用价值。

我们将从最基础的二叉树节点建模出发，逐步引入递归与迭代方式下的四种主要遍历策略（前序、中序、后序、层次遍历），然后重点解析AVL树如何通过旋转维持严格的平衡性，以及红黑树如何以颜色标记和五大约束条件实现近似平衡。最后结合文件目录系统的建模需求，演示如何利用树形结构进行路径搜索与层级管理，为后续图论内容打下坚实基础。

4.1 二叉树的基本结构与递归遍历

二叉树是一种每个节点最多有两个子节点的树形结构，通常分为左子节点和右子节点。它不仅是理解更复杂树结构的基础，也是许多算法问题（如表达式求值、Huffman编码、决策树等）的底层模型。在Java中，我们可以通过类封装来实现一个通用的二叉树节点，并在此基础上完成各种遍历与查询操作。

4.1.1 二叉树的节点定义与层次结构建模

要构建一棵二叉树，首先需要定义其基本组成单元——节点。一个典型的二叉树节点包含数据域、指向左子节点的引用和指向右子节点的引用。使用泛型可以增强代码的复用性，使其适用于不同类型的数据存储。

public class TreeNode<T> {
    T data;
    TreeNode<T> left;
    TreeNode<T> right;

    public TreeNode(T data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

上述代码定义了一个泛型化的 TreeNode 类，其中 data 用于存储任意类型的数据， left 和 right 分别指向左右子节点。这种设计允许我们在运行时创建整数、字符串或其他对象类型的节点实例。

例如，构造如下简单的二叉树：

      A
     / \
    B   C
   / \
  D   E

对应的Java代码如下：

TreeNode<String> root = new TreeNode<>("A");
root.left = new TreeNode<>("B");
root.right = new TreeNode<>("C");
root.left.left = new TreeNode<>("D");
root.left.right = new TreeNode<>("E");

该结构清晰地表达了节点间的父子关系。值得注意的是，虽然物理上这些对象分布在堆内存的不同位置，但通过引用链接形成了逻辑上的层次结构。这种“指针式”连接使得插入、删除和重构变得灵活，但也带来了额外的内存开销与缓存局部性较差的问题。

为了更好地可视化整个树的形态，我们可以借助Mermaid流程图描述其结构关系：

graph TD
    A[A] --> B[B]
    A --> C[C]
    B --> D[D]
    B --> E[E]

此图准确反映了上述代码所建立的拓扑结构。此外，在实际开发中，常需对树的高度、节点总数、叶子节点数量等属性进行统计分析，这通常依赖于递归方法实现。

属性	描述
树高	从根到最远叶节点的边数
节点数	所有非空节点的总和
叶子节点	没有子节点的节点
度	节点拥有的子节点数（0、1或2）

这类元信息对于评估树的性能至关重要，特别是在判断是否应进行平衡优化时。

4.1.2 前序、中序、后序遍历的递归与非递归实现

遍历是访问树中所有节点的基本操作，常见的三种深度优先遍历方式分别为： 前序 （根-左-右）、 中序 （左-根-右）、 后序 （左-右-根）。它们在表达式解析、序列化、语法树处理等领域广泛应用。

递归实现

递归版本简洁直观，符合人类思维习惯。以下为三种遍历的递归实现：

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeTraversal {

    public static <T> List<T> preorder(TreeNode<T> root) {
        List<T> result = new ArrayList<>();
        preorderHelper(root, result);
        return result;
    }

    private static <T> void preorderHelper(TreeNode<T> node, List<T> result) {
        if (node == null) return;
        result.add(node.data);           // 访问根
        preorderHelper(node.left, result);  // 遍历左子树
        preorderHelper(node.right, result); // 遍历右子树
    }

    public static <T> List<T> inorder(TreeNode<T> root) {
        List<T> result = new ArrayList<>();
        inorderHelper(root, result);
        return result;
    }

    private static <T> void inorderHelper(TreeNode<T> node, List<T> result) {
        if (node == null) return;
        inorderHelper(node.left, result);    // 遍历左子树
        result.add(node.data);               // 访问根
        inorderHelper(node.right, result);   // 遍历右子树
    }

    public static <T> List<T> postorder(TreeNode<T> root) {
        List<T> result = new ArrayList<>();
        postorderHelper(root, result);
        return result;
    }

    private static <T> void postorderHelper(TreeNode<T> node, List<T> result) {
        if (node == null) return;
        postorderHelper(node.left, result);  // 遍历左子树
        postorderHelper(node.right, result); // 遍历右子树
        result.add(node.data);               // 访问根
    }
}

代码逻辑逐行解读：

• preorder() ：初始化结果列表并调用辅助函数。
• preorderHelper() ：
• 若当前节点为空，则直接返回（递归终止条件）；
• 否则先加入当前节点数据（体现“前”字含义）；
• 再递归处理左子树；
• 最后递归处理右子树。
• 中序与后序仅改变访问顺序，其余结构一致。

以之前构建的树为例：

List<String> pre = preorder(root);  // 输出: [A, B, D, E, C]
List<String> in = inorder(root);    // 输出: [D, B, E, A, C]
List<String> post = postorder(root); // 输出: [D, E, B, C, A]

中序遍历特别重要： 当二叉树为二叉搜索树时，中序遍历的结果是一个升序序列 ，这是后续AVL与红黑树排序能力的理论依据。

非递归实现（使用栈）

由于递归可能导致栈溢出（尤其在深度较大的树中），采用显式栈模拟调用过程更为安全。以下是前序遍历的迭代版本：

import java.util.Stack;

public static <T> List<T> preorderIterative(TreeNode<T> root) {
    List<T> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode<T>> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode<T> node = stack.pop();
        result.add(node.data);

        // 先压入右子节点，再压入左子节点（保证左先出）
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    return result;
}

参数说明与执行逻辑分析：

• 使用 Stack<TreeNode<T>> 显式保存待处理节点；
• 初始将根节点入栈；
• 循环中每次弹出栈顶元素并访问；
• 然后按“右→左”的顺序将其非空子节点入栈，确保下一轮先处理左侧分支；
• 时间复杂度为 O(n)，空间复杂度最坏为 O(h)，h为树高。

类似地，中序遍历的非递归实现需沿最左路径不断入栈，直到无法前进后再回溯访问：

public static <T> List<T> inorderIterative(TreeNode<T> root) {
    List<T> result = new ArrayList<>();
    Stack<TreeNode<T>> stack = new Stack<>();
    TreeNode<T> current = root;

    while (current != null || !stack.isEmpty()) {
        // 一直向左走到底
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        // 回退并访问
        current = stack.pop();
        result.add(current.data);
        // 转向右子树
        current = current.right;
    }
    return result;
}

此方法巧妙利用了栈的“后进先出”特性，完美模拟了递归调用栈的行为。

4.1.3 层次遍历与队列的协同工作机制

除了深度优先遍历，还有一种广度优先的方式称为 层次遍历 （Level-order Traversal），即按层从上到下、每层从左到右依次访问节点。这种遍历必须借助队列（FIFO）结构实现。

import java.util.LinkedList;
import java.util.Queue;

public static <T> List<T> levelOrder(TreeNode<T> root) {
    List<T> result = new ArrayList<>();
    if (root == null) return result;

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

    while (!queue.isEmpty()) {
        TreeNode<T> node = queue.poll();
        result.add(node.data);

        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    return result;
}

执行流程说明：

• 初始化队列并将根节点入队；
• 当队列非空时，取出队首节点并访问；
• 将其左右子节点（若存在）依次入队；
• 重复直至队列为空。

对于前述示例树，输出为： [A, B, C, D, E] ，完全按照层级顺序排列。

该算法广泛应用于：
- 树的宽度计算；
- 找到每一层的最大值；
- 判断完全二叉树或满二叉树；
- 层序反序列化重建树。

下表对比了四种主要遍历方式的特点：

遍历方式	数据结构	访问顺序	典型用途
前序遍历	栈（递归/显式）	根→左→右	复制树、表达式前缀
中序遍历	栈	左→根→右	BST排序输出
后序遍历	栈	左→右→根	删除树、表达式后缀
层次遍历	队列	层级从上到下	宽度优先搜索

此外，还可绘制流程图表示层次遍历的控制流：

flowchart TD
    A[开始] --> B{根为空?}
    B -- 是 --> C[返回空列表]
    B -- 否 --> D[根入队]
    D --> E{队列非空?}
    E -- 否 --> F[结束]
    E -- 是 --> G[出队当前节点]
    G --> H[访问该节点]
    H --> I[左子入队?]
    I --> J[右子入队?]
    J --> E

该流程图清晰展示了循环判断、节点出队、子节点入队的闭环逻辑，有助于理解广度优先搜索的本质机制。

综上所述，掌握多种遍历技术不仅提升编码能力，也为后续学习平衡树、图算法奠定坚实基础。接下来章节将进一步探讨如何通过自平衡机制避免普通二叉搜索树退化为链表的问题。

5. 图的表示与常用算法应用

5.1 图的数据结构表示方法

图（Graph）是一种用于表示对象之间多对多关系的非线性数据结构，广泛应用于社交网络、交通路径规划、任务调度等领域。在Java中，图可以通过多种方式建模和实现，其中最常见的是 邻接矩阵 和 邻接表 。

邻接矩阵 vs 邻接表：Java 实现对比

特性	邻接矩阵	邻接表
存储空间复杂度	O(V²)	O(V + E)
添加边时间复杂度	O(1)	O(1)
查询两点是否相连	O(1)	O(degree)
适合场景	密集图（边多）	稀疏图（边少）
内存占用	高	低
支持加权图	直接存储权重值	可通过Map或内部类扩展
实现难度	简单	中等

邻接矩阵使用二维数组 boolean[][] 或 int[][] 表示顶点之间的连接关系；而邻接表则通常采用 Map<Integer, List<Edge>> 或 List<List<Integer>> 的形式维护每个节点的邻居列表。

Java 示例：邻接表实现无向加权图

import java.util.*;

class Graph {
    private int V; // 顶点数量
    private List<List<Edge>> adj; // 邻接表

    static class Edge {
        int dest;
        int weight;

        public Edge(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }

    public Graph(int v) {
        V = v;
        adj = new ArrayList<>(v);
        for (int i = 0; i < v; i++) {
            adj.add(new LinkedList<>());
        }
    }

    // 添加无向边（可带权重）
    public void addEdge(int src, int dest, int weight) {
        adj.get(src).add(new Edge(dest, weight));
        adj.get(dest).add(new Edge(src, weight)); // 无向图双向添加
    }

    // 打印图结构
    public void printGraph() {
        for (int u = 0; u < V; u++) {
            System.out.print("顶点 " + u + " -> ");
            for (Edge e : adj.get(u)) {
                System.out.print("(" + e.dest + "," + e.weight + ") ");
            }
            System.out.println();
        }
    }
}

上述代码中：
- V 表示图中顶点总数。
- adj 是一个动态列表数组，每个索引对应一个顶点的邻接边集合。
- Edge 类封装目标顶点与边权信息，支持后续最短路径等算法扩展。

图类型建模：有向图、无向图与加权图

图类型	边方向性	是否有权重	Java 建模方式
无向图	双向	否/是	addEdge(a,b); addEdge(b,a);
有向图	单向	否/是	仅 addEdge(from,to)
加权图	单/双	是	使用Edge类或Map存储weight
DAG（有向无环图）	单向	可选	拓扑排序适用场景

例如，在构建有向图时只需单向添加边：

public void addDirectedEdge(int src, int dest, int weight) {
    adj.get(src).add(new Edge(dest, weight));
}

图的遍历算法：DFS 与 BFS

图的遍历是许多高级算法的基础，主要包括深度优先搜索（DFS）和广度优先搜索（BFS），两者分别基于栈（递归）和队列实现。

DFS 递归实现（适用于连通性判断）

public void dfs(int start, boolean[] visited) {
    visited[start] = true;
    System.out.print(start + " ");

    for (Edge e : adj.get(start)) {
        if (!visited[e.dest]) {
            dfs(e.dest, visited);
        }
    }
}

BFS 迭代实现（适用于最短路径初步探索）

public void bfs(int start) {
    boolean[] visited = new boolean[V];
    Queue<Integer> queue = new LinkedList<>();

    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int u = queue.poll();
        System.out.print(u + " ");

        for (Edge e : adj.get(u)) {
            if (!visited[e.dest]) {
                visited[e.dest] = true;
                queue.offer(e.dest);
            }
        }
    }
}

BFS 能保证首次访问某节点时即为其从起点出发的最短边数路径，适合“六度空间”、“朋友推荐”等层级扩散场景。

graph TD
    A[0] -- 2 --> B[1]
    A -- 1 --> C[2]
    B -- 3 --> D[3]
    C -- 4 --> D
    D -- 1 --> E[4]
    style A fill:#f9f,stroke:#333
    style E fill:#bbf,stroke:#333

该流程图展示了一个简单加权无向图的连接关系，可用于后续最短路径计算演示。

本文还有配套的精品资源，点击获取

简介：数据结构与算法是IT领域的编程基石，直接影响程序性能与优化能力。本资源“数据结构与算法代码详解JAVA版”系统讲解了使用Java语言实现各类核心数据结构与经典算法的方法。涵盖数组、链表、栈、队列、树、图、哈希表等数据结构，以及排序、查找、最短路径、动态规划、贪心算法等关键算法，并通过“AlgorithmPresentation”文件提供可运行的Java代码示例，帮助读者深入理解其工作原理并应用于实际开发中。该资源适合各阶段开发者学习与实践，助力提升编程能力、面试表现和问题解决效率。

本文还有配套的精品资源，点击获取