第三章 栈、队列和数组

3.1 栈（Stack）

一、栈的基本概念

栈（Stack）：只允许在一端进行插入和删除操作的线性表。允许操作的一端称为栈顶（top），不允许操作的一端称为栈底（bottom）。

核心特征：后进先出（LIFO, Last In First Out）

🗣️ 大白话：栈就像一摞盘子——你只能从最上面放盘子（入栈/压栈），也只能从最上面拿盘子（出栈/弹栈）。最后放上去的盘子最先被拿走，这就叫"后进先出"。

🔗 【跨学科联动·OS/计组】 栈在操作系统中无处不在：

• 函数调用栈：每次函数调用时，OS 将返回地址、局部变量、参数压入栈帧（Stack Frame），函数返回时弹出恢复现场。这就是为什么递归过深会导致栈溢出（Stack Overflow）。
• 中断处理：CPU 响应中断时，自动将 PC（程序计数器）和 PSW（程序状态字） 压栈保存现场，中断返回时弹栈恢复。
• 表达式求值：编译原理中用栈实现中缀→后缀表达式转换，本质是利用栈的 LIFO 特性处理运算符优先级。
• 计组中的堆栈寻址方式（SP 寄存器指向栈顶）也与此直接相关。

基本操作：

• Push(&S, x)：入栈（压栈），将元素 x 加入栈顶
• Pop(&S, &x)：出栈（弹栈），弹出栈顶元素
• GetTop(S, &x)：读栈顶元素（不删除）
• StackEmpty(S)：判断栈是否为空

二、栈的顺序存储实现

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

class SqStack {
    static final int MaxSize = 50;
    int[] data = new int[MaxSize];
    int top = -1;   // 栏顶指针

    boolean isEmpty() { return top == -1; }
    boolean isFull()  { return top == MaxSize - 1; }
    void push(int x)  { data[++top] = x; }
    int pop()         { return data[top--]; }
    int getTop()      { return data[top]; }
}

初始化：S.top = -1（栈空时 top 为 -1）

⚠️ 另一种初始化：S.top = 0（top 指向栈顶元素的下一个位置）

• 栈空：S.top == 0
• 入栈：S.data[S.top++] = x
• 出栈：x = S.data[--S.top]

共享栈：两个栈共享同一片存储空间，一个从底部向上长，一个从顶部向下长：

• 栈1的栈顶指针 top0 从 -1 开始增长
• 栈2的栈顶指针 top1 从 MaxSize 开始减小
• 栈满条件：top0 + 1 == top1

三、栈的链式存储实现

typedef struct Linknode {
    ElemType data;
    struct Linknode *next;
} *LiStack;

class LiStackNode {
    int data;
    LiStackNode next;
    LiStackNode(int data) {
        this.data = data;
        this.next = null;
    }
}
// 链式栈的入栈和出栈都在链表头部进行（头插法/头删法）

通常以链表头部作为栈顶，入栈和出栈都在链表头部进行（便于操作，$O(1)$）。

四、栈的出栈序列问题（卡特兰数）

$n$ 个不同元素依次进栈，合法出栈序列的总数为卡特兰数：

$\frac{1}{n+1}C_{2n}^{n} = \frac{(2n)!}{(n+1)! \cdot n!}$

🗣️ 大白话：3个元素（1,2,3）依次入栈，问有多少种合法的出栈顺序？答案是5种。不合法的例子：3,1,2 是不可能的——因为3先出来意味着1,2都在栈里，此时2在1上面，所以2必须先于1出栈。

3.2 队列（Queue）

一、队列的基本概念

队列（Queue）：只允许在一端插入（队尾 rear）、另一端删除（队头 front）的线性表。

核心特征：先进先出（FIFO, First In First Out）

🗣️ 大白话：队列就像排队买饭——先来的先买，后来的排后面。从队尾进来，从队头出去。

🔗 【跨学科联动·OS/计网】 队列在其他学科中的应用：

