第3章栈、队列和数组（自学版）¶

章节定位：结构过渡章

这一章把线性结构进一步推进到受限存取结构，并首次系统进入数组地址计算与压缩存储。
建议先掌握栈和队列的核心操作，再集中攻克括号匹配、表达式求值和特殊矩阵映射。

1. 本章定位¶

这一章是在线性表之后，对“受限线性结构”和“数组存储思想”的继续展开。

如果说第 2 章主要解决的是：

线性表是什么
顺序表和链表怎么实现

那么第 3 章主要解决的是：

当插入和删除被限制在某些位置时，会出现什么更高效、更有特点的结构
当数据按多维形式组织时，内存里到底怎么存
当矩阵里有大量重复值或大量零时，为什么要压缩存储

所以，这一章其实包含两条主线：

栈与队列：研究“操作受限的线性表”
数组与特殊矩阵：研究“顺序存储的扩展和压缩”

2. 资料准备情况¶

本章已提供以下学习资源：

原文 OCR 底稿已生成：本章 OCR 底稿
页面图像已生成：本章页面图像
本章配套代码已经提供：第3章普通代码版
当前内容可先重点阅读 3.1 栈 的起稿与代码落地

建议按下面顺序继续学习：

3.2 队列
3.3 栈和队列的应用
3.4 数组和特殊矩阵

3. 学习目标¶

学完本章后，你应该至少能做到：

说清楚栈和队列分别限制了什么操作
理解 LIFO 和 FIFO 的本质差别
自己写出顺序栈、共享栈、链栈的基本操作
看懂并分析出栈序列是否合法
理解数组按行优先、列优先存储的地址计算
理解为什么特殊矩阵能压缩存储，以及压缩后下标如何映射

4. 本章结构总览¶

根据 DS.pdf 和 本章 OCR 底稿，第 3 章主干结构为：

3.1 栈
3.2 队列
3.3 栈和队列的应用
3.4 数组和特殊矩阵

这一章的推荐学习顺序不是死记定义，而是：

先把“限制在哪里”搞懂
再把“顺序存储和链式存储怎么写”搞懂
再去看典型应用
最后做数组和压缩存储

5. 章前提醒¶

这一章非常容易出现一种错觉：

“概念不难，所以不用太在意细节”

但真正丢分的地方，往往就在细节里：

栈顶指针初值到底是 -1 还是 0
入栈时到底是“先移动指针再写值”，还是“先写值再移动指针”
队空和队满条件到底怎么判断
数组地址计算时下标是从 0 开始还是从 1 开始
压缩存储时到底只存了哪一部分

所以这一章一定不能只停留在“看懂概念”，而要落实到：

公式
指针
边界条件
真实代码

6. 3.1 栈¶

6.1 栈的基本概念¶

根据原文，栈（Stack）是：

只允许在一端进行插入或删除操作的线性表

这个定义很短，但信息量很大。

先拆开来看：

它首先是线性表
它不是任意位置都能操作
它只允许在同一端进行插入和删除

这就意味着：

栈并没有改变“线性关系”
它改变的是“操作权限”

更形象一点理解：

普通线性表像一排抽屉，你理论上可以在中间某个位置做操作
栈像一摞盘子，你只能从最上面放，也只能从最上面拿

这就是栈最核心的直觉。

6.2 栈顶、栈底、空栈¶

原文里这一组术语必须分清：

栈顶（Top）
允许插入和删除的一端
栈底（Bottom）
固定的一端，通常不直接操作
空栈
不含任何元素的栈

你可以把它想成一摞书：

最上面那本就是“栈顶”
最下面那本所在的一端就是“栈底”
一本书都没有，就是“空栈”

6.3 栈的操作特性：后进先出¶

栈最重要的结论就是：

后进先出
英文是 LIFO，即 Last In First Out

为什么？

因为你总是只能从顶端操作。

例如元素按 1, 2, 3, 4 的顺序入栈：

1 先进去
4 最后进去

那最先能被拿出来的，一定是最上面的 4。

这和排队正好相反，所以后面你学队列时一定要主动对比。

6.4 栈的基本操作¶

原书给出的基本操作思路非常重要，后面做题会默认你已经会这些动作：

InitStack
初始化一个空栈
StackEmpty
判断栈是否为空
Push
入栈
Pop
出栈
GetTop
读取栈顶元素但不出栈
DestroyStack
销毁栈

这里最容易混的是：

Pop 会真的删除栈顶元素
GetTop 只是看一眼，不删除

这个区别在做选择题和写代码时都特别容易被忽略。

6.5 栈为什么这么重要¶

很多同学第一次学栈，会觉得它有点“刻意”：

为什么非要限制只能在一端操作？

原因是这种限制反而带来了特别清晰的行为模式，因此它很适合解决下面这些问题：

括号匹配
表达式求值
递归调用过程
深度优先搜索中的回退
出栈序列合法性判断

也就是说，栈不是为了“多发明一个结构”，而是为了匹配这一类天然具有“回退”“最近进入先处理”特征的问题。

7. 3.1.2 栈的顺序存储¶

7.1 顺序栈的核心思想¶

栈既然是线性表，就可以像顺序表一样，用一段连续内存来存。

这就得到：

顺序栈

原书的核心意思是：

用一组地址连续的存储单元保存元素
再配一个 top 指针，表示当前栈顶位置

所以顺序栈的关键不是数组本身，而是：

数组 + top

7.2 top 到底表示什么¶

这是顺序栈最关键、也最容易乱的点。

教材里常见两种定义方式：

top 指向当前栈顶元素
top 指向栈顶元素的下一个位置

这两种都能写对，但：

判空条件不同
判满条件不同
入栈和出栈时指针变化顺序也不同

当前这套代码首稿采用的是最常见的一种：

空栈时 top = -1
top 指向当前栈顶元素

于是：

入栈：先 ++top，再写值
出栈：先取值，再 top--
栈空：top == -1
栈满：top == MAX_SIZE - 1

7.3 原书伪代码 vs 真实代码¶

原书思想版伪代码：

