栈
1. 括号匹配问题
1.1 概述
在代码编写中，若括号不匹配编译器会报错。最后出现的左括号最先被匹配（最里层被外层包裹），符合后进先出（LIFO）性质，可用栈解决。
1.2 算法演示
遵循规则：
- 左括号入栈。若遍历结束栈非空，则缺少右括号。
- 右括号出现时，检查栈顶是否为匹配的左括号。若不匹配或栈空，则错误。
1.3 算法实现
遍历字符串，根据字符类型执行入栈或出栈操作，最终判断栈是否为空且无匹配错误。
1.4 小结
利用栈的 LIFO 特性可有效检测括号是否成对出现。
2. 表达式求值问题
2.1 引言
操作数为数字，运算符为 +、-、*、/。数学家提出不用括号的表示法，即前缀表达式（波兰表达式）和后缀表达式（逆波兰表达式）。
2.2 简述
- 中缀：运算符在两个操作数中间。
- 后缀：运算符在两个操作数后面。
- 前缀：运算符在两个操作数前面。
2.3 中缀转后缀（手算）
使用'左优先原则'保证运算顺序唯一。观察运算符优先级和结合性进行转换。
2.4 后缀表达式的计算
2.4.1 手算
遇到操作数入栈，遇到运算符弹出两个操作数计算后将结果压栈，重复直至得到最终结果。
2.4.2 机算
表达式：AB+CD*E/-F+
步骤 | 栈内容（从底到顶）
---|---
1.A|[A]
2.B|[A,B]
3.+|[A+B]
4.C|[A+B,C]
5.D|[A+B,C,D]
6.*|[A+B,C*D]
7.E|[A+B,C*D,E]
8./|[A+B,(C*D)/E]
9.-|[(A+B)-((C*D)/E)]
10.F|[(A+B)-((C*D)/E),F]
11.+|[((A+B)-((C*D)/E))+F]
2.5 中缀转前缀（手算）
转为前缀表达式采用'右优先原则'，逻辑与后缀相反。
2.6 前缀表达式的计算
从右向左扫描，操作数入栈，遇运算符弹栈计算。示例如下：
| 步骤 | 元素 | 栈（从底到顶） | 说明 |
|---|---|---|---|
| 1 | 1 | [1] | 入栈 |
| 2 | 1 | [1,1] | 入栈 |
| 3 | + | [2] | 1+1=2 |
| ... | ... | ... | ... |
2.7 小结
后缀和前缀表达式消除了括号依赖，便于计算机处理。
3. 表达式求值问题（续）
3.1 中转后（手算）
包含括号的中缀表达式转后缀时，需处理括号优先级。
3.2 中转后（机算）
正常无括号形式与加括号形式处理逻辑一致，括号作为界限符控制入栈时机。
3.3 小结
通过双栈法或单栈法可实现中缀转后缀并计算。
4. 栈在递归中的应用
4.1 函数调用背后的过程
A 调用 B，B 调用 C，C 结束返回 B，B 结束返回 A。最后调用的函数最先结束，符合后进先出特性。
4.2 递归
递归即函数自己调用自己。
4.2.1 阶乘
递归调用时参数 n 依次减小至 1，返回时依次相乘。
4.2.2 斐波那契数列
典型递归案例，需注意效率优化。
4.3 小结
系统栈自动管理递归调用过程。
队列
1. 树的层次遍历
先进先出（FIFO）：
- 先访问根节点（第 1 层）。
- 再访问子节点（第 2 层）。
- 依此类推。
2. 图的广度优先遍历
先进先出（FIFO）：
- 先访问起点。
- 再访问邻居节点。
- 然后访问下一层邻居。
3. 在操作系统中的应用
用于进程调度等场景。
矩阵的压缩存储
涉及线性代数知识。
1. 数组的存储结构
1.1 一维数组的存储结构
连续内存空间存储。
1.2 二维数组的存储结构
分为行优先和列优先两种映射方式。
2. 矩阵的存储结构
2.1 普通矩阵
按常规方式存储。
2.2 对称矩阵
上下三角区数据重复，只存一个三角区以节约空间。
2.3 三角矩阵
上三角或下三角区为同一元素，可省略空间。
2.4 带状矩阵
非零元素集中在对角线附近，其余为 0，可省略大量空间。
2.5 稀疏矩阵
有效数据少，按位置排列存储，节约空间。
2.6 小结
针对特殊矩阵采用压缩存储可显著降低空间复杂度。
