栈、队列和数组

3.1 栈

栈的定义

栈（Stack）是只允许在一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。栈遵循**后进先出（LIFO）**原则。

基本操作：

InitStack(&S)：初始化栈
Push(&S, e)：元素 e 入栈
Pop(&S, &e)：栈顶元素出栈，用 e 返回
GetTop(S, &e)：读取栈顶元素
StackEmpty(S)：判断栈是否为空

💡 记忆技巧：栈就像"一摞盘子"，你只能从最上面拿盘子，也只能把新盘子放在最上面。

顺序栈

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int top;  // 栈顶指针
} SqStack;

初始化：S.top = -1; 入栈：S.data[++S.top] = e; 出栈：e = S.data[S.top--]; 判空：S.top == -1 判满：S.top == MaxSize - 1

链式栈

链式栈用单链表实现，以头结点后的第一个结点作为栈顶，所有操作都在链表头部进行。

typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} *LinkStack;

入栈（头插法）：s->next = S->next; S->next = s; 出栈：p = S->next; S->next = p->next; free(p);

栈的应用

括号匹配

遍历表达式，遇到左括号入栈，遇到右括号时检查栈顶是否匹配。若匹配则弹出，不匹配则错误。最后检查栈是否为空。

表达式求值（中缀转后缀）

中缀表达式 a + b * c - d 转为后缀表达式 a b c * + d - 的规则：

操作数直接输出。
运算符入栈，但遇到优先级低于或等于栈顶运算符时，先弹出栈顶运算符。
左括号直接入栈，右括号则弹出直到左括号。

后缀表达式求值

从左到右扫描后缀表达式，遇到操作数入栈，遇到运算符则弹出两个操作数运算，结果入栈。

函数调用

函数调用时，系统用栈保存返回地址、局部变量等信息。每次函数调用对应一次入栈，返回对应一次出栈。

栈的递归应用

递归函数的核心思想是"自己调用自己"，系统通过栈自动完成递归调用和返回。每层递归会创建新的栈帧，包含参数、局部变量和返回地址。

递归的缺点：效率低，空间复杂度高（可能栈溢出）。 递归转非递归：很多时候可以用栈模拟递归过程。

栈的经典问题

迷宫求解：利用栈保存走过的路径，遇到死路时回溯（出栈），直到找到出口。

进制转换：将十进制数反复除以基数，将余数入栈，最后依次出栈即得结果。例如十进制 10 转二进制：10÷2=5余0→5÷2=2余1→2÷2=1余0→1÷2=0余1，栈从底到顶为 0→1→0→1，出栈得 1010。

共享栈

两个栈共享一块连续的存储空间，分别从两端向中间生长。栈1的栈底在 0，栈2的栈底在 MaxSize-1。

判满：top1 + 1 == top2
优点：节省空间，只有当整个存储空间用完时才真的满。

括号匹配算法的完整描述

初始化一个空栈 S
遍历表达式中的每个字符 ch:
  if ch 是左括号 '(' 或 '[' 或 '{':
    Push(S, ch)
  else if ch 是右括号 ')' 或 ']' 或 '}':
    if StackEmpty(S): 匹配失败（右括号多余）
    top = Pop(S)
    if ch 和 top 不匹配: 匹配失败（括号不匹配）
遍历结束后:
  if StackEmpty(S): 匹配成功
  else: 匹配失败（左括号多余）

中缀转后缀算法的详细规则

操作数直接加入后缀表达式。
遇到运算符时，若栈为空或栈顶为 '('，则直接入栈。否则，将栈中优先级大于等于该运算符的运算符依次弹出，再将该运算符入栈。
遇到 '(' 直接入栈。
遇到 ')' 将栈中直到 '(' 的运算符依次弹出（'(' 不加入表达式）。
扫描结束后，将栈中剩余运算符依次弹出。

运算符优先级（从高到低）：乘除 (*, /) > 加减 (+, -) > 左括号 (()。

后缀表达式求值的详细过程

初始化空栈 S
遍历后缀表达式中的每个 token:
  if token 是操作数:
    Push(S, token)
  else (token 是运算符):
    右操作数 = Pop(S)
    左操作数 = Pop(S)
    结果 = 左操作数 token 右操作数
    Push(S, 结果)
最终栈顶元素即为表达式的值

⚠️ 易错点：注意运算符是"左操作数 op 右操作数"，出栈时先弹出的是右操作数。

3.2 队列

队列的定义

队列（Queue）是只允许在一端插入、另一端删除的线性表。允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。队列遵循**先进先出（FIFO）**原则。

基本操作：

InitQueue(&Q)：初始化队列
EnQueue(&Q, e)：元素 e 入队
DeQueue(&Q, &e)：队头元素出队，用 e 返回
GetHead(Q, &e)：读取队头元素
QueueEmpty(Q)：判断队列是否为空

💡 记忆技巧：队列就像"排队买票"，先来的人先买票离开，后来的人排在后面。

循环队列（重点）

为了解决假溢出问题，将顺序队列从逻辑上首尾相连形成循环队列。

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int front;  // 队头指针
    int rear;   // 队尾指针
} SqQueue;

