数据结构基础｜面向IT护照考试的数组、链表、栈、队列、树整理

什么是数据结构

数据结构是用于高效存储和操作数据的格式。根据用途选择合适的结构，处理速度和内存效率会有很大差异。

线性结构

数组（Array）

数组将相同类型的数据存储在连续的内存区域中。通过下标访问，访问时间为 O(1)，速度很快。另一方面，插入或删除元素时需要移动后续元素，因此需要 O(n) 的时间，这是其弱点。

链表（Linked List）

链表中，每个元素通过“数据”和“指向下一个元素的指针”连接。如果知道位置，插入和删除可以在 O(1) 时间内完成，但通过下标访问需要 O(n) 时间。

栈（Stack・LIFO）

栈是 LIFO（Last In First Out），即后进先出的数据结构。主要操作是 push（添加）和 pop（取出）。实际例子包括函数调用历史、撤销功能、浏览器的返回按钮等。

队列（Queue・FIFO）

队列是 FIFO（First In First Out），即先进先出的数据结构。操作是 enqueue（添加）和 dequeue（取出）。用于打印机的打印等待队列和消息队列等。

双端队列（Deque）

可以从两端进行添加和取出的队列。兼具栈和队列的特性。

层次结构

树结构（Tree）

树结构是具有父子关系的层次结构。由节点和边组成。术语包括根、叶、深度、高度。

二叉树（Binary Tree）

二叉树是每个节点最多有两个子节点的树。特别是二叉搜索树，按左 < 父 < 右的顺序排列，因此搜索可以在 O(log n) 时间内完成。

其他

哈希表

哈希表通过哈希函数将键转换为下标来存储值。平均可以在 O(1) 时间内完成搜索、插入和删除，但需要处理冲突（链地址法或开放地址法）。

图

图通过节点和边表示关系。用于网络图、社交网络的好友关系、地图路径等。

IT护照考试的出题要点

栈（LIFO）和队列（FIFO）的区别是高频考点。此外，数组和链表的访问、插入所需的计算量，以及树结构的术语（根、叶、深度）也要掌握。

历年真题的典型模式

• “后进先出的数据结构是哪个”型 → 栈
• “适合打印机打印队列的数据结构是哪个”型 → 队列

相关术语

• 算法与计算量（算法与计算量）
• 数据库（关系数据库与SQL基础）

学习技巧

LIFO 可以联想为栈（叠盘子），FIFO 可以联想为队列（排队），这样更容易记忆。将“数组 = 快速访问，链表 = 快速插入”的特性进行对比。树的术语（根、叶）一旦用图解说明，理解会更深入。

总结

掌握线性和层次结构，以及 LIFO/FIFO 的区别和各数据结构的特性，数据结构问题就能稳定得分。如果想全面练习技术类内容，请访问技术类汇总；想进行实战模拟，请前往模拟考试。