• OS·进程调度：就绪队列（FCFS 调度）、多级反馈队列调度都基于队列
• OS·磁盘调度：FCFS 磁盘调度算法就是一个请求队列
• OS·缓冲区：生产者-消费者模型中的缓冲池本质是循环队列
• 计网·分组交换：路由器的输入/输出缓冲区就是队列（FIFO），队列满时发生丢包
• BFS 使用队列而 DFS 使用栈——这是考试中要求区分的核心对比点

二、队列的顺序实现——循环队列

问题：用普通数组实现队列时会出现"假溢出"（数组前面有空位但无法使用）。

解决方案：循环队列——把数组首尾相连，形成逻辑上的"环"。

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

class SqQueue {
    static final int MaxSize = 50;
    int[] data = new int[MaxSize];
    int front = 0, rear = 0;

    void enQueue(int x) {
        data[rear] = x;
        rear = (rear + 1) % MaxSize;
    }
    int deQueue() {
        int x = data[front];
        front = (front + 1) % MaxSize;
        return x;
    }
    int size() {
        return (rear - front + MaxSize) % MaxSize;
    }
    boolean isEmpty() { return front == rear; }
    boolean isFull()  { return (rear + 1) % MaxSize == front; }
}

关键操作（用取模运算实现循环）：

如何区分队空和队满？（三种方法）

⚠️ 2011年真题考点：当 front 和 rear 分别指向队头元素和队尾元素（而非队尾元素的下一个位置）时，初始化需要特殊处理。

若要求第1个入队元素存储在 A[0]，且入队操作为 rear = (rear+1)%n; A[rear] = x（先移动再存值），则初始时 front = 0, rear = n-1。这样第一次入队时 rear = (n-1+1)%n = 0，元素存入 A[0]。

💡 记忆：rear 指向队尾元素（而非下一个位置）的方案中，rear 初值 = front 前一个位置。

🗣️ 大白话：最常用的是"牺牲一个位置"。就像圆形跑道上有50个座位，我们只坐49个，留一个空座位——如果队尾追上队头（差一个位置），就说明满了；如果队头等于队尾，就说明空了。

三、队列的链式实现

