数据结构第 3 章：栈、队列和数组

408 数据结构「栈、队列和数组」复习：核心知识点、真题题型、通用解法与易错点。

已参考本站中这一章对应的 408 真题和408 模拟选择题。站内真题把本章分成四部分：栈、队列、栈与队列的应用、数组与压缩存储；模拟题又补充了共享栈、链栈、链队、表达式求值栈深、特殊矩阵地址计算等变式。(Any Docs)

从站内真题分布看，本章不是那种“记几个定义就行”的章节。真正反复考的是：

模块	重要程度	最核心题型
栈	★★★★★	合法出栈序列、操作模拟、最小栈容量
循环队列	★★★★★	front/rear、队空队满、队列长度
栈/队列综合	★★★★★	栈+队列组合、双端队列
表达式	★★★★★	中缀转后缀、运算符栈、后缀求值
数组地址	★★★★☆	行优先/列优先地址计算
特殊矩阵	★★★★★	对称矩阵、三对角矩阵压缩
稀疏矩阵	★★★☆☆	三元组、十字链表
链栈/链队	★★★☆☆	指针操作、复杂度
递归与栈	★★★☆☆	调用栈
共享栈	★★★☆☆	双栈判满

内容按照“掌握一类方法，迁移同类题目”的思路组织。

一、栈：本章第一大核心

1. 栈到底是什么

栈是只能在同一端进行插入和删除的线性表。

这一端叫做栈顶。

最根本特征：

后进先出 LIFO

例如依次入栈

a → b → c

如果全部入完以后再出栈：

c → b → a

但一定注意：

入栈序列确定，并不意味着出栈序列确定。

因为 Push 和 Pop 可以任意交替。

这正是整个“合法出栈序列”题型的根本。

站内 2017 真题就直接考过：确定入栈顺序并不能唯一确定出栈顺序；栈也不是“两端均可操作”的结构。(Any Docs)

二、题型一：给定出栈序列，判断是否合法

这是栈最重要的题。

站内真题中 2009、2010、2011、2013、2020、2022 都围绕出入栈过程命题。(Any Docs)

2.1 最稳的方法：真实模拟

假设入栈序列为

1,2,3,4,5

希望判断出栈序列

2,3,5,4,1

是否合法。

规则只有一句话：

想输出目标元素，如果它还没入栈，就一直 Push；如果它已经入栈，那么它必须正好位于栈顶。

过程：

目标2：
Push 1
Push 2
Pop 2

栈：[1]

目标3：
Push 3
Pop 3

栈：[1]

目标5：
Push 4
Push 5
Pop 5

栈：[1,4]

目标4：
Pop 4

目标1：
Pop 1

所以合法。

2.2 一个非常好用的判死规则

假设某时刻栈是：

栈底 → [1,2,5] ← 栈顶

下一目标却是 1。

那么不可能直接得到 1。

因为必须先：

5出栈
2出栈

才能看到 1。

因此：

一个已经进入栈、但被其他元素压住的元素，不可能越过上面的元素先出栈。

这是所有栈序列题的本质。

三、典型真题：2009 最小栈容量

题目

站内 2009 真题：元素

a,b,c,d,e,f,g

依次进入栈，元素出栈以后立即进入队列，最终队列出队次序要求为

b,d,c,f,e,a,g

问栈至少需要多大容量。站内答案为 3。(Any Docs)

解法

因为：

栈出栈 \to 队列入队

而队列 FIFO，所以最终队列输出顺序实际上就是：

栈的出栈顺序

于是要求栈产生：

b,d,c,f,e,a,g

模拟。

输出 b

Push a
Push b
Pop b

栈：

[a]

此时最大深度 2。

输出 d

Push c
Push d

此时：

[a,c,d]

最大深度变成：

3

然后：

Pop d
Pop c

输出 f

Push e
Push f

栈：

[a,e,f]

仍然最大 3。

然后：

f,e,a

全部弹出。

最后 g 入栈再出栈。

所以：

3

这类题的通法

题目问：

“最少栈容量是多少？”

不要找公式。

模拟过程中记录栈深最大值即可。

设每一步栈元素数为：

s_{1}, s_{2}, \dots, s_{m}

那么：

C_{m i n} = max s_{i}

四、题型二：带额外操作限制的出栈序列

2010 真题

题目大意：

a,b,c,d,e,f

依次进栈，Push、Pop 可以交替，但是不允许连续进行三次 Pop。

问哪个出栈序列不可能。

站内不可能的序列是：

a,f,e,d,c,b

(Any Docs)

为什么？

要求第一个输出：

所以：

Push a
Pop a

接下来第二个必须输出：

因此必须把：

b,c,d,e,f

全部压进去。

现在栈：

[b,c,d,e,f]
          ↑

接下来只能：

f
e
d
c
b

连续 Pop 五次。

但是题目规定：

不允许连续三次 Pop。

因此必然非法。

本题方法

这种题本质上是在普通栈模拟的基础上加一个状态变量：

连续Pop次数

只需要每执行：

Push → 计数清零
Pop  → 计数 + 1

判断是否违反题目约束即可。

以后可能改成：

