线性数据结构

如果一种数据结构中，每个元素最多只有一个前驱和一个后继，那么这种数据结构就是线性数据结构。

基础结构#

数组#

数组是最基础、最简单的线性存储结构。它在内存中表现为一块连续的内存空间，用于存储一组类型相同的数据元素。

• 核心特性：随机访问

  数组最大的优势在于能够以 $O(1)$ 的时间复杂度访问任意位置的元素。这种高效的“随机访问”能力得益于两个强制性条件：连续的内存空间和相同的元素类型。

  当计算机需要访问数组中下标为 $i$ 的元素时，它不需要从头遍历，而是利用下标直接通过一个简单的寻址公式计算出该元素的绝对内存地址：

  $\text{Address}[i] = \text{BaseAddress} + i \times \text{ElementSize}$

  其中 BaseAddress 是数组的首地址，ElementSize 是单个元素占用的字节大小（因为类型相同，所以大小固定）。由于计算机执行一次乘法和一次加法的时间是恒定的，所以无论数组有多大，访问任意元素都能 $O(1)$ 完成。

链表#

与数组相反，链表不要求内存空间的连续性。它通过一组离散的、不连续的内存块（称为节点，Node）来存储数据。每个节点除了包含数据本身之外，还必须包含一个或多个指向下一个（或前一个）节点地址的指针。

按照指针的连接方式不同，链表可以分为单/双向、顺序/循环。

• 核心特性：动态插入与删除

  链表天然具备动态扩容的能力，不需要在声明时指定固定大小。其核心优势在于高效的插入和删除操作。

  在已知目标位置的前提下，链表插入一个新节点只需要修改目标位置前后节点的指针指向即可，时间复杂度为 $O(1)$。这一过程完全不需要移动任何其他数据元素，因此效率极高。

---

---

封装#

在基础的线性数据结构上，我希望实现一些抽象的数据结构，以配合算法的过程。栈和队列就是其中最具代表性的，它们分别在 DFS 和 BFS 中发挥重要作用。

栈#

栈是一种操作受限的线性表。它限定所有的插入和删除操作只能在表的一端进行，这一端被称为栈顶 (Top)，另一端则被称为栈底 (Bottom)。栈严格遵循后进先出 (LIFO, Last In First Out) 的原则。将新元素放入栈顶的过程称为入栈 (Push)，将栈顶元素移出的过程称为出栈 (Pop)。

栈的特性使得其非常适合在 DFS 中保存历史记录，以备回溯。

此外，由于数学表达式可以看作一棵树，求值的过程可以看作对其进行深度优先遍历，因此栈也十分适合表达式解析、求值。

利用栈进行表达式解析和求值#

我们通常书写的表达式，二元运算符在其操作数之间。这种格式被称为中缀表达式，适合人类的直观读写，但由于优先级和括号等复杂规则，对计算机来说难以求解。

和中缀表达式对应的还有另外两种表达式：前缀表达式和后缀表达式，又称波兰式和逆波兰式。二者分别定义为「二元运算符位于其操作数前面/后面」的表达式。这种表达式可以不借助括号就清晰表示运算顺序。

实际上，将表达式看作一棵二叉树之后，上述三种表达式分别对应这棵二叉树的前/中/后序遍历，详见搜索算法 ↗。例如：

$1+2\times( 5-3 )$ 的表达式树就是：

flowchart TD

	plus(("+")) --> times(("×")) --> 2((2))
	times --> minus(("-")) --> 5((5))
	minus --> 3((3))
	plus ---> 1((1))

其前缀表达式为：$+\ 1\ \times\ 2\ -\ 5\ 3$；后缀表达式为：$1\ 2\ 5\ 3\ -\ \times\ +$.

使用一个栈，我们可以方便地把中缀表达式转换为后缀表达式。而对该过程稍加修改，我们也可以使用两个栈求出表达式的值或者建立表达式树。

中缀表达式转后缀表达式#

维护一个「运算符栈」，然后从左到右遍历中缀表达式：

1. 遇到数字 → 直接输出
2. 遇到运算符 → 直到栈为空，或者栈顶是「优先级相同或更低」的运算符，或者栈顶是「左括号」，否则不断输出并弹出栈顶；把当前运算符压入栈
3. 遇到左括号 → 直接压入栈
4. 遇到右括号 → 不断输出并弹出栈顶，直到弹出一个左括号；不要把右括号压入栈

最后，如果栈里面还有运算符，不断输出并弹出栈顶。

这个算法源自 Dijkstra 的调度场算法。

表达式求值#

在刚刚的算法基础上，我们不直接输出数字，而是把要输出的数字也存入一个「数字栈」中。然后在每次输出运算符时，取出「数字栈」的顶部两个数字，按照该运算符进行运算，然后把得到的结果数字重新压入「数字栈」。

之后，如果「运算符栈」里面还有运算符（此时「数字栈」里面也必然有对应数量的剩余数字），不断弹出运算符，并取出数字进行运算，再将结果压回「数字栈」。

最后，数字栈中会剩下唯一的数字，即结果。

建立表达式树#

继续在刚刚的算法基础上，我们把「数字栈」替换为「表达式树节点栈」，并把 “取出「数字栈」的顶部两个数字，按照该运算符进行运算，然后把得到的结果数字重新压入「数字栈」” 替换为 “取出「表达式树节点栈」的顶部两个节点，以该运算符节点为根，连接这两个节点，然后把该运算符节点压入「表达式树节点栈」”。

最后，按照算法流程连接起来的树就是表达式树。

队列#

队列同样是一种操作受限的线性表。与栈不同的是，它允许在表的一端进行插入，在另一端进行删除。进行插入的一端称为队尾 (Rear/Tail)，进行删除的一端称为队头 (Front/Head)。队列严格遵循先进先出 (FIFO, First In First Out) 的原则。在队尾添加元素称为入队 (Enqueue)，在队头移除元素称为出队 (Dequeue)。