3.1 栈的定义

栈的特性是 后进先出 (LIFO, Last In First Out)：最后入栈的元素最先出栈。

3.2 栈的基本操作

• InitStack(&S) / StackEmpty(S)：初始化 / 判空。
• Push(&S, x)：进栈，新元素 x 成为栈顶。
• Pop(&S, &x)：出栈，弹出栈顶元素并赋给 x。
• GetTop(S, &x) / Top(S)：读栈顶元素，但不删除。

进出栈序列与 Catalan 数

对入栈序列 1,2,…,n，其合法的出栈序列数即 n 个元素的不同出栈顺序数，等于 第 n 个卡特兰数：

Cₙ = C(2n, n) / (n+1) = (2n)! / [(n+1)! · n!]

当 n=3 时，C₃=5，1,2,3 的合法出栈序列共 5 种：1 2 3、1 3 2、2 1 3、2 3 1、3 2 1。注意 3 1 2 非法。

3.3 栈的应用

1. 括号匹配

扫描表达式，遇左括号入栈，遇右括号则与栈顶左括号匹配并出栈；若栈空或不匹配则出错；扫描结束栈空即匹配成功。

2. 递归调用

函数调用时，系统用递归工作栈保存每层的实参、局部变量和返回地址。递归深度过大会导致栈溢出。递归 → 迭代转换常借助显式栈。

3. 表达式求值

借助运算符栈和操作数栈实现。常见三种表达式：

• 前缀（波兰）：运算符在前，如 + A B。
• 中缀：常规形式 A + B，需考虑优先级与括号。
• 后缀（逆波兰 RPN）：运算符在后，如 A B +，无括号、按顺序求值，最适合计算机处理。

3.4 队列的定义

基本操作：InitQueue、QueueEmpty、EnQueue（入队）、DeQueue（出队）、GetHead（取队头）。

3.5 循环队列

顺序队列会发生"假溢出"（rear 到达数组末尾但前端有空位）。将数组视为首尾相接的环，即循环队列。设数组大小 MaxSize：

• 初始 / 队空：front == rear
• 入队：Q.data[Q.rear] = x; Q.rear = (Q.rear+1) % MaxSize
• 出队：x = Q.data[Q.front]; Q.front = (Q.front+1) % MaxSize
• 队满（牺牲一个单元）：(Q.rear+1) % MaxSize == Q.front
• 队中元素个数：(Q.rear - Q.front + MaxSize) % MaxSize

3.6 双端队列

允许两端都可以进行入队和出队操作的队列。进一步受限可派生出：

• 输入受限的双端队列：一端只能入队，两端可出队。
• 输出受限的双端队列：一端只能出队，两端可入队。

3.7 多维数组的存储

高级语言中的多维数组在内存中必须映射为一维线性地址，主要有两种映射方式。

1. 按行优先（行主序 Row-major）

先按行号从小到大排列，同一行内按列号从小到大排列。C/C++、Pascal 等语言采用此方式。

• 二维数组 A[m][n]：元素 A[i][j] 前有完整的 i 行（共 i×n 个元素）再加该行前 j 个元素。
• 地址公式：LOC(A[i][j]) = LOC(A[0][0]) + (i×n + j) × L（L 为每个元素所占字节数）。
• 三维数组 A[p][m][n]：LOC(A[i][j][k]) = LOC(A[0][0][0]) + (i×m×n + j×n + k) × L。

2. 按列优先（列主序 Column-major）

先按列号从小到大排列，同一列内按行号从小到大排列。Fortran、MATLAB 等语言采用此方式。

• 二维数组 A[m][n]：元素 A[i][j] 前有完整的 j 列（共 j×m 个元素）再加该列前 i 个元素。
• 地址公式：LOC(A[i][j]) = LOC(A[0][0]) + (j×m + i) × L。

n 维数组的一般化地址映射公式

设 n 维数组声明为 A[d₁][d₂]…[dₙ]，元素 A[i₁][i₂]…[iₙ] 的存储位置：

• 按行优先：LOC = base + (i₁×d₂×d₃×…×dₙ + i₂×d₃×…×dₙ + … + iₙ₋₁×dₙ + iₙ) × L
• 按列优先：LOC = base + (iₙ×dₙ₋₁×…×d₁ + iₙ₋₁×dₙ₋₂×…×d₁ + … + i₂×d₁ + i₁) × L

本质上，按行优先是从最左维向最右维"展开"，按列优先则是从最右维向最左维"展开"。可以通过计算前面完整"块"的个数来推导任一元素的偏移量。

按行优先 vs 按列优先示例

以二维数组 A[3][4] 为例，设 LOC(A[0][0])=100，L=4 字节：

3.8 特殊矩阵的压缩存储

对含大量重复或对称元素的矩阵，可只存部分元素以节省空间，并建立映射关系 (i,j) → k（1 下标）。

1. 对称矩阵

满足 a[i][j]=a[j][i]。只存下三角（含主对角线），按行优先存入一维数组 B，大小 n(n+1)/2。

if i >= j: k = i(i-1)/2 + j-1
else:       k = j(j-1)/2 + i-1   // 对称映射到下三角

2. 三角矩阵

下三角矩阵：下三角存元素，上三角全为常数 c。存下三角 n(n+1)/2 个 + 1 个常数，共 n(n+1)/2+1。上三角矩阵类似。

3. 三对角矩阵

仅主对角线及其上下相邻两条对角线有非零元，共 3n−2 个元素。按行优先映射：

k = 2i + j - 3   // |i-j| <= 1 时，1 下标

3.9 栈入栈出过程可视化

对入栈序列 1 2 3 4，对比两种典型操作：① 入栈即出栈（出栈序 = 入栈序）；② 全部入栈后出栈（出栈序反转）。这正是 LIFO 特性的体现。

3.10 括号匹配动画演示

栈的经典应用：扫描表达式，遇左括号入栈、遇右括号匹配栈顶。选择不同示例观察匹配成功/失败的场景。

3.11 表达式求值动画演示

经典双栈算法: 阶段1中缀->后缀(调度场算法), 阶段2后缀求值。演示 3+4*(5-2) 的计算过程。