数据结构：八大数据结构分类
在计算机科学和编程领域，八大数据结构 是最常见、最基础的分类，常用于面试、算法设计和实际开发。这些数据结构通常指：
- 数组（Array）
- 栈（Stack）
- 队列（Queue）
- 链表（Linked List）
- 树（Tree）
- 图（Graph）
- 堆（Heap）
- 散列表/哈希表（Hash Table）
这些数据结构可以进一步分为线性结构（数组、栈、队列、链表）和非线性结构（树、图、堆、散列表）。下面详细介绍每一种的特点、优缺点和应用场景。
八大数据结构对比表
| 数据结构 | 类型 | 存储方式 | 主要特点 | 优点 | 缺点 | 常见应用场景 |
|---|---|---|---|---|---|---|
| 数组 | 线性 | 连续内存 | 固定大小、随机访问（下标索引） | 查询快 O(1)、缓存友好 | 插入/删除慢 O(n)、大小固定 | 矩阵、查找表、缓冲区 |
| 栈 | 线性 | 顺序/链式 | 后进先出（LIFO） | 插入/删除快 O(1) | 访问受限（只能顶端操作） | 函数调用、表达式求值、深度优先搜索 |
| 队列 | 线性 | 顺序/链式 | 先进先出（FIFO） | 插入/删除快 O(1) | 访问受限（只能两端操作） | 任务调度、BFS、消息队列 |
| 链表 | 线性 | 非连续内存 | 动态大小、节点指针连接 | 插入/删除快 O(1) | 查询慢 O(n)、缓存不友好 | 动态列表、队列/栈实现、LRU缓存 |
| 树 | 非线性 | 节点+指针 | 层次结构（一对多） | 查找/插入/删除平均 O(log n) | 最坏 O(n)（退化成链表） | 二叉搜索树、堆、文件系统、DOM树 |
| 图 | 非线性 | 节点+边 | 多对多关系 | 灵活建模复杂关系 | 存储/遍历复杂（空间大） | 社交网络、路径查找、推荐系统 |
| 堆 | 非线性 | 数组（完全二叉树） | 父节点 ≥/≤ 子节点（大/小顶堆） | 取极值 O(1)、插入/删除 O(log n) | 不支持随机访问 | 优先队列、堆排序、TopK问题 |
| 哈希表 | 非线性 | 数组+链表/树 | 键值映射（Key-Value） | 平均查找/插入/删除 O(1) | 冲突处理、最坏 O(n)、无序 | 缓存、数据库索引、集合/映射 |
每种数据结构的简要说明
- 数组：连续内存存储相同类型元素，支持快速随机访问，但大小固定，插入删除需移动元素。
- 栈：只允许在一端（栈顶）操作，适合“撤销”或递归场景。
- 队列：两端操作（队尾入队、队头出队），适合顺序处理任务。
- 链表：节点分散存储，通过指针连接，动态扩展方便，但遍历慢。
- 树：层次结构，常见变种如二叉树、平衡树（AVL/红黑树）、B树，用于高效搜索和排序。
- 图：节点间任意连接，分为有向/无向图，用于建模复杂关系（如地图、社交）。
- 堆：完全二叉树结构，常用于优先队列，实现堆排序。
- 哈希表：通过哈希函数将键映射到数组索引，解决冲突常用链地址法或红黑树（Java HashMap）。
这些数据结构是算法的基础，许多高级结构（如红黑树、跳表）都基于它们扩展。学习时建议结合实际代码实现（如LeetCode题目）加深理解。如果你需要某一种的详细代码示例或算法分析，欢迎继续提问！