不允许连续两次 Push；
最多连续 k 次 Pop；
每两次 Pop 之间必须有 Push；
栈容量限制为 k。

统一都用状态模拟。

五、题型三：固定某一个出栈位置，求其他位置可能值

这是稍难的一类。

5.1 2013 真题

入栈序列：

1,2,3,...,n

出栈序列：

p1,p2,p3,...,pn

已知：

p_{2} = 3

求：

p_{3}

可能有多少个不同值。

站内答案：

n - 1

(Any Docs)

先问：第三个为什么不能是 3？

因为：

p_{2} = 3

意味着 3 已经第二个出栈了。

所以：

p_{3} \neq = 3

接下来证明其他值都可以。

情况 1：让第三个输出 1

可以：

Push 1
Push 2
Pop 2

Push 3
Pop 3
Pop 1

前三个：

2,3,1

所以：

p_{3} = 1

可以。

情况 2：让第三个输出 2

Push 1
Pop 1

Push 2
Push 3
Pop 3
Pop 2

于是：

1,3,2

所以 2 也可以。

情况 3：让第三个输出任意较大的 k

例如希望：

p_{3} = 7

先：

Push 1
Pop 1

Push 2
Push 3
Pop 3

现在继续：

Push 4
Push 5
Push 6
Push 7
Pop 7

即可。

所以：

p_{3} \in {1, 2, 4, 5, \dots, n}

元素数为：

n - 1

六、模拟题升级：若 $p_{2} = k$

网站模拟题进一步把真题推广成：

p_{2} = k, k > 3

问 $p_{3}$ 有多少可能取值。

站内结论：

n - k + 2

(Any Docs)

这题很值得学，因为它展示了从真题推广一般模型的方法。

可能值为：

k - 2, k - 1, k + 1, k + 2, \dots, n

因此共有：

2 + (n - k)

即：

n - k + 2

这种题真正要做的是：

不要暴力枚举整个出栈序列，而要研究指定位置出现时“栈里还剩什么”。

七、题型四：固定开头元素，求合法序列数量

2011 真题

题目：

a,b,c,d,e

依次进入栈。

问合法出栈序列中，以 d 开头的有多少种。

站内答案：

4

(Any Docs)

要让 d 第一个出来：

Push a
Push b
Push c
Push d
Pop d

现在：

[a,b,c]

而 e 还没有入栈。

接下来 e 可以在以下不同时间插入：

c,b,a 全弹出以后

或者：

弹c,b以后

或者：

弹c以后

或者：

马上Push e

于是四种：

d,c,b,a,e
d,c,b,e,a
d,c,e,b,a
d,e,c,b,a

所以：

4

八、关于合法出栈序列的一个进阶结论

如果有 $n$ 个互异元素按固定顺序进栈，所有可能的合法出栈序列个数是 Catalan 数：

C_{n} = \frac{1}{n + 1} (n 2 n)

例如：

C_{1} = 1

C_{2} = 2

C_{3} = 5

C_{4} = 14

408 不一定直接要求计算大 Catalan 数，但这个结论非常适合处理“共有多少种合法栈序列”类问题。

九、2020 真题：直接模拟 Push / Pop

题目给操作：

Push
Push
Pop
Push
Pop
Push
Push
Pop

入栈元素依次：

a,b,c,d,e

问实际输出什么。

站内答案：

b,c,e

(Any Docs)

这种题完全不要脑算。

画表：

操作	栈	输出
Push a	a
Push b	a,b
Pop	a	b
Push c	a,c
Pop	a	c
Push d	a,d
Push e	a,d,e
Pop	a,d	e

因此：

b, c, e

十、2022 真题：栈序列的基本性质

站内 2022 真题考的是：给定入栈排列 in 和候选出栈排列 out，哪些说法正确。

正确思想包括：

可以通过模拟判断是否合法；
出栈序列可以和入栈序列相同；
也可以与入栈序列完全逆序。

因此：

入栈后立即出栈

得到原序列；

而：

全部入栈后统一出栈

得到逆序列。(Any Docs)

十一、栈的顺序存储

最普通的顺序栈：

ElemType data[MAXSIZE];
int top;

如果规定：

top 指向当前栈顶元素

常见初始化：

top = -1

队空：

t o p = - 1

栈满：

t o p = M A X S I Z E - 1

Push：

data[++top] = x;

Pop：

x = data[top--];

十二、最容易出陷阱的地方：top 的定义

有些题会规定：

top 指向栈顶元素。

另一些题规定：

top 指向栈顶元素之后的下一个空位置。

这两个公式完全不同。

因此考场一定先在草稿纸写：

top到底指什么？

再写操作。

这和后面的循环队列是完全一样的思想。

十三、共享栈

网站模拟题专门补充了共享栈。(Any Docs)

数组：

0                              n-1
↓                               ↓
栈1 → → → 空闲 ← ← ← 栈2

两个栈从两端往中间生长。

最大优点：

两个栈动态共享空闲空间。

如果一个栈很大、另一个很小，不会像“数组一人一半”那样浪费大量空间。

判满思想

重点不是死记：

top1-top2==1

而是：

两边的“下一可用位置”相遇以后，就没有空位了。