InitStack(S):
    S.top = -1

Push(S, x):
    if 栈满:
        return false
    S.top = S.top + 1
    S.data[S.top] = x

Pop(S, x):
    if 栈空:
        return false
    x = S.data[S.top]
    S.top = S.top - 1

真实 C 代码见：

第3章普通代码版

当前已经落地的核心函数包括：

InitSeqStack
SeqStackEmpty
SeqStackFull
PushSeqStack
PopSeqStack
GetTopSeqStack

真实代码片段如下：

/* 顺序栈：top 指向当前栈顶元素。空栈时 top 为 -1。 */
typedef struct {
    ElemType data[MAX_SIZE];
    int top;
} SeqStack;

/* 入栈：先移动 top，再写入数据。 */
bool PushSeqStack(SeqStack *stack, ElemType value) {
    if (stack == NULL || SeqStackFull(stack)) {
        return false;
    }
    stack->data[++stack->top] = value;
    return true;
}

/* 出栈：先取栈顶元素，再让 top 回退。 */
bool PopSeqStack(SeqStack *stack, ElemType *value_out) {
    if (SeqStackEmpty(stack) || value_out == NULL) {
        return false;
    }
    *value_out = stack->data[stack->top--];
    return true;
}

7.4 为什么顺序栈好写¶

因为栈只在顶端操作，所以顺序栈不需要像顺序表那样频繁搬移中间元素。

这意味着：

入栈通常是 O(1)
出栈通常也是 O(1)

你可以把它理解成：

顺序表在中间插入像“队伍里插队”，很多人要挪位置
顺序栈在顶端插入像“最上面再放一本书”，几乎不影响下面的元素

7.5 共享栈¶

原书在栈的顺序存储里专门讲了一个很典型的结构：

共享栈

它的核心思想是：

两个栈共用一个数组
一个栈从左往右长
一个栈从右往左长
只有两个栈顶相邻时才算真的满了

这样做的优点是：

比给两个栈分别固定空间更节省
谁用得多，谁就多占一点空间

当前代码首稿里已经把共享栈也落成了真实代码，对应函数包括：

InitSharedStack
PushSharedStack0
PushSharedStack1
PopSharedStack0
PopSharedStack1

8. 3.1.3 栈的链式存储¶

8.1 为什么还需要链栈¶

顺序栈已经很好用了，那为什么还要学链栈？

因为顺序栈有一个天然缺点：

容量上限通常要提前估计

如果预估太小，就可能上溢。

链栈的思路则是：

需要一个结点，就申请一个结点

因此它更灵活。

8.2 链栈的本质¶

链栈本质上就是：

用单链表实现栈

并且通常把：

链表表头

作为：

栈顶

因为这样入栈和出栈都只要改表头，效率最高。

8.3 原书伪代码 vs 真实代码¶

原书思想版伪代码：

Push(x):
    新建结点 p
    p->data = x
    p->next = top
    top = p

Pop(x):
    if 栈空:
        return false
    p = top
    x = p->data
    top = p->next
    释放 p

真实代码见：

第3章普通代码版

当前已经落地的核心函数包括：

InitLinkStack
LinkStackEmpty
PushLinkStack
PopLinkStack
GetTopLinkStack
DestroyLinkStack

真实代码片段如下：

/* 链栈入栈：新结点插到表头。 */
bool PushLinkStack(LinkStack *stack, ElemType value) {
    LinkNode *node;

    if (stack == NULL) {
        return false;
    }

    node = (LinkNode *)malloc(sizeof(LinkNode));
    if (node == NULL) {
        return false;
    }
    node->data = value;
    node->next = stack->top;
    stack->top = node;
    return true;
}

9. 栈的典型应用：括号匹配¶

这是栈最经典、最适合入门的一道应用题。

为什么括号匹配适合用栈？

因为：

最后出现的左括号
必须最先和后面的右括号匹配

这恰好就是：

后进先出

当前真实代码里已经补了：

IsBracketSequenceBalanced

它用顺序栈来判断一个括号串是否匹配。

这类题的思路非常值得记住：

左括号入栈
遇到右括号时弹出一个左括号
如果类型对不上，说明不匹配
最后栈空才说明完全匹配

10. 3.2 队列¶

10.1 队列的基本概念¶

如果说栈是：

只允许在一端插入和删除

那么队列就是：

只允许在一端插入
在另一端删除

这意味着它和栈一样，都是“操作受限的线性表”，但限制方式不同。

更形象一点理解：

栈像一摞盘子，只能从最上面放、从最上面拿
队列像排队打饭，后面的人只能排到队尾，前面的人只能从队头离开

所以队列最核心的直觉不是“线性表”，而是：

先来先走

10.2 队头、队尾与操作特性¶

队列里也有几个必须分清的术语：

队头（front）
允许删除的一端
队尾（rear）
允许插入的一端
空队列
没有任何元素

队列最核心的行为特征是：

先进先出
英文是 FIFO
即 First In First Out

为什么？

因为先进入队列的元素更靠近队头，所以它会先被删除。

10.3 为什么顺序队列会出现“假溢出”¶

很多同学第一次学顺序队列，会觉得：

“不就是数组加两个指针吗？”

但它比顺序栈多一个经典坑：

假溢出

比如一个数组从左到右使用，rear 一直往后走。
即使前面已经出队腾出了位置，只要 rear 到了数组末尾：

你仍然不能继续简单入队

这就叫：

不是数组真的满了
但普通顺序队列写法已经没法再插入

所以教材后面一定会引出：

循环队列

10.4 循环队列的核心思想¶

循环队列的本质只有一句话：

把数组头尾“逻辑上接起来”

这样当 rear 走到最后一格后：

它可以回到数组开头继续使用那些已经空出来的位置

这就是为什么循环队列比普通顺序队列更常用。

当前代码里采用的约定是：

front 指向队头元素
rear 指向下一个可插入位置
预留一个空位置区分队空和队满

于是：

队空：front == rear
队满：(rear + 1) % MAX_SIZE == front

10.5 原书伪代码 vs 真实代码：循环队列¶

