👋 欢迎来到 HL 主题 5：抽象数据结构 (ADS)！
本章我们将跳出简单的变量和数组，探索组织数据时更具结构化且强大的方法。别担心，这些概念听起来可能有点深奥，其实并不复杂！抽象数据结构 (Abstract Data Structure, ADS) 仅仅是一个关于“如何组织和访问数据”的正式蓝图。
你可以把 ADS 看作你编程工具箱中的“专业工具”。如果你需要管理一个等待列表，就用“队列”；如果你需要跟踪函数调用，就用“栈”。掌握这些结构是编写高效且优雅的高级 (Higher Level) 计算机科学方案的核心。
主题 5 的核心学习目标
- 理解抽象 (Abstraction) 与实现 (Implementation) 之间的区别。
- 掌握栈 (LIFO) 和队列 (FIFO) 的行为方式及用途。
- 理解链表 (Linked Lists) 等动态结构的概念。
- 探索非线性结构，特别是二叉搜索树 (BSTs)。
1. 抽象的概念
什么是抽象数据结构 (ADS)？
ADS 定义了数据、数据之间的关系，以及可以对这些数据执行的操作，但并不指定数据在内存中是如何存储的。
这种分离被称为抽象 (Abstraction)。
类比：电视遥控器
当你按下电视遥控器上的“音量加”按钮时，你并不关心电路、红外线信号或电视内部的编程代码（即实现）。你只关心那个操作（“音量加”）是否按预期工作（即抽象）。
同样，当我们使用“栈”这一 ADS 时，我们只定义了操作（PUSH 和 POP）。我们并不担心这个栈内部是使用固定的数组还是灵活的链表来实现的。
抽象 vs. 实现
- 抽象 (Abstraction)： 逻辑视角。该数据结构能做什么？（例如：队列按顺序保存等待处理的项目。）
- 实现 (Implementation)： 物理视角。该数据结构是如何构建的？（例如：使用数组，或者使用对象链表。）
为什么要这样分离？ 这让我们能够先专注于问题的定义。如果一名软件工程师需要一个等待列表，他们可以直接调用“队列 ADS”蓝图。稍后，系统程序员可以根据具体的计算机环境决定实现该队列的最优方式。
快速总结
ADS = 它做什么 (What)。
实现 = 它怎么做 (How)。
2. 栈：后进先出 (LIFO)
定义与行为
栈 (Stack) 是一种线性 ADS，所有的添加和删除操作都发生在同一端，称为栈顶 (top)。
这导致了 LIFO (Last-In, First-Out，后进先出) 的行为。最后放入栈的项目永远是第一个被移除的。
类比：餐厅托盘架
想象一下餐厅里的托盘分配器。你只能把新托盘放在最上面，也只能从最上面拿走一个托盘。最后放进去的托盘，总是最先被取走。
关键栈操作
- PUSH： 将一个项目添加到栈顶。
- POP： 移除并返回栈顶的项目。
- PEEK (或 TOP)： 查看但并不移除栈顶的项目。
- isEmpty： 检查栈当前是否包含任何项目。
冷知识 (现实应用)
栈对于计算机管理程序至关重要。运行时栈 (Run-Time Stack)（或调用栈）用于跟踪函数调用。当函数 A 调用函数 B 时，B 会被 PUSH 到栈上。当 B 执行完毕，它会被 POP 出栈，程序会返回 A 中刚才中断的位置继续执行。
常见错误： 混淆 PEEK 和 POP。POP 会改变栈，而 PEEK 只会读取栈。
快速复习：栈的记忆口诀
LIFO：Last In (后进) 意味着 First Out (先出)。
3. 队列：先进先出 (FIFO)
定义与行为
队列 (Queue) 是一种线性 ADS，插入操作发生在其中一端（队尾 rear/tail），删除操作发生在另一端（队首 front/head）。
这导致了 FIFO (First-In, First-Out，先进先出) 的行为。第一个进入队列的项目是第一个离开的项目。
类比：排队
想想在超市排队结账或演唱会买票。第一个排队的人是第一个被服务的。新人总是加入到队伍的最后（队尾）。
关键队列操作
- ENQUEUE： 将项目添加到队列的末尾（队尾）。
- DEQUEUE： 移除并返回队列前端（队首）的项目。
- PEEK (或 FRONT)： 查看队首的项目但不移除它。
- isEmpty： 检查队列是否为空。
现实应用：打印任务
如果你发送了三个文档到共享打印机，它们不会同时打印。它们会排在一个打印队列中。第一个发送的文档 (FIFO) 会被第一个打印出来。
实现说明 (HL 重点)
虽然队列可以用简单的数组来实现，但效率往往较低，因为 DEQUEUE 操作需要将剩余的所有项目向前移动。为了获得更高的效率，队列通常使用循环数组 (circular array) 或链表来实现。
4. 链表：动态存储
数组的缺陷
数组（静态数据结构）有两个主要限制：一是创建时大小固定，二是由于需要移动元素，在中间插入或删除数据非常缓慢。
定义与结构
链表 (Linked List) 是一种动态 ADS，其元素在内存中不必连续存储。相反，每个元素被称为节点 (Node)，包含两个部分：
- 数据 (Data)： 本身的值。
- 指针 (Pointer)： 指向序列中下一个节点的链接。
链表总是以一个特殊的指针 头 (Head) 开始，它指向第一个节点。当节点的指针为 Null 时，表示链表结束。
类比：寻宝游戏
想象一个寻宝游戏，每一条线索（节点）都告诉你下一条线索的位置（指针）。你只需要知道第一条线索（Head）在哪里，就能找到所有后续线索，即使这些线索散落在很广的区域内（非连续内存）。
链表的主要优点
- 动态大小： 它们可以根据需要增减，从而有效地利用内存。
- 高效的插入/删除： 要插入或删除节点，你只需要修改相邻节点的指针即可。无需移动大量数据！
链表类型 (考纲范围)
- 单向链表 (Singly Linked List)： 每个节点只指向下一个节点。（单行道）。
- 双向链表 (Doubly Linked List)： 每个节点有两个指针：一个指向下一个节点，一个指向前一个节点。（双行道，使向后遍历和删除变得更容易）。
快速总结：效率
链表用牺牲顺序访问速度（数组擅长的地方）来换取在列表中间进行插入和删除的快速处理。
5. 树：非线性结构
定义与术语
树 (Tree) 是一种用于表示层级数据的非线性 ADS。它由通过边 (Edges) 连接的节点组成。
树的关键术语：
- 根 (Root)： 树中最顶端的节点。（它没有父节点。）
- 子节点 (Child)： 从根出发，直接连接到另一个节点的节点。
- 父节点 (Parent)： 子节点的反义词。
- 叶节点 (Leaf)： 没有子节点的节点。（它位于树枝的末端。）
- 子树 (Subtree)： 树的一部分，其本身也是一棵树。
二叉搜索树 (BSTs)
二叉树 (Binary Tree) 是一棵树，其中每个节点最多有两个子节点（左子树和右子树）。
二叉搜索树 (BST) 执行一套组织规则，从而实现极高效的搜索、插入和删除：
- 左子树中的所有值必须小于父节点的值。
- 右子树中的所有值必须大于父节点的值。
为什么 BST 很有用？
如果你想在 BST 中查找数字 15，从根节点开始。如果根节点是 20，你立刻知道只需要去左子树中寻找，这有效地将搜索范围缩小了一半。这种速度至关重要！
分步讲解：向 BST 插入数据
插入一个值（例如：55）：
- 从根节点开始。
- 55 小于根吗？去左边。55 大于根吗？去右边。
- 重复第 2 步，沿着树向下查找，直到到达一个 Null 指针。
- 在该空位插入新节点 (55)。
树的遍历方法
遍历 (Traversal) 是指访问树中每个节点恰好一次的过程。有三种主要的递归遍历方法，其区别在于根节点 (Root) 相对于其左子树和右子树的访问顺序。
遍历记忆口诀：根 (R) 的位置
我们总是访问左子树 (L) 和右子树 (T)。区别在于根节点 (R) 在什么时候被访问。
1. 中序遍历 (In-order, L R T)：
顺序： 左子树 -> 根节点 -> 右子树
- 效果： 如果对 BST 进行中序遍历，总是能按数值或字母顺序输出结果。这是 BST 最著名的特性。
2. 前序遍历 (Pre-order, R L T)：
顺序： 根节点 -> 左子树 -> 右子树
- 效果： 常用于创建树的副本或重建树的结构。
3. 后序遍历 (Post-order, L T R)：
顺序： 左子树 -> 右子树 -> 根节点
- 效果： 主要用于删除或处理树，确保在处理/删除父节点之前，其所有子节点都已被处理/删除。
快速复习：ADS 一览
栈 (Stack)： LIFO (后进先出)。想想托盘。
队列 (Queue)： FIFO (先进先出)。想想排队。
链表 (Linked List)： 动态内存，通过指针灵活插入/删除。
二叉搜索树 (BST)： 层级结构（树），基于规则（左 < 根 < 右）进行快速搜索。