网站模拟题的特定定义下：

t o p_{1} = t o p_{2} + 1

即：

t o p_{1} - t o p_{2} = 1

但如果题目换了 top 定义，公式可能变化。

十四、链栈

链栈其实就是：

在单链表表头完成 Push 和 Pop。

因为链表头部插入、删除都是：

O (1)

若：

Node *top;

出栈：

p = top;
x = top->data;
top = top->next;
delete p;

网站模拟题也直接考过：

x = top->data
top = top->link

这一基本指针次序。(Any Docs)

十五、队列：第二大核心

队列的根本特征：

先进先出 FIFO

普通队列：

队头                       队尾
↓                           ↓
出队 ← a ← b ← c ← d ← 入队

即：

队尾入队；
队头出队。

十六、为什么需要循环队列

假设数组：

A[0...7]

不断出队以后，前面的单元虽然空出来了，但如果 rear 已经走到数组末尾，普通顺序队列就会出现：

前面有空间，后面没空间。

称为假溢出。

解决办法：

rear 到末尾后重新绕回 A[0]

因此产生：

循环队列

十七、循环队列最重要的统一思想

以后看到循环队列，先问两个问题：

问题一

front 指哪里？

可能是：

队头元素；
队头元素前一个位置。

问题二

rear 指哪里？

可能是：

队尾元素；
队尾后一个空位置。

没看清这两个定义以前，所有公式都不要写。

十八、最常见模型：rear 指队尾后一空位

设数组大小为：

m

规定：

front → 队头元素
rear  → 队尾后一个位置

且为了区分空与满，牺牲一个单元。

队空

f r o n t = r e a r

队满

rear 再向前一个位置就撞到 front：

(r e a r + 1) mod m = f r o n t

元素个数

统一公式：

L = (r e a r - f r o n t + m) mod m

最大元素数

因为牺牲一个单元：

m - 1

十九、为什么长度公式要加 $m$

如果：

front = 2
rear  = 6

显然：

L = 6 - 2 = 4

但若循环后：

front = 6
rear  = 2

真实长度：

6 → 7 → 0 → 1

共 4。

直接算：

2 - 6 = - 4

不行。

加一个数组长度，例如：

m = 8

则：

(2 - 6 + 8) mod 8 = 4

所以：

(r e a r - f r o n t + m) mod m

本质就是“圆环距离”。

网站模拟题也反复考了这个长度公式。(Any Docs)

二十、2014 真题：循环队列队空、队满

题目规定：

end1 → 队头元素
end2 → 队尾后一个位置

最多存：

M - 1

个元素。

站内答案：

队空：

e n d 1 = e n d 2

队满：

e n d 1 = (e n d 2 + 1) mod M

(Any Docs)

这是最标准的循环队列模型之一。

二十一、2011 真题为什么不能套上述公式

2011 真题规定的是：

队列非空时：
front → 队头元素
rear  → 队尾元素

并要求：

第一个元素必须存入 A[0]。

答案初始：

f r o n t = 0, r e a r = n - 1

为什么？

因为入队时 rear 先移动：

r e a r = (r e a r + 1) mod n

如果初始：

r e a r = n - 1

第一次：

r e a r = (n - 1 + 1) mod n = 0

于是新元素正好进入：

A[0]

(Any Docs)

这就是前文强调的原因：

循环队列绝对不能脱离指针定义背公式。

二十二、区分队空和队满的三种经典办法

这是理论题高频点。

方法一：牺牲一个单元

队空：

f r o n t = r e a r

队满：

(r e a r + 1) mod m = f r o n t

最大容量：

m - 1

方法二：增加 size

维护：

size = 当前元素数量

队空：

s i z e = 0

队满：

s i z e = m

这时数组全部单元都可以用。

方法三：增加 tag

当：

f r o n t = r e a r

时，再通过 tag 区分：

最后一次操作是出队 → 空
最后一次操作是入队 → 满

这种题非常适合以后变式考。

二十三、双端队列

双端队列：

Deque

允许：

左端入
右端入
左端出
右端出

但 408 特别喜欢限制其中某些操作。

二十四、2010 真题：两端入、一端出

题目大意：

a,b,c,d,e

依次到来。

允许：

两端入队
固定一端出队

问哪个出队序列不可能。

站内答案对应序列：

d,b,c,a,e

(Any Docs)

极好用的方法：反向删除法

如果所有元素：

先全部入完
再开始出队

那么反过来想。

最后进入的 e，一定是从队列：

左端

或者：

右端

进入。

所以最终排列中：

e 必须位于某一端。

删除 e。

然后同理：

d 必须位于剩余序列某一端。

再删 d。

然后检查 c……

如果某一步发现“当前最新插入的元素位于中间”，那么这个排列绝不可能形成。

这是限制双端队列特别漂亮的一种方法。

二十五、2021 真题：受限双端队列升级版

题目规定：

一端只能入队
另一端既能入队又能出队

输入：

1,2,3,4,5

问哪个输出序列不可能。

站内答案是不可能产生：

4,1,3,2,5

(Any Docs)

这类题因为入队与出队可以交叉发生，不能简单套“所有元素入完后反删”。

最稳的是：