判空判满条件（有两种常用方式）：

方式一：牺牲一个存储单元

队空条件：Q.front == Q.rear
队满条件：(Q.rear + 1) % MaxSize == Q.front
队列长度：(Q.rear - Q.front + MaxSize) % MaxSize

入队：Q.rear = (Q.rear + 1) % MaxSize; Q.data[Q.rear] = e; 出队：e = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize;

方式二：增设 size 变量

typedef struct {
    ElemType data[MaxSize];
    int front, rear;
    int size;  // 队列当前长度
} SqQueue;

队空：size == 0
队满：size == MaxSize

方式三：增设 tag 变量

初始 tag = 0。
入队成功 tag = 1，出队成功 tag = 0。
判满：front == rear && tag == 1
判空：front == rear && tag == 0

📌 408考点提示：循环队列的判空判满是高频选择题考点，尤其是牺牲一个存储单元的方式。注意：题目可能会用不同的初始条件（如 front 指向队头元素还是队头前一个位置），需要灵活判断。

链式队列

typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct {
    LinkNode *front, *rear;
} LinkQueue;

初始化：Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode)); Q.front->next = NULL; 入队：s->data = e; s->next = NULL; Q.rear->next = s; Q.rear = s; 出队：p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free(p);

双端队列

双端队列（Deque）允许在两端进行插入和删除操作。

输入受限的双端队列：一端允许插入和删除，另一端只允许删除（相当于一个栈加一个队列）。
输出受限的双端队列：一端允许插入和删除，另一端只允许插入。

栈和队列的对比

特性	栈	队列
基本原则	后进先出（LIFO）	先进先出（FIFO）
插入操作	仅栈顶	队尾
删除操作	仅栈顶	队头
应用场景	括号匹配、函数调用、表达式求值	缓冲区、层次遍历、BFS
实现方式	顺序栈/链式栈	顺序队列/循环队列/链式队列

3.3 数组的存储结构

行优先和列优先

对于二维数组 A[m][n]：

行优先存储：先存第一行，再存第二行... 元素 A[i][j] 的地址：LOC(i,j) = LOC(0,0) + (i×n + j)×L 其中 L 为每个元素占用的存储单元数。

列优先存储：先存第一列，再存第二列... 元素 A[i][j] 的地址：LOC(i,j) = LOC(0,0) + (j×m + i)×L

3.4 特殊矩阵的压缩存储

对称矩阵

A[i][j] = A[j][i]，只需存储上三角或下三角（含对角线），共 n(n+1)/2 个元素。

下三角（行优先）映射（下标从 1 开始）：

当 i ≥ j（下三角区域+对角线）：k = i(i-1)/2 + j - 1
当 i < j（上三角区域）：k = j(j-1)/2 + i - 1

示例：4×4 对称矩阵，a₃₂（即第3行第2列）在一维数组中的位置： k = 3×2/2 + 2 - 1 = 3 + 1 = 4（0-based 第4个元素）

三角矩阵

下三角矩阵：下三角和主对角线元素各自不同，上三角元素为同一常数（通常为 0 或 c）。共需 n(n+1)/2 + 1 个存储单元（多出的一个存常数）。
上三角矩阵：上三角和主对角线元素各自不同，下三角元素为同一常数。

上三角矩阵（行优先）映射（下标从 1 开始）：

当 i ≤ j（上三角区域+对角线）：k = (i-1)(2n-i+2)/2 + (j-i)
当 i > j（下三角区域）：常数 C

三对角矩阵（带状矩阵）

只有主对角线及其相邻两侧对角线（三条对角线）上的元素非零。 |i - j| > 1 时元素为 0。

压缩存储方式：将三条对角线的元素按行存储到一维数组中。对于 n×n 的三对角矩阵，非零元素共 3n-2 个。

