欢迎来到数据结构的世界！
有没有想过手机是如何记录你的“撤销”历史，或者打印机是怎么决定哪份文件先打印的吗？答案就在数据结构 (Data Structures)！在这一章，我们不只是单纯处理数据，更要探索如何运用巧妙的方法来组织和存储这些数据，以便更有效地使用它们。这就像在整理衣物，你是要把衣服乱堆成一团，还是把它们整齐地分类放进抽屉呢？选择正确的结构，找东西时效率绝对会快得多！
如果有些概念初看觉得抽象，请别担心。我们会用大量的现实生活类比，帮助你轻松理解。让我们开始吧！
1. 栈与队列：排队好伙伴
栈 (Stack - LIFO)
栈 (Stack) 是一种线性数据结构，遵循 LIFO 原则：后进先出 (Last-In, First-Out)。
类比：想象一叠自助餐厅的餐盘。最后放上去的那一个餐盘，一定是第一个被拿走的。你不可能在不弄乱的情况下直接抽取最底下的餐盘！
核心操作：
1. 入栈 (Push)： 将项目加入到栈的最上方。
2. 出栈 (Pop)： 将项目从栈的最上方移除。
3. 查看 (Peek/Top)： 查看最上方的项目而不将其移除。
队列 (Queue - FIFO)
队列 (Queue) 遵循 FIFO 原则：先进先出 (First-In, First-Out)。
类比：买珍珠奶茶排队。第一个加入队伍的人一定最先获得服务。既简单又公平！
线性队列 vs. 环形队列：
- 线性队列 (Linear Queue)： 当项目被移除时，前端的空间就“浪费”了，除非你将所有人向前移动（这会很慢）。
- 环形队列 (Circular Queue)： 当到达数组末端时，下一个项目会“绕回”到前端（如果有空间的话）。这就像旋转木马，座位不断循环移动！
核心操作：
1. 入队 (Enqueue)： 将项目加入到队列的后端 (rear)。
2. 出队 (Dequeue)： 将项目从队列的前端 (front) 移除。
快速复习：记住 S-L (Stack-LIFO) 和 Q-F (Queue-FIFO)。栈用于撤销操作；队列则用于等待名单！
2. 线性链表 (Linear Linked Lists)
链表 (Linked List) 是由多个节点 (nodes) 组成的集合。每个节点包含两个部分：
1. 数据 (Data)： 实际存储的信息。
2. 指针 (Pointer)： 指向链表中下一个节点的箭头。
类比：寻宝游戏。每个线索（节点）告诉你宝藏是什么（数据），并给你一张指向下一个线索的地图（指针）。当线索显示“没有更多位置了”（空指针 null pointer）时，游戏结束。
操作：
- 搜索 (Search)： 你必须从“头部 (Head)”开始，逐一跟随箭头直到找到目标。你不能直接“跳”到中间！
- 插入 (Insert)： 若要新增节点，只需“中断链接”并重新导向指针即可。这比移动整个数组快得多！
- 删除 (Delete)： 修改前一个节点的指针，使其“跳过”你想删除的那个节点即可。
常见错误：如果你在链表的最开头进行插入或删除操作，却忘了更新头部 (Head) 指针！
重点总结：与长度固定的数组相比，链表的大小具有高度弹性。
3. 二叉树与二叉搜索树 (BST)
二叉树 (Binary Tree) 是一种层次式结构，每个节点最多拥有两个子节点（左子节点和右子节点）。
二叉搜索树 (Binary Search Tree, BST)
BST 是一种特殊的二叉树，遵循特定规则：
- 左子节点 < 父节点
- 右子节点 > 父节点
例子：如果根节点是 50，所有小于 50 的数字都在左侧分支，所有大于 50 的数字都在右侧。这使得搜索变得极快，因为每走一步都能排除掉一半的树！
树的遍历 (Tree Traversals)
我们如何“访问”树中的每一个节点？主要有三种方法：
1. 前序遍历 (Pre-order)： 根 -> 左 -> 右（用于复制树）。
2. 中序遍历 (In-order)： 左 -> 根 -> 右（小贴士：对于 BST，这会以升序访问节点！）。
3. 后序遍历 (Post-order)： 左 -> 右 -> 根（用于删除树或评估数学表达式）。
树的搜索方式
1. 广度优先搜索 (BFS)： 一层一层地探索（由上而下，由左至右）。
2. 深度优先搜索 (DFS)： 在回溯之前，尽可能地向深处钻研某一个分支。
总结：树非常适合表示层次结构（例如电脑中的文件夹）以及进行快速搜索 (BST)。
4. 哈希表 (Hash Tables)
哈希表 (Hash Table) 专为即时查找而设计。它利用哈希函数 (Hash Function) 将键值（如学生 ID）转换为索引（数组中的特定位置）。
类比：专属储物柜。你不需要检查每一个柜子，只要用神奇公式：“你的柜号就是你 ID 的后两位数。”你就能直接找到对应柜子！
问题：碰撞 (Collisions)
如果两名学生的 ID 结尾都是“23”怎么办？这就是碰撞。
处理碰撞（线性探测 Linear Probing）：如果你的指定位置已满，就寻找下一个可用的空位。这就像发现椅子上有人坐了，就坐到隔壁空位一样。
重点总结：哈希表追求的是速度。一个好的哈希函数能均匀地分布数据，避免“挤在一起”。
5. 文本文件处理
程序需要在关闭后仍能“记住”数据，我们通过存储数据到文本文件 (Text Files) 来达成。
流程：
1. 开启 (Open)： 以读取 (r)、写入 (w) 或追加 (a) 模式开启文件。
2. 处理 (Process)： 使用循环读取文件中的行，或是将新数据写入其中。
3. 关闭 (Close)： 一定要关闭文件！这就像挂断电话一样——如果不做，可能会丢失数据或“锁死”文件。
你知道吗？ 在 Python 中，使用 with 关键字可以自动为你关闭文件，即使发生错误也能确保文件安全关闭！
总结检查表
- 栈 (Stack)： LIFO（后进先出）。想想“撤销”按钮。
- 队列 (Queue)： FIFO（先进先出）。想想“打印机队列”。
- 链表 (Linked List)： 节点 + 指针。大小弹性，但搜索较慢。
- BST： 左小右大。搜索速度极快。
- 中序遍历： 可从 BST 取得排序后的数据。
- 哈希表： 使用函数达成接近即时的存取。留意碰撞！
- 文件： 永久存储的关键。开启 -> 处理 -> 关闭。
如果起初觉得有点棘手，别担心！ 数据结构就像工具箱里的各种工具。你越常在代码中练习使用它们，就越能明白哪个工具才是完成任务的最佳选择。继续加油，保持编码！