根据目标输出逐项构造。

如果能构造出来，就是可能；如果某一步出现“必须越过另一个元素才能出队”，就不可能。

二十六、2018 真题：队列 + 栈综合题

这是非常值得掌握的一道。

初始队列：

1,2,3,4,5,6

1 在队头。

有一个空栈。

允许三种操作：

① 队头元素直接输出
② 队头元素进栈
③ 栈顶元素输出

问哪个序列不能产生。

站内答案：

3,4,5,6,1,2

(Any Docs)

为什么？

要先输出：

那么 1、2 必须先从队列取走。

它们又不能输出，只能进栈：

Push 1
Push 2

此时：

栈底 [1,2] 栈顶

然后：

3,4,5,6

可以从队列直接输出。

但最后栈里只能：

2
1

而目标要求：

1
2

违反 LIFO。

所以不可能。

这类综合题的核心思想

看到“队列 + 栈”时：

原队列确定了取出顺序；栈决定了其中暂存元素的反转关系。

这比单独研究两个结构更重要。

二十七、链式队列

经典结构：

Node *front;
Node *rear;

队头负责删除，队尾负责插入。

普通链队入队

rear->next = s;
s->next = NULL;
rear = s;

网站模拟题也直接考过这一指针操作。(Any Docs)

为什么队头、队尾指针都重要？

如果只有链表头：

删除头：

O (1)

找尾：

O (n)

如果同时保存 rear：

入队：

O (1)

出队：

O (1)

二十八、循环单链表只保存 rear 的妙用

模拟题考过：

不带头结点的循环单链表，只保存 rear，入队和出队复杂度是多少？

答案：

O (1), O (1)

(Any Docs)

原因是：

rear
 ↓
尾结点 → 队头 → ... → 尾结点
          ↑
       rear->next

所以队头：

rear->next

直接可以取得。

因此根本不用遍历。

这是一类非常典型的：

“环形结构 + 保存尾指针 = 同时 O(1) 找头和尾”

二十九、2019 真题大题：设计可复用空间的队列

这道是本章最值得重视的算法设计题之一。

要求大意：

初始为空；
可以动态扩容；
出队结点以后不能浪费，空间以后还要重复利用；
队列已经占用的总空间只增不减；
入队、出队始终：

O (1)

站内方案使用循环单链表，保留出队后的结点继续复用。(Any Docs)

为什么不能简单动态数组？

动态数组满后通常需要：

申请更大连续区域；
把已有元素搬过去。

这个扩容步骤可能需要：

O (n)

而题目要求：

始终 O (1)

所以不合适。

循环链表怎么实现

让：

front → 当前队头的前驱
rear  → 当前队尾

环中分成：

有效元素区
+
已经申请但当前空闲的结点区

出队以后：

不 delete。

只是移动 front。

因此旧结点成为空闲空间。

下一次入队优先复用。

只有：

真的没有空闲结点

时才申请新结点。

于是：

分配总空间只增不减；
已出队空间可以复用；
Push / Pop 都只移动几个指针。

均为：

O (1)

这是非常漂亮的结构设计思想。

三十、栈和队列的应用

这一部分站内真题考过：

2009 打印缓冲区；
2012 中缀转后缀的最大栈深；
2014 表达式转换过程中的栈内容；
2015 递归调用栈；
2016 火车轨道；
2024 中缀/后缀表达式。(Any Docs)

其中最重要的是：

表达式

三十一、表达式的三种形式

例如：

a + b \times c

中缀

运算符在中间：

a + b * c

人最习惯。

前缀

+ a * b c

后缀

a b c * +

又叫逆波兰表达式。

最大优势：

不需要括号，而且运算顺序唯一。

三十二、中缀转后缀：必须彻底掌握

准备一个：

运算符栈

从左到右扫描。

遇到操作数

直接输出。

例如：

直接进入后缀序列。

遇到左括号

直接入栈：

遇到右括号

一直弹运算符，直到：

然后把左括号丢掉。

括号本身绝不进入最终后缀表达式。

遇到普通运算符

假设当前运算符为 op。

不断比较栈顶。

如果栈顶运算符优先级：

\geq

当前 op，则把栈顶弹出。

直到：

栈空；
栈顶是左括号；
栈顶优先级低于当前运算符。

然后当前 op 入栈。

三十三、2024 真题：中缀转后缀

题目表达式：

x + y \times (z - u) / v

站内答案对应后缀：

x y z u - * v / +

(Any Docs)

分层理解。

首先：

z - u

后缀：

z u -

于是：

y (z - u)

变成：

y z u - *

再除以 v：

y z u - * v /

最后加 x：

x y z u - * v / +

即：

x y z u - * v / +

三十四、2012 真题：问运算符栈最大深度

表达式较长，并带有双层括号。

题目不是问最终后缀式，而是问：

转换过程中操作符栈同时最多保存多少个符号？

站内答案：

5

关键最大状态类似：