地址映射：aᵢⱼ 在一维数组中的下标为 2i + j - 3（从 0 开始，需满足 |i-j| ≤ 1）。

稀疏矩阵

非零元素很少（一般远少于零元素）的矩阵。通常非零元素个数 ≤ 矩阵总元素的 5%。

存储方式：

三元组表：(row, col, value)。每个非零元素用一个三元组表示，按行优先顺序排列。
十字链表：每行每列用链表串联非零元素，适合矩阵运算中非零元素频繁变化的情况。

三元组表的转置：将 (i, j, v) 变为 (j, i, v)，并按行优先排列。经典算法需要先统计每列的非零元素个数，再确定每个元素在新表中的位置。

稀疏矩阵

非零元素很少（一般远少于零元素）的矩阵。存储方式：

三元组表：(row, col, value)
十字链表：每行每列用链表串联非零元素

📌 408考点提示：对称矩阵、三角矩阵的压缩存储地址计算是常考选择题。稀疏矩阵通常考三元组表示和转置操作。

⚠️ 易错点：

循环队列判空判满时，注意题目中 front 和 rear 的指向方式（front 指向队头元素还是队头前一个位置）。
栈和队列的"先进/后进"分析题要注意出入顺序的组合可能。
数组地址计算注意下标是 0-based 还是 1-based。

3.5 题型示例

例题1：循环队列存储在数组 A[0..m] 中，头尾指针分别为 front 和 rear，写出队空、队满条件（牺牲一个单元方式）。解：

队空：front == rear
队满：(rear + 1) % (m + 1) == front
元素个数：(rear - front + m + 1) % (m + 1)

例题2：用两个栈模拟一个队列。解：设栈 S1 和 S2。

入队：元素 push 到 S1。
出队：若 S2 不为空，pop S2；若 S2 为空，将 S1 中所有元素依次 pop 并 push 到 S2，然后 pop S2。

共享栈（双端栈）

共享栈是两个栈共用同一块连续存储空间，栈1从低地址向高地址增长，栈2从高地址向低地址增长。

typedef struct {
    ElemType data[MaxSize];
    int top1;   // 栈1的栈顶指针
    int top2;   // 栈2的栈顶指针
} ShStack;

初始化：top1 = -1; top2 = MaxSize;
栈1入栈：S.data[++S.top1] = e;
栈2入栈：S.data[--S.top2] = e;
判满：top1 + 1 == top2

共享栈可以有效利用内存空间，只有当整个数组都满时才真正无法入栈。

队列的应用：杨辉三角（二项式系数）

利用队列逐层生成杨辉三角的每一行。第 i 行有 i+1 个数，每个数是上一行相邻两数之和。

初始化队列 Q，将第一行 [1] 入队
对于 i 从 1 到 n:
  在队尾插入 0（辅助计算）
  出队一个元素 s = Q.front
  循环 i+1 次:
    出队 t = Q.front
    入队 s + t
    s = t

优先队列

优先队列是一种特殊的队列，出队操作删除优先级最高（或最低）的元素。堆是实现优先队列的常用方式（见排序章节）。

队列在操作系统中的应用

先来先服务（FCFS）调度：就绪队列。
缓冲区的实现：I/O 请求排队。
消息队列：进程间通信。

队列在计算机系统中的应用

CPU 任务调度：就绪队列、阻塞队列。
页面置换算法：FIFO 页面置换。
广度优先搜索：图/树的层序遍历。

数组的存储结构补充

对于三维数组 A[d₁][d₂][d₃]：

行优先：LOC(i,j,k) = LOC(0,0,0) + (i×d₂×d₃ + j×d₃ + k)×L
列优先：LOC(i,j,k) = LOC(0,0,0) + (k×d₂×d₁ + j×d₁ + i)×L

示例3：中缀表达式 (a + b) * c + d / e 转为后缀表达式。解：

扫描     输出          栈
a        a
+        a             +
b        a b           +
)        a b +         (弹出直到"(")
*        a b +         *
c        a b + c       *
+        a b + c *     +
d        a b + c * d   +
/        a b + c * d   +/
e        a b + c * d e +/
结束      a b + c * d e / +

后缀表达式：a b + c * d e / +

本章总结

栈和队列是两种重要的受限线性表，它们的区别在于操作受限的位置不同。栈适用于需要"回溯"的场景（如括号匹配、函数递归），队列适用于需要"按序处理"的场景（如 BFS、缓冲区）。数组的压缩存储则是节省空间的重要技巧，各类矩阵的地址映射需要熟练掌握。

栈、队列和数组