原书思想版伪代码：

InitQueue(Q):
    Q.front = 0
    Q.rear = 0

EnQueue(Q, x):
    if 队满:
        return false
    Q.data[Q.rear] = x
    Q.rear = (Q.rear + 1) % MaxSize

DeQueue(Q, x):
    if 队空:
        return false
    x = Q.data[Q.front]
    Q.front = (Q.front + 1) % MaxSize

真实 C 代码见：

第3章普通代码版

当前已经落地的核心函数包括：

InitCircularQueue
CircularQueueEmpty
CircularQueueFull
EnqueueCircularQueue
DequeueCircularQueue
GetHeadCircularQueue
PrintCircularQueue

真实代码片段如下：

/* 循环队列：front 指向队头元素，rear 指向下一个可插入位置。 */
typedef struct {
    ElemType data[MAX_SIZE];
    int front;
    int rear;
} CircularQueue;

/* 入队：把新元素放到 rear 位置，再让 rear 循环后移。 */
bool EnqueueCircularQueue(CircularQueue *queue, ElemType value) {
    if (queue == NULL || CircularQueueFull(queue)) {
        return false;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX_SIZE;
    return true;
}

这段代码最应该看懂的点是：

为什么 rear 写完数据后要取模
为什么队满不是 rear == front
为什么要故意浪费一个存储单元

答案其实都在服务同一个目标：

让队空和队满的判断足够清楚，不打架

10.6 链队列¶

队列除了顺序存储，还能用链式存储。

链队列最常见的写法是同时维护两个指针：

front
rear

它们分别负责：

从队头删除
在队尾插入

当前代码里使用的是：

带头结点 的链队列

这样做的好处是：

队空和非空时，很多边界操作更统一

10.7 原书伪代码 vs 真实代码：链队列¶

原书思想版伪代码：

InitQueue(Q):
    建立头结点
    Q.front = Q.rear = 头结点

EnQueue(Q, x):
    新建结点 p
    p->data = x
    p->next = NULL
    Q.rear->next = p
    Q.rear = p

DeQueue(Q, x):
    if 队空:
        return false
    p = Q.front->next
    x = p->data
    Q.front->next = p->next
    若 p 是原队尾:
        Q.rear = Q.front
    释放 p

真实代码里已经落地的函数包括：

InitLinkQueue
LinkQueueEmpty
EnqueueLinkQueue
DequeueLinkQueue
GetHeadLinkQueue
PrintLinkQueue
DestroyLinkQueue

这类代码最容易错的地方是：

队列原本只有一个元素时出队
删除后没有同步更新 rear
头结点和首元结点混淆

10.8 双端队列¶

双端队列（Deque）可以理解成：

队列的升级版

它允许：

从队头插入
从队尾插入
从队头删除
从队尾删除

这意味着它既有一点像队列，也有一点像栈。

当前代码中已经给出一个双端队列的真实版本，目的不是要求立刻背代码，而是先把“结构长什么样”建立起来。

你真正要先记住的是：

双端队列的本质，是“两个端点都能操作”

10.9 队列和栈怎么对比记¶

这是本章最适合直接背下来的一个对照表：

栈：后进先出，LIFO
队列：先进先出，FIFO
栈：同一端插入删除
队列：一端插入，另一端删除
栈：更像“回退”
队列：更像“排队”

如果这组对比你脑子里非常清楚，后面很多选择题都会简单很多。

11. 3.3 栈和队列的应用¶

11.1 为什么一定要学“应用”¶

只背定义，栈和队列其实很容易学得发虚。

因为它们和第 2 章的线性表不一样：

栈和队列本身往往不是最终目的
它们更多时候是“解决别的问题的工具”

所以真正掌握这一章，不是会写 Push、Pop、EnQueue、DeQueue 就够了，而是要知道：

什么问题天然适合用栈
什么问题天然适合用队列
为什么这个问题一旦换成别的结构就别扭了

11.2 栈在括号匹配中的应用¶

这个应用我们前面已经先落了真实代码，这里再把“为什么”讲透一点。

括号匹配的核心不是“左括号和右括号数量相等”，而是：

最近出现、但还没匹配掉的左括号
必须最先和当前右括号尝试配对

这就是一种非常典型的：

最近进入的任务，最先处理

所以它天然符合栈的 LIFO 思想。

更形象一点：

你可以把每一个还没匹配成功的左括号理解成“待完成任务”
越靠后的左括号，越急着等自己的右括号
所以最急的那个任务，一定在最上面

这就是为什么括号匹配不是队列题，而是栈题。

11.3 栈在表达式求值中的应用¶

原书这里很重视：

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

这部分很多同学一开始会觉得抽象，其实可以这样理解：

人看中缀表达式舒服
机器更喜欢后缀表达式

因为中缀表达式里：

运算优先级
括号嵌套

都需要额外判断。

而后缀表达式的好处是：

运算顺序已经被写进表达式结构里了
不再需要括号

例如：

中缀：A + B * (C - D) - E / F
后缀：ABCD-*+EF/-

你现在不用急着把变换规则全背下来，先记住最重要的一点：

后缀表达式求值特别适合用栈

因为遇到运算符时：

只需要把前面最近压进去的两个操作数弹出来
计算完后再把结果压回去

这又一次是“最近的先处理”，所以还是栈。

11.4 队列在哪些问题里特别自然¶

如果说栈对应的是：

回退
嵌套
最近优先

那么队列天然适合的是：

排队
逐层
先来先处理

典型例子包括：

缓冲区
打印任务排队
消息队列
层次遍历
广度优先搜索

这里你可以建立一个很有用的直觉：

题目如果强调“最近、回退、嵌套”，优先想栈
题目如果强调“先来后到、按层、排队等待”，优先想队列

11.5 栈和队列应用题最容易丢分的地方¶

这一类题并不总是难在代码，而常常难在：

没有认出题目本质到底是栈还是队列
会讲思路，但边界条件没处理好
模拟过程时顺序写反

所以你后面做题时，要强迫自己先问一句：

这个问题的处理顺序，到底是“最近优先”，还是“先来优先”？

这个判断对了，结构通常就选对了一大半。

12. 3.4 数组和特殊矩阵¶

12.1 为什么这一节会出现在栈和队列后面¶

很多同学第一次看到这一章后半段，会觉得有点跳：

前面还在讲栈和队列
后面怎么突然讲数组和矩阵了

其实这并不突然。

因为这一章后半段想解决的是：

当数据按多维形式组织时，内存里应该怎么放

这仍然属于：

存储结构

只是前面讲的是“受限线性表”，这里讲的是“多维顺序存储”和“压缩存储”。

12.2 数组的本质¶

原书里对数组的定义很重要，核心意思是：

数组是由若干个相同类型数据元素构成的有限序列

它和线性表的关系可以这样记：

一维数组可以看成一个线性表
二维数组可以看成“元素仍然有序，但每个元素本身又是一个定长数组”

更关键的是：

数组一旦定义，维数和维界通常就固定了

这就决定了数组最擅长的是：

按下标直接访问
连续存储
地址计算

而不擅长的是：

任意位置频繁插入删除

12.3 为什么数组能随机访问¶

这是数组和链表最大的体验差异。

数组之所以能随机访问，不是因为“它名字就叫数组”，而是因为：

所有元素在内存中连续存放
每个元素长度固定
所以任意元素地址都能通过公式直接算出来

这就是地址计算的本质：

不是一个一个找过去
而是直接算出它在哪

所以数组的优势可以浓缩成一句话：

已知下标，就能立刻定位

12.4 二维数组为什么也能线性存储¶

这是很多同学一开始会迷糊的地方：

二维数组看起来像表格
内存却是一维线性的

怎么做到的？

答案是：

按某种固定顺序“铺平”

最常见有两种方式：

行优先
列优先

行优先的意思是：

先把第一行连续存完
再存第二行
再存第三行

列优先则反过来：

先存第一列
再存第二列
再存第三列

你可以把二维数组想成一张表格，而内存像一条长卷尺。
所谓行优先或列优先，就是决定：

你沿着哪条路径把这张表格展开成一条线

12.5 为什么要学特殊矩阵压缩存储¶

如果一个矩阵里：

有大量元素相同
或者大量元素都是 0

那继续用普通二维数组完整存它，就会浪费很多空间。

这时就需要：

压缩存储

压缩存储的核心不是“换个名字存”，而是：

不再老老实实存每个位置
而是只存真正有信息量的部分

这就是数据结构里特别典型的一种思想：

利用规律，减少存储开销

12.6 对称矩阵、三角矩阵、三对角矩阵¶

原书这一节的重点其实不是让你死背一堆公式，而是先认出：

这些矩阵的“非重复信息”到底集中在哪

比如：

对称矩阵
上三角和下三角互相镜像
所以存一半就够了
下三角矩阵
上三角很多位置都是相同常量
所以只需要存有信息量的那部分，再补一个常量区
三对角矩阵
非零元素只集中在主对角线附近三条线
其他位置几乎都没必要存

所以你真正要先抓住的是：

公式是结果
规律才是原因

12.7 稀疏矩阵为什么不能只存“值”¶

稀疏矩阵里，非零元素很少。

很多人第一反应会说：

“那我只把非零值记下来不就行了？”

不行。

因为你只知道值，不知道它原来在哪一行哪一列，这个矩阵就没法恢复了。

所以稀疏矩阵真正要保存的是：

值
行号
列号

这就是三元组表的核心思想。

换句话说，稀疏矩阵压缩后丢掉的不是“意义”，而是：

那些本来就没信息量的大量零元素

12.8 这一节最该建立的直觉¶

学数组和特殊矩阵时，最重要的不是一上来背所有下标映射公式，而是先建立这几个判断习惯：

这组数据在内存里是不是连续的
我是按行展开，还是按列展开
哪些元素是重复信息
哪些元素是真正必须存的
当前题目里下标到底从 0 还是从 1 开始

其中最后一条尤其重要，因为很多计算题不是公式不会，而是：

下标起点看错了

12.9 一维数组地址计算公式¶

先从最简单的一维数组开始。

设：

数组名为 A
每个元素占 L 个存储单元
A[low] 的存储地址为 LOC(A[low])

那么 A[i] 的地址公式是：

LOC(A[i]) = LOC(A[low]) + (i - low) * L

这条公式的本质特别简单：

先看它离起始下标差了几个位置
再乘每个元素的长度
最后加到首地址上

例如：

A[0] 地址是 100
每个元素占 4 字节
求 A[5] 的地址

则：

LOC(A[5]) = 100 + (5 - 0) * 4 = 120

这一题最容易错的点不是公式，而是：

忘了数组下标可能不是从 0 开始

12.10 二维数组地址计算：行优先与列优先¶

设二维数组：

A[low1..high1][low2..high2]

其中：

每个元素占 L 个存储单元
行数为 high1 - low1 + 1
列数为 high2 - low2 + 1

行优先¶

行优先时，前面先存完了多少元素，取决于：

前面有多少整行
当前这一行前面还有多少列

公式为：

LOC(A[i][j]) = LOC(A[low1][low2]) + ((i - low1) * 列数 + (j - low2)) * L

如果列数记为 n，那么也常写成：

LOC(A[i][j]) = LOC(A[0][0]) + (i * n + j) * L

这里默认下标从 0 开始。

列优先¶

列优先时，逻辑反过来：

先看前面有多少整列
再看当前这一列前面有多少行

公式为：

LOC(A[i][j]) = LOC(A[low1][low2]) + ((j - low2) * 行数 + (i - low1)) * L

一个完整例子¶

设：

A[0..2][0..3]
每个元素占 2 个存储单元
LOC(A[0][0]) = 100

求 A[2][1] 的地址。

行优先下：

列数 = 4
LOC(A[2][1]) = 100 + (2 * 4 + 1) * 2 = 118

列优先下：

行数 = 3
LOC(A[2][1]) = 100 + (1 * 3 + 2) * 2 = 110

这就是为什么题目里“按行优先还是按列优先”一定要先看清。

12.11 对称矩阵压缩存储公式¶

对称矩阵最核心的规律是：

a[i][j] = a[j][i]

所以：

上三角和下三角只需要存一边

最常见做法是：

按行存下三角部分（含主对角线）

如果下标从 0 开始，且 i >= j，则：

k = i * (i + 1) / 2 + j

也就是说：

a[i][j] 存在一维数组 B[k] 中

如果 i < j，因为对称，可以先交换成：

a[i][j] = a[j][i]

再代公式。

例子¶

求 a[3][1] 在压缩数组中的位置。

因为 3 >= 1，直接代：

k = 3 * 4 / 2 + 1 = 7

所以它存到：

B[7]

这类题最关键的不是硬背，而是先想：

这一项属于“我真正存的那一半”吗？

12.12 下三角矩阵与上三角矩阵¶

下三角矩阵¶

下三角矩阵里：

主对角线以上通常全是同一个常量

所以一般做法是：

先存下三角和主对角线
再额外存一个常量位置

若按行优先、下标从 0 开始，且 i >= j，则仍有：

k = i * (i + 1) / 2 + j

若 i < j，说明它在上三角常量区，就映射到：

最后那个常量存储单元

上三角矩阵¶

上三角矩阵则反过来：

主对角线以下通常都是同一个常量

如果按行优先存上三角（含主对角线），i <= j 时，前面元素个数可以理解为：

前 i 行已经存了若干个
当前行再往后数到第 j 列

常见结果公式为：

k = n * i - i * (i - 1) / 2 + (j - i)

这里 n 是矩阵阶数。

如果 i > j，则映射到常量区。

这一节做题时特别推荐你：

先画一个 4 x 4 或 5 x 5 小矩阵
给压缩数组编号
自己数一遍

这样比死背更稳。

12.13 三对角矩阵压缩存储¶

三对角矩阵也叫带状矩阵，它的非零元素只集中在：

主对角线
主对角线上一条
主对角线下一条

也就是说，只有满足：

|i - j| <= 1

的位置才可能有非零值。

按行优先压缩时，一个非常常见的公式是：

k = 2 * i + j

这里默认下标从 0 开始。

更严格地说，这个公式对应的是把合法位置顺次压进一维数组后的编号关系。

例子¶

求 a[3][2] 在压缩数组中的位置。

因为：

|3 - 2| = 1

它在三条对角线范围内，所以：

k = 2 * 3 + 2 = 8

所以它对应：

B[8]

这类题的第一步永远不是代公式，而是先判断：

这个元素到底在不在三条对角线范围内

12.14 稀疏矩阵三元组表例子¶

稀疏矩阵最典型的压缩方式是：

三元组表

每个非零元素存成：

(行号, 列号, 值)

例如矩阵：

0 0 5
0 2 0
7 0 0

压缩后可以写成：

(0, 2, 5)
(1, 1, 2)
(2, 0, 7)

还要额外保存：

总行数
总列数
非零元素个数

因为如果只看这三个三元组：

你并不能确定原矩阵到底是 3 x 3
还是更大的矩阵里恰好只有这些非零元

12.15 这一部分做题的统一步骤¶

以后你碰到数组地址计算和压缩存储题，建议固定按这个顺序做：

先判断下标从 0 开始还是从 1 开始
判断是行优先还是列优先
判断当前结构有没有“规律可压缩”
先找“前面已经排了多少个元素”
再确定当前元素在这一层里的偏移量
最后再写公式

这六步看起来慢，但其实能极大减少粗心出错。

尤其要记住：

很多题不是不会，而是直接跳到公式，导致前提条件看错

12.16 3.4 自学检查¶

如果你学完 3.4，建议拿下面这几题问自己：

你能解释为什么数组支持随机访问，而链表不支持吗？
你能写出二维数组行优先地址公式吗？
你能说清列优先和行优先到底差在哪吗？
你能解释为什么对称矩阵只存一半就够了吗？
你能判断一个元素是否落在三对角矩阵的压缩范围内吗？
你能说清稀疏矩阵为什么必须保存行号和列号吗？

13. 本章下一步施工路线¶

这一稿之后，我会继续按最高标准把第 3 章往下推进：

继续补厚 3.1 栈，加题型整理、易错点和自学检查
继续补厚 3.2 队列，加题型整理与逐行拆解
给 3.3 栈和队列的应用 补更多典型题和代码落地
给 3.4 数组和特殊矩阵 补地址计算、压缩存储公式与例题讲解

14. 当前可用文件¶

OCR 底稿：本章 OCR 底稿
页面图片：本章页面图像
本章正文首稿：本书第3章正文
本章代码首稿：第3章普通代码版
本章逐行注释代码：第3章逐行注释版代码

15. 代码阅读入口¶

为了让这一章真正适合自学，现在代码阅读也分成两层：

运行版：第3章普通代码版
逐行注释版：第3章逐行注释版代码

建议阅读顺序：

先看这份讲义，把概念和题型地图建立起来
再看逐行注释版代码，逐步理解每一个动作
最后回到运行版代码，培养更接近考试和工程的阅读感觉

如果你的本地编辑器对中文编码比较挑剔，还可以使用：

第3章兼容编码版逐行注释代码

16. 题型分类索引¶

这一章的题目表面上很散，实际上可以浓缩成下面几类。

16.1 栈的基本操作与判定类¶

这类题主要考：

栈空、栈满条件
top 指针含义
入栈、出栈的顺序
共享栈空间利用

对应内容：

顺序栈
共享栈
链栈

16.2 出栈序列与合法性分析类¶

这类题是考研里特别高频的一类。

它本质上考的是：

你是否真正理解 LIFO
你能不能模拟“当前最急迫的元素是谁”

做这类题时，最有效的方法通常不是死猜，而是：

画栈
按步骤模拟

16.3 队列判空判满与循环队列类¶

这类题最常考：

假溢出
循环队列判空判满
front 和 rear 的定义差异

真正难点往往不在入队出队本身，而在：

题目采用的是哪一种指针约定

16.4 栈和队列应用类¶

这类题是本章最有“算法味”的部分。

典型内容：

括号匹配
表达式求值
后缀表达式
缓冲区与排队模型
层次遍历、广度优先

16.5 数组地址计算与压缩存储类¶

这类题主要考：

行优先
列优先
对称矩阵压缩
三角矩阵压缩
三对角矩阵压缩
稀疏矩阵三元组表

这类题最容易让人误以为是“公式题”，其实本质上是在考：

你能不能数清楚前面已经排了多少个元素

17. 易错点总表¶

这一章最常见的丢分点，我给你集中拎出来。

17.1 栈的易错点¶

top 的初值搞混
“先加再存”还是“先存再加”写反
Pop 和 GetTop 混淆
共享栈判满条件写错

17.2 队列的易错点¶

以为普通顺序队列不会假溢出
把循环队列的队空和队满条件写成一样
链队列只剩一个元素时出队，没有同步更新 rear
双端队列下标回绕时忘了取模

17.3 数组和矩阵的易错点¶

行优先和列优先看反
下标从 0 开始还是从 1 开始看错
公式里用错“行数”或“列数”
压缩存储时没有先判断该元素是不是落在有效区域
稀疏矩阵只记值，不记行列

18. 刷题路径¶

建议按下面的顺序训练本章内容。

18.1 基础训练：先练基本动作¶

目标：

把栈和队列最基础的入、出、读头动作写顺

建议顺序：

顺序栈
链栈
循环队列
链队列
双端队列

18.2 进阶训练：专攻判定与模拟¶

目标：

不再靠“感觉”判断，而是能稳定模拟过程

建议顺序：

出栈序列合法性
栈顶变化过程
循环队列判空判满
双端队列限制条件

18.3 强化训练：应用题¶

目标：

看到题目就能迅速判断“这题为什么是栈/为什么是队列”

建议顺序：

括号匹配
后缀表达式求值
中缀转后缀
队列在缓冲区中的应用

18.4 第四轮：公式与压缩存储¶

目标：

不再死背公式，而是能自己推到正确映射关系

建议顺序：

一维数组地址
二维数组行优先
二维数组列优先
对称矩阵
三角矩阵
三对角矩阵
稀疏矩阵三元组表

19. 逐行拆解示范¶

下面把第 3 章最关键的几个代码动作，再用“逐行思维”的方式过一遍。

19.1 循环队列入队：为什么先写入再移动 rear¶

核心代码：

bool EnqueueCircularQueue(CircularQueue *queue, ElemType value) {
    if (queue == NULL || CircularQueueFull(queue)) {
        return false;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX_SIZE;
    return true;
}

逐行理解：

先判断队列是否存在、是否已满
把新值写到 rear 当前指向的位置
再把 rear 往后移动一格
由于是循环队列，所以移动后要取模

为什么不是先移动 rear 再写？

因为在当前这套定义里：

rear 指向的是“下一个可插入位置”

所以这一格本来就是拿来写新元素的。

19.2 链队列出队：为什么删掉最后一个元素时要改 rear¶

核心代码：

bool DequeueLinkQueue(LinkQueue *queue, ElemType *value_out) {
    QueueNode *node;

    if (LinkQueueEmpty(queue) || value_out == NULL) {
        return false;
    }

    node = queue->front->next;
    *value_out = node->data;
    queue->front->next = node->next;
    if (queue->rear == node) {
        queue->rear = queue->front;
    }
    free(node);
    return true;
}

逐行理解：

先判断是否为空
node 指向真正要出队的第一个实际结点
先保存这个结点的数据
再让头结点跳过它
如果这个结点恰好也是队尾，说明原队列只有一个元素
此时必须把 rear 拉回头结点
最后再释放结点

这题的核心就是：

删除最后一个实际结点后，队列状态必须回到“空队列”的一致表示

19.3 后缀表达式求值：为什么弹出时先右后左¶

核心代码会做这样一组动作：

Pop(..., &right);
Pop(..., &left);
ApplyBinaryOperator(left, right, op, &value);

这一顺序不能反。

因为后缀表达式里如果看到运算符，例如 5 2 -：

先弹出来的是 2
它应该是右操作数
后弹出来的是 5
它才是左操作数

所以你会发现：

栈里“先弹出来”的元素
在表达式里不一定是“先算的左边那个”

这也是表达式求值题特别容易出错的地方。

20. 本章自学检查清单¶

学完第 3 章后，你可以直接拿这份清单自测。

20.1 概念层¶

你能说清 LIFO 和 FIFO 的区别吗？
你能说清栈和队列各自限制了哪一端吗？
你能解释为什么循环队列能解决假溢出吗？
你能解释为什么数组支持随机访问吗？

20.2 代码层¶

你能自己写出顺序栈基本操作吗？
你能自己写出循环队列的入队和出队吗？
你能自己写出链队列出队时对 rear 的更新吗？
你能自己写出括号匹配的栈式做法吗？

20.3 做题层¶

你能判断一题更适合用栈还是队列吗？
你能写出二维数组按行优先的地址公式吗？
你能判断三对角矩阵某元素是否落在压缩范围内吗？
你能说清稀疏矩阵为什么不能只保存非零值吗？

22. 原书试题区整理版¶

22.1 这一版整理的作用¶

这一部分不是把原书题目原样搬过来，而是把第 3 章原书试题按“考法”重新归类。

这样整理的价值主要有两点：

学生做题前，能先判断题目属于哪一类，不会把整章题目看成一团
后面继续补逐题详细解答时，可以直接沿着这个分类继续展开

当前这一版主要先做三件事：

把原书第 3 章试题按知识块重新归组
给出每类题在考什么
给出对应的做题思路和易错点

22.2 栈的基本概念与操作题¶

这一类题通常围绕：

栈的定义
LIFO
栈顶、栈底、空栈
顺序栈判空 / 判满
共享栈

这类题最核心的考点是：

栈只在一端操作
“后进先出”到底意味着什么
top 究竟表示的是“栈顶元素位置”还是“下一个可插入位置”

做题思路：

先判断题目是在考概念还是考具体顺序栈定义
再看 top 的语义是怎么约定的
最后再代入判空 / 判满公式

易错点：

不同教材里 top 定义不同，生搬硬套
把“只能在一端操作”和“只能存一类数据”混淆

22.3 出栈序列与合法性分析题¶

这一类题通常围绕：

给定入栈序列
判断某个出栈序列是否合法
模拟多个元素的压栈与弹栈过程

这类题本质上是在考：

你是否真正理解 LIFO
你会不会顺着过程手推，而不是靠感觉猜

做题思路：

老老实实模拟栈变化
每看一个目标出栈元素，就判断是否需要继续入栈
若栈顶刚好是目标元素，再出栈

易错点：

想直接猜结果，不做过程模拟
忽略“中间必须先入栈才能后出”的约束

22.4 队列与循环队列题¶

这一类题通常围绕：

队列的定义
FIFO
假溢出
循环队列判空 / 判满
入队、出队后 front、rear 如何变化

这类题最核心的考点是：

队列只允许一端入、另一端出
循环队列里下标移动是“取模意义上的循环”

做题思路：

先确认 front 和 rear 在当前定义里分别表示什么
再看判空 / 判满是基于哪条公式
最后模拟每次入队 / 出队后的变化

易错点：

把普通顺序队列和循环队列公式混掉
误以为“数组还有空位”就一定还能入队

22.5 栈和队列应用题¶

这一类题通常围绕：

括号匹配
表达式求值
后缀表达式
哪类问题更适合用栈
哪类问题更适合用队列

这类题最核心的是：

栈适合处理“最近的尚未匹配信息”
队列适合处理“先来先服务”的过程

做题思路：

先判断问题需要“回头看最近元素”还是“按到达顺序处理”
再决定该用栈还是队列
表达式题里尤其要注意操作数弹出顺序

易错点：

表达式求值时左右操作数顺序写反
看到“排队”就机械想到队列，看到“括号”就机械想到栈，但解释不清原因

22.6 数组地址计算与压缩存储题¶

这一类题通常围绕：

一维数组地址计算
二维数组按行优先 / 列优先地址计算
对称矩阵压缩
三角矩阵压缩
三对角矩阵压缩
稀疏矩阵三元组表

这类题最常考的不是定义，而是：

地址公式怎么写
元素是否落在压缩范围内
压缩后一维下标怎么映射

做题思路：

先判断存储方式
再判断元素是否在压缩保留区域
最后套对应公式

易错点：

行优先、列优先公式混掉
没先判断元素是否在压缩区域里
只记公式，不理解为什么这么映射

22.7 这一版整理后的使用方法¶

现在最推荐这样用这部分：

做题前先判断题目属于栈、队列、应用题还是数组压缩题
再看这一类题最常见的主线和易错点
做不出来时，再回看后面的逐题详细解答版和对应代码

23. 原书试题逐题详细解答版（基础部分）¶

23.1 高频题 1：为什么循环队列能解决假溢出¶

题目本质：

这类题不是只问“循环队列更高级”，而是在问：

顺序队列里原本浪费掉的空间，为什么在循环定义下又能继续用。

正确结论：

循环队列通过让 front 和 rear 在数组中循环移动，解决了普通顺序队列的假溢出问题

详细思路：

普通顺序队列中，队头元素出队后，前面的空位置通常不会自动复用
如果 rear 一路走到数组尾部，即使前面空出来很多位置，也可能无法继续入队
循环队列把整个数组首尾接起来看
这样 rear 到尾部后可以回到开头继续利用空位

易错点：

只记“循环队列能解决假溢出”，却说不清它到底复用了谁
误以为循环队列不需要判满条件

23.2 高频题 2：为什么出栈序列题一定要模拟¶

题目本质：

这类题在考的是你能不能真正按照 LIFO 去推，而不是靠直觉猜一个像样的序列。

正确结论：

出栈序列是否合法，最稳的判断方式就是老老实实模拟压栈和出栈过程

详细思路：

给定入栈序列后，元素只能按这个顺序进入栈
任何一个想弹出的元素，如果当前还没压进栈，就必须继续压栈
如果已经在栈里，但不在栈顶，也不能先弹它
只有当目标元素恰好位于栈顶时，才能合法弹出

易错点：

想直接靠感觉判断“好像能出”
忽略了中间元素必须先压栈才能影响出栈次序

23.3 高频题 3：共享栈为什么能更节省空间¶

题目本质：

这类题在考的是你是否理解“两个使用高峰不一定同时出现”这个思路。

正确结论：

共享栈让两个栈共用同一段连续空间，在很多场景下能提高空间利用率

详细思路：

两个独立顺序栈如果各自预留固定空间，可能会出现一边很空、一边不够用
共享栈让一个栈从左向右长，另一个栈从右向左长
只要中间还没碰上，就说明总空间还能继续利用
所以它本质上是减少“静态分割带来的浪费”

易错点：

误以为共享栈能让栈无限扩容
不会判断共享栈满的条件

23.4 高频题 4：后缀表达式求值为什么弹出时先右后左¶

题目本质：

这类题在考的是你是否真正理解“栈顶出来的顺序”和“运算符左右操作数顺序”不是一回事。

正确结论：

在后缀表达式求值中，遇到二元运算符时，先弹出的元素是右操作数，后弹出的元素才是左操作数

详细思路：

例如后缀表达式 5 2 -
扫描到 - 时，栈顶首先弹出的是 2
它在原表达式中应当是右操作数
再弹出的是 5
它才是左操作数
所以应用运算时要写成 left op right

易错点：

弹出两个数后直接按“先弹出的当左边”处理
对减法、除法这种不满足交换律的运算尤其容易错

23.5 高频题 5：为什么数组支持随机访问¶

题目本质：

这类题在考的是“随机访问”到底建立在哪个前提上。

正确结论：

数组支持随机访问，是因为元素地址可以通过首地址和下标直接计算

详细思路：

数组元素通常连续存储
一旦知道首地址、元素大小和下标
某个元素的位置就能直接算出来
所以不需要像链表那样从头往后找

易错点：

把“数组能随机访问”说成“因为数组是线性的”
没有把连续存储和地址计算联系起来

23.6 高频题 6：为什么二维数组也能线性存储¶

题目本质：

这类题在考的是你是否把“逻辑上是二维”和“存储上是线性”区分开了。

正确结论：

二维数组在内存中仍然是按某种固定次序线性存放的，常见有行优先和列优先

详细思路：

内存本质上还是一维线性空间
所谓二维数组，只是我们在逻辑上把元素看成行列结构
实际存储时，会按行优先或列优先的规则，把二维下标映射到一维地址

易错点：

以为二维数组在内存里真有“二维格子”
地址计算时没先分清行优先还是列优先

23.7 高频题 7：对称矩阵为什么只存一半¶

题目本质：

这类题在考的是你是否利用了矩阵结构里的冗余信息。

正确结论：

对称矩阵只需要存主对角线及其一侧，因为另一侧完全可以由对称关系推出

详细思路：

对称矩阵满足 a[i][j] = a[j][i]
所以主对角线两边的信息并不独立
如果上三角已经存了，下三角就可以通过对称关系还原
这样就能节省空间

易错点：

只记“存一半”，却说不清为什么另一半可由谁推出
压缩映射前没先判断元素在哪个半区

23.8 高频题 8：稀疏矩阵为什么不能只存非零值¶

题目本质：

这类题在考的是你是否理解“值”和“位置”在稀疏矩阵里同样重要。

正确结论：

稀疏矩阵不能只存非零值，还必须存这些非零值所在的行列位置

详细思路：

稀疏矩阵中，非零元素很少
只存值虽然能节省空间
但如果不知道它属于哪一行、哪一列，就无法还原原矩阵结构
所以三元组表要同时记录：
行号
列号
值

易错点：

只盯“省空间”，忽略“还原结构”
误以为值本身就足以表示矩阵

23.9 基础题解学习提示¶

这一部分先覆盖的是第 3 章最核心、最常见、最能建立题感的一批题：

循环队列和假溢出
出栈序列合法性
共享栈空间利用
后缀表达式求值
数组随机访问
二维数组线性存储
对称矩阵压缩
稀疏矩阵三元组表

这意味着第 3 章现在已经不只是有“代码层”和“题型层”，而是开始有“原书题解层”了。

站内代码入口¶

对应代码专题：第3章栈、队列和数组代码
如果你想逐行对照实现，建议把正文页和代码专题页一起打开。

继续阅读¶

← 上一章：第2章线性表下一章：第4章串 →

第3章 栈、队列和数组（自学版）¶

1. 本章定位¶

2. 资料准备情况¶

3. 学习目标¶

4. 本章结构总览¶

5. 章前提醒¶

6. 3.1 栈¶

6.1 栈的基本概念¶

6.2 栈顶、栈底、空栈¶

6.3 栈的操作特性：后进先出¶

6.4 栈的基本操作¶

6.5 栈为什么这么重要¶

7. 3.1.2 栈的顺序存储¶

7.1 顺序栈的核心思想¶

7.2 top 到底表示什么¶

7.3 原书伪代码 vs 真实代码¶

7.4 为什么顺序栈好写¶

7.5 共享栈¶

8. 3.1.3 栈的链式存储¶

8.1 为什么还需要链栈¶

8.2 链栈的本质¶

8.3 原书伪代码 vs 真实代码¶

9. 栈的典型应用：括号匹配¶

10. 3.2 队列¶

10.1 队列的基本概念¶

10.2 队头、队尾与操作特性¶

10.3 为什么顺序队列会出现“假溢出”¶

10.4 循环队列的核心思想¶

10.5 原书伪代码 vs 真实代码：循环队列¶

10.6 链队列¶

10.7 原书伪代码 vs 真实代码：链队列¶

10.8 双端队列¶

10.9 队列和栈怎么对比记¶

11. 3.3 栈和队列的应用¶

11.1 为什么一定要学“应用”¶

11.2 栈在括号匹配中的应用¶

11.3 栈在表达式求值中的应用¶

11.4 队列在哪些问题里特别自然¶

11.5 栈和队列应用题最容易丢分的地方¶

12. 3.4 数组和特殊矩阵¶

12.1 为什么这一节会出现在栈和队列后面¶

12.2 数组的本质¶

12.3 为什么数组能随机访问¶

12.4 二维数组为什么也能线性存储¶

12.5 为什么要学特殊矩阵压缩存储¶

12.6 对称矩阵、三角矩阵、三对角矩阵¶

12.7 稀疏矩阵为什么不能只存“值”¶

12.8 这一节最该建立的直觉¶

12.9 一维数组地址计算公式¶

12.10 二维数组地址计算：行优先与列优先¶

行优先¶

列优先¶

一个完整例子¶

12.11 对称矩阵压缩存储公式¶

例子¶

12.12 下三角矩阵与上三角矩阵¶

下三角矩阵¶

上三角矩阵¶

12.13 三对角矩阵压缩存储¶

例子¶

12.14 稀疏矩阵三元组表例子¶

12.15 这一部分做题的统一步骤¶

12.16 3.4 自学检查¶

13. 本章下一步施工路线¶

14. 当前可用文件¶

15. 代码阅读入口¶

16. 题型分类索引¶

16.1 栈的基本操作与判定类¶

16.2 出栈序列与合法性分析类¶

16.3 队列判空判满与循环队列类¶

16.4 栈和队列应用类¶

16.5 数组地址计算与压缩存储类¶

17. 易错点总表¶

17.1 栈的易错点¶

17.2 队列的易错点¶

17.3 数组和矩阵的易错点¶

18. 刷题路径¶

18.1 基础训练：先练基本动作¶

18.2 进阶训练：专攻判定与模拟¶

18.3 强化训练：应用题¶

第3章栈、队列和数组（自学版）¶