typedef struct LinkNode {   // 链式队列结点
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct {            // 链式队列
    LinkNode *front, *rear; // 队头和队尾指针
} LinkQueue;

class LinkNode {
    int data;
    LinkNode next;
    LinkNode(int data) {
        this.data = data;
        this.next = null;
    }
}
class LinkQueue {
    LinkNode front, rear;  // 队头和队尾指针
    LinkQueue() {
        front = rear = new LinkNode(0);  // 带头结点
    }
    void enQueue(int x) {
        LinkNode s = new LinkNode(x);
        rear.next = s;
        rear = s;
    }
    int deQueue() {
        LinkNode p = front.next;
        int x = p.data;
        front.next = p.next;
        if (rear == p) rear = front;  // 最后一个元素出队
        return x;
    }
    boolean isEmpty() { return front == rear; }
}

• 带头结点：Q.front == Q.rear 时为空（都指向头结点）
• 不带头结点：Q.front == NULL 时为空

四、双端队列

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

• 输出受限的双端队列：一端允许插入和删除，另一端只允许插入
• 输入受限的双端队列：一端允许插入和删除，另一端只允许删除

⚠️ 考研爱考：给定输入序列，判断某个输出序列是否可能通过双端队列实现。

判断方法：

• 普通队列：只能产生 FIFO 顺序
• 普通栈：只能产生 LIFO 顺序（可用卡特兰数计算总数）
• 输入受限的双端队列：能产生的序列 ⊇ 栈能产生的序列（因为两端都可以输出）
• 输出受限的双端队列：能产生的序列 ⊇ 栈能产生的序列（因为两端都可以输入）
• 某些序列既不能由栈产生也不能由队列产生，但可以由双端队列产生

💡 考研选择题通常给出4个序列，问哪些不能由某种双端队列产生。解题方法：逐个模拟，用草稿纸画出双端队列的操作过程。

3.3 栈和队列的应用

一、栈在括号匹配中的应用

算法思路：依次扫描每个字符：

1. 遇到左括号——入栈
2. 遇到右括号——检查栈顶是否配对
   • 配对成功——弹出栈顶元素
   • 配对失败——匹配失败
3. 扫描完毕后栈空——匹配成功

二、栈在表达式求值中的应用

三种表达式：

中缀转后缀（手工方法）：

1. 按运算符优先级对中缀表达式加括号
2. 将运算符移到对应括号的后面
3. 去掉所有括号

例：$A + B \times C - D$ → $((A + (B \times C)) - D)$ → $((A\ (B\ C\times)+)\ D-)$ → $A\ B\ C \times + D -$

中缀转后缀（机器算法，用运算符栈）：

从左到右扫描中缀表达式：

1. 遇到操作数——直接加入后缀表达式
2. 遇到左括号 (——入栈
3. 遇到右括号 )——依次弹出栈中运算符加入后缀表达式，直到遇到左括号（左括号出栈但不加入）
4. 遇到运算符——与栈顶运算符比较优先级：
   • 若栈空、栈顶为 ( 、或当前运算符优先级高于栈顶运算符 → 入栈
   • 否则 → 弹出栈顶运算符加入后缀表达式，重复比较新栈顶，直到可以入栈
5. 扫描完毕 → 依次弹出栈中所有运算符加入后缀表达式

💡 优先级规则：× / 高于 + -。相同优先级时弹出栈顶（左结合）。

详细示例：中缀 A*(B+C)-D → 后缀

中缀转前缀：从右到左扫描，规则类似但方向相反。

【2012年408真题】 含复杂嵌套括号的完整示例：a+b-a*((c+d)/e-f)+g → ab+acd+e/f-*-g+

💡 栈中操作符最大同时存在数为5（步骤8~10：#-*((+）。这是2012年真题考查的核心点。

后缀表达式求值（用栈）：

1. 从左到右扫描后缀表达式
2. 遇到操作数——入栈
3. 遇到运算符——弹出两个操作数，计算结果入栈
4. 最终栈中唯一元素就是结果

🗣️ 大白话：后缀表达式对计算机很友好——不需要考虑优先级和括号，从左到右扫一遍就算完了。这就是为什么编译器内部都先把表达式转成后缀的。

三、栈在递归中的应用

系统在执行递归函数时，会使用一个递归工作栈。每次递归调用时，将当前函数的局部变量、返回地址等信息压入系统栈中，形成一个栈帧（Stack Frame）；递归返回时弹出栈帧恢复现场。

递归工作栈中每个栈帧包含：

• 局部变量
• 形参
• 返回地址
• （其他现场信息）

递归的空间复杂度 = 递归调用的最大深度（即递归栈的最大长度）

⚠️ 递归的缺点：

• 递归层数太深 → 栈溢出（Stack Overflow）
• 重复计算（如朴素的 Fibonacci 递归 → 指数级时间复杂度）→ 可用记忆化搜索或动态规划优化
• 递归效率通常低于等价的迭代实现（因为函数调用开销）

💡 递归转非递归：可以利用显式栈模拟系统递归栈来消除递归（如非递归DFS、非递归中序遍历）。

四、队列的应用

1. 层次遍历（如二叉树的层序遍历）
2. 计算机系统中的应用：
   • CPU 调度中的就绪队列
   • 打印机的打印缓冲区
   • 消息队列

3.4 数组和特殊矩阵的压缩存储

一、数组

多维数组的存储：

• 行优先存储：一行一行地按顺序存储（C语言采用）
• 列优先存储：一列一列地按顺序存储（Fortran采用）

二维数组 $A[m][n]$ 按行优先存储，元素 $A[i][j]$ 的地址为：

$LOC(A[i][j]) = LOC(A[0][0]) + (i \times n + j) \times sizeof(ElemType)$

二、特殊矩阵的压缩存储

⚠️ 审题陷阱：矩阵元素下标通常从 1 开始（$a_{1,1}$），数组下标默认从 0 开始（$B[0]$）。题目如果说"数组下标从1开始"，公式需要调整！

对称矩阵（$a_{ij} = a_{ji}$）：只存储下三角区（含主对角线），$n$ 阶对称矩阵只需 $\frac{n(n+1)}{2}$ 个存储单元。

元素 $a_{ij}$（$i \geq j$）在一维数组 $B[0, \ldots]$ 中的下标 $k$：

$k = \frac{i(i-1)}{2} + j - 1 \quad (i \geq j)$

若 $i < j$，则 $k = \frac{j(j-1)}{2} + i - 1$（利用对称性 $a_{ij} = a_{ji}$）

下三角矩阵（上三角区元素全为常量 $c$）：

• 下三角区（$i \geq j$）：$k = \frac{i(i-1)}{2} + j - 1$
• 常量 $c$ 统一存放在最后：$k = \frac{n(n+1)}{2}$
• 共需 $\frac{n(n+1)}{2} + 1$ 个存储单元

上三角矩阵（下三角区元素全为常量 $c$）：

• 上三角区（$i \leq j$）：$k = \frac{(i-1)(2n-i+2)}{2} + j - i$
• 常量 $c$ 存在最后

三对角矩阵（带状矩阵）：

• 元素 $a_{ij}$ 只在 $|i-j| \leq 1$ 时非零
• 按行优先存储时，$a_{ij}$ 的下标 $k = 2i + j - 3$（行列号从1开始，$k$ 从0开始）
• 反向公式（已知 $k$ 求 $i,j$）：$i = \lfloor(k+1)/3\rfloor + 1$，$j = k - 2i + 3$

稀疏矩阵：非零元素远少于矩阵元素总数。

• 三元组表表示：(行号, 列号, 值)，此外还需存储矩阵的总行数和总列数（2023年真题考点）
• 十字链表表示：每行一个链表、每列一个链表，交叉组成十字形

⚠️ 2018年408真题：上三角矩阵按行存入一维数组 $N$，元素 $m_{6,6}$ 在 $N$ 中的下标为50。上三角公式关键：第 $i$ 行有 $n-i+1$ 个元素（$i$ 从1开始），$m_{i,j}$ 的下标 $k = \frac{(i-1)(2n-i+2)}{2} + j - i$。

⚠️ 2021年408真题：下三角矩阵行优先存储，已知 $A[3][3]$ 地址为220，求 $A[5][5]$ 地址。用公式计算二者之间的元素个数即可。

📝 真题剖析

【2014年408真题】 一个栈的入栈序列为 1, 2, 3, ..., n，其出栈序列为 $p_1, p_2, p_3, \ldots, p_n$。若 $p_2 = 3$，则 $p_3$ 可能的取值个数为（）。

A. $n-3$   B. $n-2$   C. $n-1$   D. 无法确定

解析：

$p_2 = 3$ 意味着第2个出栈的元素是3。

分析 $p_1$ 的可能值：

• 若 $p_1 = 1$：先入1出1，再入2入3，出3。此时栈中有2，接下来可入4,5,...再出，$p_3$ 可以是 2, 4, 5, ..., n 中的任一个。
• 若 $p_1 = 2$：先入1入2，出2，再入3，出3。此时栈中有1，$p_3$ 可以是 1, 4, 5, ..., n。
• 若 $p_1 = 4$：先入1入2入3入4，出4出3。此时栈中有1和2，$p_3$ 可以是 2, 5, 6, ..., n。

综合分析，$p_3$ 不可能是 3（已出栈），可以是 1, 2, 4, 5, ..., n 中的任一个，共 $n-1$ 个。

答案选C。

📌 第三章总结