栈
栈的基本概念
栈是一种线性数据结构，遵循先进后出，后进先出（LIFO）原则。最后插入的元素最先被移除。栈的操作通常限制在栈顶进行，包括压栈（push）和弹栈（pop）。
栈的核心操作
压栈（Push） 将元素添加到栈顶。若栈已满（固定容量栈），则称为栈溢出（Stack Overflow）。
弹栈（Pop） 移除并返回栈顶元素。若栈为空，则称为栈下溢（Stack Underflow）。
查看栈顶（Peek/Top） 返回栈顶元素但不移除它。
判空（isEmpty） 检查栈是否为空。
栈的实现方式
数组实现 使用数组存储元素，维护一个栈顶指针（或索引）。压栈时指针递增，弹栈时指针递减。 优点：实现简单，访问速度快。 缺点：容量固定，可能需动态扩容。
链表实现 使用链表的头部作为栈顶，压栈和弹栈均在头部操作。 优点：动态扩容，无固定大小限制。 缺点：额外内存存储指针，操作略慢于数组。
栈的应用场景
函数调用栈 程序执行时，函数调用和返回通过栈管理。每次调用压栈，返回时弹栈。
表达式求值 中缀表达式转后缀表达式或直接求值时，用栈处理运算符优先级。
括号匹配 检查括号是否成对且嵌套正确。遇到左括号压栈，右括号弹栈匹配。
撤销操作（Undo） 文本编辑器中，每次操作压栈，撤销时弹栈恢复状态。
队列
队列的基本概念
队列是一种先进先出（FIFO, First In First Out）的线性数据结构，类似于现实生活中的排队场景。元素从队列的尾部（rear）加入，从队列的头部（front）移除。
队列的操作
- 入队（Enqueue）：在队列尾部添加元素。
- 出队（Dequeue）：从队列头部移除元素并返回。
- 查看队头（Peek/Front）：获取队头元素但不移除。
- 判空（IsEmpty）：检查队列是否为空。
- 获取队列大小（Size）：返回队列中元素的数量。
队列的实现方式
队列可以通过数组或链表实现：
基于数组的实现 使用固定大小的数组时，可能遇到'假溢出'问题（即数组未满但无法插入），需通过循环队列优化。
基于链表的实现 动态分配节点，无需担心容量限制，但需要额外的指针开销。
队列的应用场景
- 任务调度：如 CPU 任务队列、打印任务队列。
- 广度优先搜索（BFS）：遍历树或图时使用队列管理待访问节点。
- 缓冲区管理：数据流处理中的缓冲机制。
二叉树
二叉树的基本概念
二叉树是一种树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。节点之间的连接称为边，没有子节点的节点称为叶子节点。
二叉树的特点
- 有序性：子节点分为左、右，顺序不可随意调换。
- 递归结构：每个子树本身也是一棵二叉树。
- 常见类型：包括满二叉树、完全二叉树、二叉搜索树（BST）、平衡二叉树（如 AVL 树）等。
二叉树的遍历方式
- 深度优先遍历（DFS）：前序遍历（根→左→右）、中序遍历（左→根→右）、后序遍历（左→右→根）。
- 广度优先遍历（BFS）：按层级从上到下、从左到右访问节点。
应用场景
- 二叉搜索树用于高效查找、插入和删除（平均时间复杂度 O(log n)）。
- 堆（一种完全二叉树）用于优先队列和排序算法（如堆排序）。
- 哈夫曼树用于数据压缩编码。
存储方式
- 链式存储：通过节点对象存储值和左右子节点的引用。
- 顺序存储：用数组表示，通过下标计算父子节点位置（适用于完全二叉树）。
哈希表
哈希表的基本概念
哈希表是一种通过哈希函数将键（Key）映射到存储位置（值 Value）的数据结构。它支持高效的数据插入、删除和查找操作，平均时间复杂度为 O(1)。
核心组成
- 哈希函数：将键转换为数组索引，理想情况下应均匀分布以减少冲突。
- 冲突处理：常见方法包括链地址法（链表存储冲突键）和开放寻址法（探测空闲位置）。
特点
- 高效性：平均情况下操作时间为常数级。
- 空间权衡：需预留足够空间以减少冲突，可能浪费部分内存。
- 无序性：不保证键的顺序（某些实现如 LinkedHashMap 除外）。
应用场景
- 快速查找（如字典、缓存）。
- 去重（如统计唯一元素）。
- 数据库索引优化。
注意事项
- 哈希函数设计不当会导致性能退化至 O(n)。
- 动态扩容（Rehashing）可能影响实时性。