-
*
(
(
+

共 5 个。(Any Docs)

这类题怎么做最快

不要完整写后缀式。

画：

扫描位置 | 运算符栈 | 当前深度

只维护：

maxDepth

即可。

这和前面“最小栈容量”实际上是同一种思想：

最小容量 = 运行过程中最大栈深

三十五、2014 真题：问扫描到某字符时栈中有什么

表达式：

a / b + (c \times d - e \times f) / g

问扫描到 $f$ 时，运算符栈里的内容。

按照规则：

扫描：

a /
b

遇到 +，先弹 /：

遇到：

得到：

+ (

遇到第一个 *：

+ ( *

遇到减号时，因为：

* 的优先级 > -

先把乘号弹掉：

+ ( -

随后遇到第二个乘号：

+ ( - *

扫描到 f 时，f 是操作数，因此栈不变。

所以从栈底到栈顶：

+ ( - *

站内页面这一题部分选项的文本渲染有些异常，但其逐步解析本身体现的正确栈状态就是上述过程。(Any Docs)

三十六、后缀表达式求值

后缀表达式：

5 3 2 + *

使用：

操作数栈

扫描。

遇到数：

Push

遇到运算符：

Pop a
Pop b
计算 b op a
Push结果

特别注意：

b o p a

不是：

a o p b

对于减法、除法，这是超级高频陷阱。

三十七、2018 真题：两个栈求值

站内题设：

操作数栈从底到顶：

5,8,3,2

运算符栈：

*,-,+

每次：

弹出 $a$ ；
再弹出 $b$ ；
弹出运算符；
算：

b o p a

结果重新压入。

最终得到：

15

(Any Docs)

过程：

第一次：

3 + 2 = 5

操作数栈：

5,8,5

第二次：

8 - 5 = 3

变成：

5,3

第三次：

5 \times 3 = 15

三十八、操作数栈最大深度题

模拟题专门考：

操作数栈大小只有 3，哪个表达式求值时会发生上溢？

核心方法：

先转后缀，再扫描后缀表达式，记录操作数栈最大深度。

例如后缀开头连续出现：

A B C D

说明还没遇到运算符以前已经 Push 四个操作数。

因此至少需要：

4

个栈空间。

如果容量只有 3：

上溢

网站模拟题就是用这一方法。(Any Docs)

三十九、递归为什么使用栈

函数：

s(1)

调用：

s(0)

那么运行时调用关系：

main
 ↓
s(1)
 ↓
s(0)

由于后调用的函数先返回：

后调用，先返回

完全符合栈的：

LIFO

因此程序运行时使用调用栈保存：

返回地址；
参数；
局部变量；
寄存器状态；
调用现场等。

四十、2015 真题：递归调用栈

题目程序核心：

s(n) = s(n-1)+n

main 调：

s(1)

最深时：

main
s(1)
s(0)

所以自栈底至栈顶：

main \to s (1) \to s (0)

(Any Docs)

四十一、栈和队列在遍历中的应用

这部分虽然往往在树和图章节真正展开，但现在就要建立映射。

DFS

深度优先：

一路往深处走
走不动再回退

适合：

栈

递归 DFS 本质上也是使用系统调用栈。

BFS

广度优先：

先发现的结点先扩展

适合：

队列

二叉树层序遍历

也是：

队列

模拟题也通过树的层序遍历、图的 DFS/BFS 检查了这一点。(Any Docs)

四十二、实际场景题：到底用栈还是队列？

打印缓冲区

2009 真题：

主机不断产生打印数据
打印机按到达顺序取数据

所以：

FIFO

使用：

队列

(Any Docs)

类似：

CPU 就绪队列；
网络数据缓冲；
BFS；
消息队列；

都体现“先来先服务”。

而：

函数调用；
括号匹配；
DFS；
表达式；
撤销操作；

更自然地对应栈。

四十三、2016 火车轨道题：隐藏的序列划分

站内 2016 真题给列车进入顺序：

8,4,2,5,3,9,1,6,7

希望最终：

1,2,3,...,9

依次离开，问至少要多少条轨道。

站内答案：

4

(Any Docs)

本质

一条轨道内，列车的相对先后顺序不能随便改变。

为了最终递增输出：

分到同一轨道的列车必须形成递增子序列。

所以问题变成：

最少用多少个递增子序列覆盖原序列？

经典结论：

最少递增子序列数 = 最长下降子序列长度

原序列存在：

8,4,2,1

长度：

4

所以至少四条轨道。

同时能构造，例如：

8,9
4,5,6,7
2,3
1

四条足够。

因此：

4

这题其实已经有一点算法思想了。

四十四、数组：关键不是“数组”，而是地址映射

二维数组：

A [m] [n]

本质上最终仍然放在：

一段连续的一维存储空间。

因此核心问题：

二维下标如何映射成一维偏移量？

四十五、行优先存储

如果数组：

A [m] [n]

下标从 0 开始，每个元素占 $w$ 字节。

基址：

B a se

那么：

A [i] [j]

之前完整经过：

i

行。

每行：

n

个元素。

因此前面共有：

in + j

个元素。

地址：

L O C (A [i] [j]) = B a se + (in + j) w

一定记成一句中文：

行优先：先跳完整的行，再跳本行里的列。

四十六、列优先

同一个数组按列优先。

前面完整经过：

j

列。

每列：

m

个元素。

因此：

L O C (A [i] [j]) = B a se + (j m + i) w

一句中文：

列优先：先跳完整的列，再跳本列里的行。

四十七、带非零下界的一般公式

设：

A [L_{1} \dots U_{1}] [L_{2} \dots U_{2}]

列数：

N = U_{2} - L_{2} + 1

行优先：

L O C (A [i] [j]) = B a se + [(i - L_{1}) N + (j - L_{2})] w

这个公式比死背各种 0/1 下标情况更稳。

四十八、2021 真题：反推二维数组列数

已知二维数组按行优先：

L O C (A [0] [0]) = 100

L O C (A [3] [3]) = 220

每个元素一个存储单元。

设每行：

n

个元素。

则：

100 + 3 n + 3 = 220

所以：

3 n = 117

n = 39

因此：

L O C (A [5] [5]) = 100 + 5 \times 39 + 5

得到：

300

站内答案也是 300。(Any Docs)

四十九、特殊矩阵压缩：本章计算题核心

主要掌握：

对称矩阵；
上三角矩阵；
下三角矩阵；
三对角矩阵；
稀疏矩阵。

其中：

对称矩阵

和

三对角矩阵

真题非常典型。

五十、对称矩阵为什么只存一半

若：

a_{ij} = a_{j i}

那么上下三角信息重复。

所以只存：

上三角

或者：

下三角

需要的元素总数：

\frac{n ( n + 1 )}{2}

五十一、下三角矩阵按行优先

假设下标：

1 \leq j \leq i \leq n

存储顺序：

a11
a21 a22
a31 a32 a33
...

第 $i$ 行以前共有：

1 + 2 + \dots + (i - 1)

个元素：

\frac{i ( i - 1 )}{2}

第 $i$ 行内部， $a_{ij}$ 前面有：

j - 1

个。

若一维数组下标从 0 开始：

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

五十二、上三角矩阵按列优先

这其实和上面的形式非常相似。

第 $j$ 列有：

j

个元素：

a1j
a2j
...
ajj

前 $j - 1$ 列：

1 + 2 + \dots + (j - 1)

所以：

\frac{j ( j - 1 )}{2}

列内 $a_{ij}$ 偏移：

i - 1

所以：

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

五十三、2020 真题：对称矩阵 + 列优先

10 阶对称矩阵，只存上三角并按列优先。

问：

m_{7, 2}

在哪里。

因为矩阵对称：

m_{7, 2} = m_{2, 7}

于是只研究：

m_{2, 7}

前 6 列共有：

1 + 2 + 3 + 4 + 5 + 6 = 21

个元素。

在第 7 列中：

m17
m27
...

$m_{2, 7}$ 是第二个，所以相对偏移 1。

因此：

k = 21 + 1

得到：

22

(Any Docs)

五十四、上三角矩阵按行优先

对于：

i \leq j

第一行存：

n

个。

第二行：

n - 1

个。

……

第 $i$ 行以前：

n + (n - 1) + \dots + (n - i + 2)

一共有：

i - 1

项。

求和：

\frac{( i - 1 ) ( 2 n - i + 2 )}{2}

第 $i$ 行内部：

a_{ii}, a_{i, i + 1}, \dots

$a_{ij}$ 的偏移：

j - i

因此：

k = \frac{( i - 1 ) ( 2 n - i + 2 )}{2} + j - i

五十五、2018 真题：12 阶对称矩阵

只存上三角，按行优先。

求：

m_{6, 6}

一维数组下标。

前五行分别有：

12, 11, 10, 9, 8

所以：

12 + 11 + 10 + 9 + 8 = 50

而 $m_{6, 6}$ 正好是第 6 行第一个存储元素。

因此：

50

(Any Docs)

五十六、最强方法：不要死背四套三角公式

很多学生最后背成：

上三角行优先一套
上三角列优先一套
下三角行优先一套
下三角列优先一套

然后考试必混。

只需记住一句：

k = 前面完整部分的元素数 + 当前行 / 列内偏移

例如下三角列优先：

第0列：n个
第1列：n-1个
第2列：n-2个
...

求 $a_{ij}$ ，就：

算第 $j$ 列前面的所有列；
再算本列内的偏移。

现场 15 秒推导，比背公式可靠得多。

五十七、模拟题：下三角按列优先

网站模拟题给：

0 \leq i, j < n

下三角：

i \geq j

按列优先。

第 $j$ 列之前：

n + (n - 1) + \dots + (n - j + 1)

有：

j

项，所以：

\frac{j ( 2 n - j + 1 )}{2}

本列从：

a_{j j}

开始。

到：

a_{ij}

偏移：

i - j

因此：

k = \frac{j ( 2 n - j + 1 )}{2} + i - j

这也是网站模拟题给出的正确关系。(Any Docs)

五十八、三对角矩阵

三对角矩阵只允许：

∣ i - j ∣ \leq 1

的位置可能非零。

形状：

× ×
× × ×
  × × ×
    × × ×
      ...
          × ×

第一行：

2

个。

中间每行：

3

个。

最后一行：

2

个。

总非零元素个数：

2 + 3 (n - 2) + 2

即：

3 n - 2

五十九、2016 真题：100 阶三对角矩阵

题目：

100 阶三对角矩阵按行优先压缩到下标从 0 开始的一维数组。

求：

m_{30, 30}

的位置。

站内答案：

87

(Any Docs)

解法

第 1 行：

2

个元素。

第 2～29 行共有：

28

行，每行 3 个。

因此第 30 行前：

2 + 28 \times 3

即：

86

个元素。

第 30 行顺序：

m30,29
m30,30
m30,31

$m_{30, 30}$ 是这一行第二个元素。

数组从 0 开始，所以：

86 + 1 = 87

即：

87

六十、三对角矩阵的一般公式

对于内部行：

2 \leq i \leq n - 1

并且：

i - 1 \leq j \leq i + 1

前面已经有：

2 + 3 (i - 2)

个元素：

3 i - 4

当前行偏移：

j - (i - 1) = j - i + 1

所以：

k = (3 i - 4) + (j - i + 1)

化简：

k = 2 i + j - 3

这里假定：

原矩阵下标从 1 开始；
压缩数组从 0 开始；
当前元素位于普通中间行。

例如：

i = 30, j = 30

则：

k = 2 \times 30 + 30 - 3

k = 87

六十一、稀疏矩阵

如果一个矩阵大部分元素都是：

0

那么存整个二维数组太浪费。

例如：

1000 \times 1000

矩阵只有 1000 个非零元素。

如果每个元素 4 B，普通数组需要：

1000 \times 1000 \times 4

即约：

4 MB

但真正有用的数据只有极少一部分。

六十二、三元组表

每个非零元素记录：

行号
列号
值

即：

(i, j, v a l u e)

因此如果：

行号 2 B；
列号 2 B；
值 4 B；

每个三元组：

2 + 2 + 4 = 8 B

1000 个非零元素：

1000 \times 8

所以：

8000 B

网站模拟题就考了这个计算。(Any Docs)

六十三、2017 真题：稀疏矩阵用什么结构

站内真题答案：

三元组表 + 十字链表

(Any Docs)

三元组表

特点：

(i,j,value)

适合：

顺序保存；
存储简单；
非零元素数量较少。

十字链表

每个非零元素同时属于：

所在行链表
+
所在列链表

因此适合：

按行访问；
按列访问；
动态修改。

六十四、2023 真题：三元组表还必须保存什么？

每个三元组已经保存：

行号
列号
值

但光有这些还不能知道：

原矩阵到底有多大。

所以还必须保存：

总行数

以及：

总列数

而不必单独保存：

包含非零元素的行数
包含非零元素的列数

因为这些可以从三元组统计。

站内 2023 真题答案也是“总行数 + 总列数”。(Any Docs)

六十五、本章最容易混淆的 10 个坑

坑 1：入栈顺序确定 ≠ 出栈顺序确定

Push、Pop 可以交错。

坑 2：栈不是两端操作

只有：

栈顶

可以插入和删除。

坑 3：后缀求值的左右操作数反了

弹：

a
b

应该：

b o p a

坑 4：循环队列公式脱离 front/rear 定义

这是本章最危险的错误。

坑 5：忘了循环队列可能牺牲一个单元

数组大小 $m$ ，不一定能存 $m$ 个。

常见模型只能存：

m - 1

坑 6：数组下标从 0 还是 1

特殊矩阵压缩题几乎必考这个细节。

坑 7：原矩阵下标和压缩数组下标可能不同

例如：

mij 从1开始
N[k] 从0开始

这是 2016、2018 等真题常见设置。

坑 8：对称矩阵元素不在存储三角区

例如只存上三角，却给：

m_{7, 2}

先利用：

m_{7, 2} = m_{2, 7}

再算。

坑 9：行优先和列优先混淆

行优先：

先完整行

列优先：

先完整列

坑 10：链队空队列时 rear 没同步

删除最后一个元素以后：

front
rear

通常都要恢复到空队列约定状态。

写算法题时这是常见扣分点。

六十六、把本章所有题型压缩成几个“万能算法”

模型 A：栈输出序列

看到：

入栈序列
+
目标出栈序列

执行：

目标元素未入栈 → 不断Push
目标元素已入栈 → 检查是否为栈顶

如果不是：

非法

模型 B：最小栈容量

直接模拟，记录：

max (栈元素数量)

模型 C：循环队列

先写：

front指？
rear指？

再推：

空
满
长度
入队
出队

千万不要反过来。

模型 D：受限双端队列

如果：

所有元素先入完，再统一出

优先尝试：

逆序删除两端法

如果入出交替：

目标序列逐项模拟

模型 E：中缀转后缀

牢记：

操作数 → 输出
( → 入栈
) → 弹到(
运算符 → 弹出优先级≥自己的栈顶，再入栈

模型 F：后缀求值

数字 → Push

运算符 →
a=Pop
b=Pop
Push(b op a)

模型 G：特殊矩阵

永远：

k = 前面完整部分 + 当前部分偏移

不要硬背十几个公式。

六十七、结合模拟题值得准备的变式

网站模拟题已经在真题基础上进一步考了共享栈、链栈、循环链队、表达式操作数栈深、三维数组与对称矩阵组合等。(Any Docs)

因此复习时尤其建议防下面几种新组合。

预测变式 1：循环队列 + tag

给：

front
rear
tag

要求：

判断空满；
求队列长度；
完成 EnQueue / DeQueue。

这种题重点考查是否真正理解：

f r o n t = r e a r

为什么本身无法区分空和满。

预测变式 2：两个栈实现队列

设：

S1：输入栈
S2：输出栈

EnQueue：

Push S1

DeQueue：

如果 S2 不空：

Pop S2

如果 S2 为空：

把S1全部倒进S2

然后：

Pop S2

虽然某一次操作可能：

O (n)

但摊还复杂度：

O (1)

非常适合和后续算法复杂度综合考。

六十八、预测变式 3：一个队列实现栈

入队以后把队列前面的元素重新轮转。

例如已有：

1,2,3

新元素 4 入队：

1,2,3,4

再依次把前三个移到尾部：

4,1,2,3

此时队头就是最新元素。

于是 DeQueue 就模拟 Pop。

网站模拟题已经考查过“一个队列可以实现栈、两个栈可以实现队列”这一概念。(Any Docs)

六十九、预测变式 4：更一般的带状矩阵

假设：

∣ i - j ∣ \leq k

才非零。

这就是三对角矩阵：

k = 1

的一般化。

考试完全可以把“三对角”稍微改成“五对角”。

不要背三对角专门公式，而是数：

每行到底保存多少元素

然后继续：

前面完整行 + 行内偏移

照样解决。

七十、预测变式 5：多维数组 + 特殊矩阵

网站模拟题已经出现比较强的组合：

三维数组的前两维满足对称关系，再结合列优先和压缩存储计算地址。(Any Docs)

这类题看起来恐怖，实际拆成两层：

第一层算：

完整二维层占多少元素

第二层算：

当前二维层内位置

所以整体永远仍是：

完整层偏移 + 层内偏移

七十一、这章复习优先级怎么安排

如果以 408 得分效率排序，建议：

第一梯队：必须完全熟练

栈出栈序列是否合法；
最小栈容量；
循环队列空、满、长度；
双端队列模拟；
栈 + 队列综合；
中缀转后缀；
后缀表达式求值；
对称矩阵地址；
三对角矩阵地址。

这部分必须达到：

看到题几乎不用回忆知识点，直接开始操作。

第二梯队：必须理解

链栈；
链队；
循环链表队列；
共享栈；
递归调用栈；
稀疏矩阵三元组；
十字链表；
普通二维数组地址。

第三梯队：防综合题

两栈实现队列；
队列实现栈；
表达式最大栈深；
多维数组地址；
带状矩阵；
栈/队列与树、图遍历结合；
动态空间复用队列设计。

七十二、一张“考场公式表”

真正值得记的其实没有多少。

循环队列常用模型

当 front 指队头、rear 指队尾后一空位，并牺牲一格：

Q u e u e E m pt y : f r o n t = r e a r

Q u e u e F u l l : (r e a r + 1) mod m = f r o n t

L e n g t h = (r e a r - f r o n t + m) mod m

二维数组行优先

L O C (A [i] [j]) = B a se + (in + j) w

二维数组列优先

L O C (A [i] [j]) = B a se + (j m + i) w

对称矩阵元素数

\frac{n ( n + 1 )}{2}

下三角、行优先、1 基矩阵 → 0 基数组

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

上三角、列优先、1 基矩阵 → 0 基数组

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

三对角矩阵元素数量

3 n - 2

三对角内部元素位置

在前述下标约定下：

k = 2 i + j - 3

所有合法固定入栈序列对应出栈序列数量

C_{n} = \frac{1}{n + 1} (n 2 n)

七十三、最后给出总结成真正的“第 3 章思维”

这一章表面上是在学四样东西：

栈
队列
数组
特殊矩阵

实际上只有三个核心思想。

第一：受限线性表就是研究“允许怎样移动”

栈：

只能栈顶动

队列：

队尾进、队头出

双端队列：

题目规定哪端能动，就严格按哪端动

所以序列题的核心不是背性质，而是：

模拟状态变化

第二：指针题不要背公式，要先确定“指针指什么”

尤其：

top
front
rear
end1
end2

先画：

元素 | 空位 | 指针

再推公式。

这一个习惯能解决绝大多数循环队列坑题。

第三：数组压缩问题全部都是“计数”

无论：

二维数组；
对称矩阵；
三角矩阵；
三对角矩阵；
三维数组；

本质永远是：

位置 = 前面已经存了多少元素 + 当前块内部偏移

真正掌握后，根本不需要背四五种三角矩阵公式。

综合本站里的真题，本文将把本章最重要的典型题锁定为：2009 最小栈容量、2013 特定位置出栈值、2014 循环队列空满、2018 队列+栈综合、2019 可复用空间队列设计、2012/2014/2024 表达式、2016 三对角矩阵、2018/2020 对称矩阵压缩、2021 二维数组地址。把这些题的“模型”真正吃透，第 3 章绝大部分 408 题就已经覆盖了。(Any Docs)

本站的 408 真题·数据结构第 3 章本站的 408 模拟题·数据结构第 3 章