第 3 章栈、队列和数组

408 数据结构第 3 章栈、队列和数组复习讲义，涵盖核心概念、重点考点与典型题型。

从考研角度，可以先形成这张总图：

内容	重要程度	最容易考什么
栈的基本性质	★★★★★	出栈序列是否合法、最小栈容量、栈深
顺序栈、共享栈	★★★★☆	`top` 含义、判空判满、指针变化
队列	★★★★★	FIFO、队头队尾位置
循环队列	★★★★★	判空、判满、元素个数、指针变化
链式队列	★★★★☆	入队/出队指针修改
双端队列	★★★☆☆	合法输出序列
括号匹配	★★★☆☆	栈的应用
表达式求值	★★★★★	中缀转后缀、后缀求值、最大栈深
递归与层次遍历	★★★★☆	为什么分别使用栈和队列
多维数组地址计算	★★★★☆	行优先、列优先
特殊矩阵压缩	★★★★★	对称矩阵、三角矩阵、三对角矩阵
稀疏矩阵	★★★☆☆	三元组存储及空间计算

一、3.1 栈

1. 栈到底是什么

栈本质上仍然是线性表，只是把线性表的操作限制了：

只能在同一端插入和删除

               ← 出栈
               → 入栈
          ┌───────────┐
栈顶 →    │     E     │  ← 最后进入
          ├───────────┤
          │     D     │
          ├───────────┤
          │     C     │
          ├───────────┤
          │     B     │
          ├───────────┤
栈底 →    │     A     │  ← 最先进入
          └───────────┘

允许插入、删除的一端叫栈顶 Top，另一端叫栈底 Bottom。

因此栈最核心的性质就是：

后进先出 LIFO。

例如依次把 A、B、C、D 全部入栈，再全部出栈：

入栈：A → B → C → D

出栈：D → C → B → A

但考试真正重要的不是这个最简单的“全部入完再全部出”，而是：

入栈和出栈可以交叉进行。

这就是出栈序列题的来源。资料将出入栈序列列为本节高频考点，并追踪到多次统考。

二、★★★★★ 出栈序列合法性——本章第一大重点

假设固定入栈次序：

1 2 3 4 5

不是只能产生

5 4 3 2 1

还可以：

1 2 3 4 5

因为可以：

1进 → 1出
2进 → 2出
……

甚至可以：

2 1 4 3 5

操作：

1进
2进
2出
1出
3进
4进
4出
3出
5进
5出

因此判断一个序列是否合法，最可靠的方法不是背规律，而是：

按目标输出序列进行模拟。

1. 标准模拟法

假设入栈序列：

1 2 3 4 5

判断目标：

3 2 1 5 4

从第一个目标 3 开始。

要让 3 出栈：

1入栈
2入栈
3入栈

此时：

栈顶
 ↓
 3
 2
 1

输出 3。

下一目标 2，它正好在栈顶，所以输出。

下一目标 1，也是栈顶，输出。

随后：

4入栈
5入栈
5出
4出

因此：

3 2 1 5 4

合法。

资料中的配套题正好给出了这个例子，并且增加了“栈容量只有 3”的限制，此序列仍然合法，因为任何时刻最多只有三个元素同时位于栈中。

2. 一个特别重要的规律

假设输入：

1 2 3 ... n

如果某时刻首先输出了较大的元素，例如：

那么意味着此前：

1 2 3 4 5

至少都已经进入过栈。

此时如果没有提前弹出其中某些元素，那么 5 下面必然是：

所以一旦某些元素已经被“压在下面”，它们之间的相对弹出顺序就被栈结构限制住了。

考试中的很多“若第几个输出为多少，则后面可能是什么”本质都在考这个。

三、Catalan 数

如果有 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 数，重点是：

看到“固定入栈顺序，问有多少种合法出栈序列”，考虑 Catalan 数。

四、栈深和最小栈容量

这个知识点非常容易和出栈序列一起考。

栈深就是某一时刻栈中元素个数。

最大栈深就是整个操作过程中栈元素数量达到的最大值。

例如：

1入
2入
3入
3出
4入
4出
2出
1出

栈大小依次：

所以最大栈深：

3

也就意味着至少需要容量为 3 的栈。

资料将“栈深分析”也列为了历年考点。

五、3.1.2 顺序栈

顺序栈就是：

用数组实现栈。

例如：

#define MaxSize 50

typedef struct {
    ElemType data[MaxSize];
    int top;
} SqStack;

这里最重要的问题不是代码，而是：

top 到底指哪里？

这是考试的大坑。

1. 最常见约定：`top` 指向栈顶元素

初始：

top = -1

因为：

data[0]

才是第一个合法位置。

因此空栈：

top = -1

满栈：

top = MaxSize - 1

入栈：

S.data[++S.top] = x;

为什么先 ++top？

原来：

top = -1

第一个元素应该放到：

data[0]

所以：

-1 → 0 → 写入元素

出栈：

x = S.data[S.top--];

即：

先取栈顶
再 top--

资料特别提醒：数组里即便还残留旧数据，只要已经不在 top 所界定的有效范围内，它就已经不是栈元素了。

2. 另一种约定：`top` 指向“栈顶的下一个位置”

也可能规定：

空栈 top = 0

那么入栈就变成：

S.data[S.top++] = x;

出栈：

x = S.data[--S.top];

因此千万不要死背：

Push 一定 ++top
Pop 一定 top--

真正应该先问：

题目中的 top 指向哪里？

资料也专门提醒，不同 top 定义对应完全不同的入栈、出栈、判空和判满方式。

六、★★★★★ 共享栈

两个栈如果各自固定分配一个数组：

栈 A：满了
栈 B：还有很多空间

仍然不能共享，很浪费。

于是让两个栈共用一个数组：

下标
0                                           MaxSize-1
↓                                                ↓
┌────────────────────────────────────────────────┐
│ → → → 栈0                  栈1 ← ← ←            │
└────────────────────────────────────────────────┘
      top0                    top1

两个栈分别从数组两端向中间生长。

如果 top 都指向当前栈顶，则初始：

top0 = -1
top1 = MaxSize

真正栈满只发生在：

两个栈顶相邻

即：

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

这也是共享栈最大的意义：

只要总空间还有位置，任意一个栈都可以继续增长。

所以共享栈降低了栈溢出的概率，提高空间利用率。

七、3.1.3 链栈

栈也可以用链表实现。

最自然的方案：

链表头部作为栈顶。

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

O (1)

于是：

top
 ↓
[A] → [B] → [C] → NULL
 ↑
栈顶

Push：

创建新结点 p
p->next = top
top = p

Pop：

p = top
x = p->data
top = top->next
free(p)

因此顺序栈和链栈的入栈、出栈都是：

O (1)

区别主要是空间。

顺序栈使用连续空间，访问局部性好，但固定容量可能溢出；链栈动态申请结点，不容易出现固定容量问题，但是每个元素需要多存一个指针。

八、3.2 队列

栈是：

后进先出

队列则是：

先进先出

即 FIFO。

出队 ← A B C D E ← 入队
       ↑       ↑
     front    rear

队头 front 是删除的一端。

队尾 rear 是插入的一端。

例如：

A入
B入
C入

只能依次：

A出
B出
C出

普通队列不允许直接“删除队尾元素”，这也是资料模拟题中的考点。

九、★★★★★ 3.2.2 循环队列——本章第二大重点

普通顺序队列会出现一个重要问题：

假溢出

假设数组：

0 1 2 3 4

一开始：

A B C D E

后来：

A、B、C 出队

数组可能变成：

× × × D E

虽然：

0 1 2

空着，但 rear 已经到数组最右端。

这就是：

假溢出。

实际有空位，只是普通数组队列不会回头利用。

解决办法：

把数组逻辑上首尾相连。

于是产生循环队列。

十、循环队列为什么要取模

假设：

MaxSize = 5

当前：

rear = 4

rear 再向右移动：

(4 + 1) mod 5 = 0

所以：

4 → 0

完成回绕。

队尾更新：

r e a r = (r e a r + 1) mod M a x S i z e

队头更新：

f r o n t = (f r o n t + 1) mod M a x S i z e

十一、★★★★★ 循环队列的判空和判满

这是408非常经典的坑。

假设：

front 指向队头元素
rear 指向队尾元素的下一个空位置

空队：

f r o n t = r e a r

但如果让整个数组都可以装元素，队满时也可能出现：

f r o n t = r e a r

这样无法区分。

最经典的方法：

牺牲一个存储单元。

于是规定：

空：

f r o n t = r e a r

满：

(r e a r + 1) mod M a x S i z e = f r o n t

所以数组长度为 MaxSize 时，最多只能装：

M a x S i z e - 1

个元素。

资料专门把这一点列为循环队列核心考点，并给出了初始化、入队和出队完整实现。

十二、★★★★★ 循环队列当前元素个数

这是必背公式之一。

L e n g t h = (r e a r - f r o n t + M a x S i z e) mod M a x S i z e

为什么？

如果没有发生绕回，比如：

front = 2
rear  = 5

那么：

L e n g t h = 5 - 2 = 3

如果发生绕回：

front = 7
rear  = 2
MaxSize = 10

队列实际上：

7 8 9 0 1

共有：

(2 - 7 + 10) mod 10 = 5

所以统一公式就是：

(r e a r - f r o n t + M a x S i z e) mod M a x S i z e

配套选择题也直接考查了这一公式。

十三、不牺牲一个位置可以吗？

可以。

资料给出了另外两类典型方法。

一种是额外记录当前元素数量 size。

此时：

front == rear

既可能表示空，也可能表示满。

由：

size == 0

判断空；

由：

size == MaxSize

判断满。

另一种是增加 tag。

例如：

tag = 0

表示最后一次是出队；

tag = 1

表示最后一次是入队。

当：

front == rear

时再结合 tag 判断即可。

所以一定记住：

front == rear 到底表示什么，必须看题目采用哪一种循环队列定义。

十四、3.2.3 链式队列

链式队列通常就是：

带队头指针和队尾指针的单链表。

front
 ↓
头结点 → A → B → C → NULL
                     ↑
                    rear

资料主要采用带头结点方案。

空队时：

front == rear

并且二者都指向头结点。

1. 入队

假设新结点：

需要：

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

可以理解为：

原尾结点 → 新结点
           ↑
         新 rear

2. 出队

删除的是：

front->next

即第一个数据结点。

核心：

p = Q.front->next;
Q.front->next = p->next;

但有一个非常重要的边界情况。

如果原来只有：

头结点 → A
         ↑
        rear

删除 A 后：

rear

不能继续指向已经释放的 A。

必须：

Q.rear = Q.front;

这是链式队列指针题最常考的细节之一。

十五、一个很经典的链式队列技巧

如果使用：

不带头结点的循环单链表表示队列，并且只保存 rear。

       ┌─────────────────────┐
       ↓                     │
      A → B → C → D ─────────┘
      ↑           ↑
   rear->next    rear

这时：

rear

直接找到队尾；

同时：

rear->next

直接找到队头。

因此：

进队：

O (1)

出队：

O (1)

配套选择题正好考了这一点。

这说明一道很重要的数据结构设计思想：

保存哪个指针，要看它能不能快速找到最常操作的位置。

十六、3.2.4 双端队列

普通队列：

一边进
另一边出

双端队列：

两边都能进
两边都能出

        双端队列

← 删除                删除 →
→ 插入   A B C D      插入 ←

还会有限制版本。

输入受限双端队列：一端不能插入，但两端可删除。

输出受限双端队列：一端不能删除，但两端可插入。

这里不用背复杂规律。

做序列题时直接模拟。

资料也将双端队列的输出序列合法性列为考点。

十七、3.3 栈和队列的应用

这部分真正要理解的不是“哪个地方用了栈”，而是：

为什么它必须表现出 LIFO 或 FIFO？

只要理解这一层，很多后面的树、图算法都会非常自然。

十八、3.3.1 括号匹配

例如：

[ ( [ ] [ ] ) ]

扫描到：

意味着将来需要：

但紧接着又出现：

那么当前最急迫的匹配对象变成：

之后如果又出现：

又必须优先寻找对应的：

也就是说：

最后出现的未匹配左括号，最先被匹配。

这正是 LIFO。

所以算法是：

for (每个字符 ch) {
    if (ch 是左括号)
        Push(S, ch);
    else if (ch 是右括号) {
        if (栈空)
            return false;

        Pop(S, top);

        if (top 和 ch 不匹配)
            return false;
    }
}

return 栈空;

这里有两种失败情况。

第一种：

())

第三个 ) 出现时栈已经空了。

说明：

右括号太多

第二种：

((())

扫描结束栈仍然非空。

说明：

左括号太多

资料中的括号匹配过程也是按这一思想描述的。

十九、★★★★★ 3.3.2 表达式求值——本章第三大重点

考研最重要的是掌握：

中缀表达式
前缀表达式
后缀表达式

我们平时写的是中缀：

A + B

前缀：

+ A B

后缀：

A B +

最大的区别是：

前缀和后缀表达式本身就编码了计算顺序，所以通常不需要括号。

二十、中缀转后缀——手算法

例如：

A + B * (C - D) - E / F

先按照正常运算顺序加全括号：

((A + (B * (C-D))) - (E/F))

然后把每个运算符放到对应两个操作数后：

最终：

A B C D - * + E F / -

也就是：

ABCD-*+EF/-

资料正是以这个表达式为示例。

二十一、★★★★★ 计算机如何实现中缀转后缀

使用一个：

运算符栈。

从左往右扫描。

遇到操作数：

直接输出

遇到左括号：

直接入栈

遇到右括号：

不断出栈并输出
直到遇到左括号
最后丢弃左括号

遇到运算符：

关键比较当前运算符与栈顶运算符的优先级。

例如当前：

栈顶：

由于：

* 比 + 优先级高

所以 * 入栈。

反过来当前：

栈顶：

则必须先把 * 弹出，因为前面的乘法必须先完成。

因此对于通常的左结合运算符，可以记成：

当前运算符优先级高于栈顶：入栈。

当前运算符优先级低于或等于栈顶：先弹栈，直到它可以入栈。

资料完整列出了这一转换算法。

二十二、为什么表达式题经常考“最大栈深”

例如资料模拟题：

a - (b*c + d/e)

扫描过程中运算符栈最大状态可能达到：

-
(
+
/

所以最大栈深为：

4

这类题不要凭感觉，要模拟栈。

配套题答案也是 4。

二十三、★★★★★ 后缀表达式求值

这一过程比“中缀转后缀”还规律。

从左往右扫描。

操作数：

入栈

运算符：

弹出两个操作数
进行运算
结果重新入栈

最大的坑：

先弹出来的是右操作数。

假设当前运算符：

依次弹出：

Y
X

真正计算：

X - Y

而不是：

Y - X

对于除法也是：

X / Y

不是：

Y / X

资料也特别按照“先弹右操作数、再弹左操作数”说明了这一规则。

例子

后缀：

5 2 3 * +

过程：

5入栈

5

2入栈

5
2

遇到 *：

3 出
2 出

计算：

2 \times 3 = 6

6 入栈：

5
6

遇到 +：

5 + 6 = 11

最终：

二十四、3.3.3 递归为什么使用栈

例如：

f(3)

调用：

f(3)
 ↓
f(2)
 ↓
f(1)

返回时恰恰反过来：

f(1) 返回
f(2) 返回
f(3) 返回

即：

后调用的函数先返回。

这就是栈。

每一层递归都需要保存一个栈帧，里面通常保存：

参数
局部变量
返回地址
现场信息

因此递归深度太深可能产生：

Stack Overflow

例如递归：

f(n) {
    f(n - 1);
}

递归深度为：

O (n)

那么辅助空间一般也是：

O (n)

资料指出任何递归算法原则上都可以借助显式栈改写为非递归形式。

二十五、3.3.4 队列与层次遍历

后面的树章节会反复遇到。

假设二叉树：

层序遍历：

A B C D E F

为什么使用队列？

根结点：

A 入队

A 出队后：

B、C 入队

B 先于 C 被发现，所以：

B 先出

然后：

D、E 入队

C 再出：

F 入队

队列确保：

先发现的结点先处理。

因此 BFS、层序遍历天然对应 FIFO。

资料也明确指出二叉树层序遍历通过队列维持“先发现先访问”的顺序。

二十六、3.3.5 队列在计算机系统中的应用

这部分不是难点，理解即可。

典型思想就是：

大量请求暂时无法同时处理 → 排队。

例如 CPU 进程调度中的就绪队列、I/O 请求队列、打印任务队列、网络数据缓冲区。

本质都是：

请求 1
请求 2
请求 3
……

按某种顺序等待系统处理。

资料将队列在计算机系统中的用途归纳为缓冲区与资源调度。

二十七、3.4 数组

数组可以理解成：

线性表的推广。

一维数组：

A[0]
A[1]
A[2]
...

二维数组则可以理解为：

一个“元素本身又是一维数组”的线性表

例如：

A[3][4]

逻辑上：

a00 a01 a02 a03
a10 a11 a12 a13
a20 a21 a22 a23

但内存本质上还是：

一条一维连续地址空间。

所以必须决定二维数组如何“摊平”。

二十八、★★★★★ 行优先存储

假设二维数组：

A[m][n]

共有：

m 行
n 列

每个元素占 L 个字节。

按行优先：

a00 a01 ... a0,n-1
a10 a11 ... a1,n-1
...

对于：

A[i][j]

前面已经完整存了 i 行。

每一行 n 个元素，所以前面：

in

个元素。

在本行之前又有：

j

个。

因此偏移元素数：

in + j

地址：

L O C (A [i] [j]) = L O C (A [0] [0]) + (in + j) L

二十九、列优先

列优先：

a00 a10 a20 ...
a01 a11 a21 ...

如果有 m 行，那么前面完整存了 j 列：

j m

然后当前列中前面有：

i

个元素。

所以：

L O C (A [i] [j]) = L O C (A [0] [0]) + (j m + i) L

资料对二维数组的行优先、列优先映射都给出了相同的计算思想。

这类题最稳妥的方法不是背公式，而是：

前面完整存了多少行/列 + 当前行/列已经走了多少元素。

三十、★★★★★ 3.4.3 特殊矩阵压缩存储——本章第四大重点

普通：

n \times n

矩阵需要：

n^{2}

个存储单元。

但有些矩阵有大量重复元素或零元素。

那么就没必要全部存。

这就是：

压缩存储。

核心思想只有一句：

只保存真正需要独立保存的信息。

三十一、★★★★★ 对称矩阵

对称矩阵满足：

a_{ij} = a_{j i}

例如：

a11 a12 a13
a21 a22 a23
a31 a32 a33

因为：

a_{12} = a_{21}

a_{13} = a_{31}

a_{23} = a_{32}

所以上半部分和下半部分重复。

只需要存一边：

下三角 + 主对角线

或者：

上三角 + 主对角线

元素总数：

1 + 2 + \dots + n

因此：

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

原来：

n^{2}

现在：

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

三十二、★★★★★ 对称矩阵下标映射怎么推

假设按下三角、行优先保存，并采用：

矩阵行列号从 1 开始
B 数组下标从 0 开始

存储顺序：

a11

a21 a22

a31 a32 a33

a41 a42 a43 a44
...

求：

aij

其中：

i \geq j

在第 i 行之前已有：

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

即：

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

个元素。

第 i 行里：

a_i1

是第一个，所以 a_ij 的行内偏移是：

j - 1

所以：

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

如果：

i < j

因为矩阵对称：

a_{ij} = a_{j i}

直接交换：

(i,j) → (j,i)

再套公式。

三十三、真正重要的是“推”，不是背

特殊矩阵公式很多。

如果同时出现：

0 / 1 起始下标
行优先 / 列优先
上三角 / 下三角

死背非常容易全乱。

考试通用方法：

压缩下标 = 前面完整存储的元素数 + 本组内部偏移。

例如资料模拟题考“下三角矩阵按列优先”。

如果数组下标从 0 开始，则第 j 列前面的元素数量为：

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

即：

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

本列内部：

i - j

于是：

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

资料中的对应模拟题正是这样推导，而不是靠硬背公式。

三十四、三角矩阵

以下三角矩阵：

a11  c   c   c
a21 a22  c   c
a31 a32 a33  c
a41 a42 a43 a44

上三角区域全都是一个相同常量：

因此下三角部分：

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

个独立元素。

再额外存一次：

总共：

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

个存储位置。

资料给出的下三角矩阵压缩思想就是如此。

三十五、上三角矩阵

反过来：

a11 a12 a13 a14
 c  a22 a23 a24
 c   c  a33 a34
 c   c   c  a44

下三角所有元素都是：

同样需要：

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

个位置。

如果按行优先，第 1 行存：

n

个。

第 2 行：

n - 1

个。

第 3 行：

n - 2

个。

所以公式仍然从：

前面完整行的元素数量之和

推导。

资料对此也给出了完整下标映射。

三十六、三对角矩阵

三对角矩阵的特点：

只有：

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

可能非零。

也就是：

∣ i - j ∣ \leq 1

的位置可能非零。

如果：

∣ i - j ∣ > 1

那么：

a_{ij} = 0

例如：

× × 0 0 0
× × × 0 0
0 × × × 0
0 0 × × ×
0 0 0 × ×

非零元素数量是多少？

第 1 行：

2 个

第 n 行：

2 个

中间：

n-2 行，每行 3 个

因此：

2 + 3 (n - 2) + 2

即：

3 n - 2

所以本来：

n^{2}

个位置，只需要约：

3 n

个位置。

资料也将三对角矩阵作为特殊矩阵压缩存储的重要类型。

三十七、3.4.4 稀疏矩阵

稀疏矩阵不是要求某种固定结构，而是：

绝大多数元素为 0。

例如：

全部保存显然很浪费。

于是只记录每个非零元素：

行
列
值

形成三元组：

(row, col, value)

例如：

(0,4,5)
(2,1,8)
(3,3,3)

这就是三元组表。

三十八、稀疏矩阵空间计算

资料里有一道典型题：

1000 × 850

的稀疏矩阵只有：

1000 个非零元素

如果三元组记录：

行号
列号
元素值

每个整数 2B，元素值 4B。

一条三元组：

2 + 2 + 4 = 8 B

1000 个：

1000 \times 8 = 8000 B

所以不要看到：

1000 × 850

就去计算整个矩阵。

压缩存储真正关心的是：

非零元素个数。

配套资料中正有这一类三元组空间计算题。

三十九、把本章所有结构串起来

理解本章最好的方法，是不要把它们当作四个孤立知识点。

线性表本来允许：

任意位置插入
任意位置删除

限制成：

只能同一端插入删除

得到：

栈。

限制成：

一端插入
另一端删除

得到：

队列。

放宽队列：

两端都能操作

得到：

双端队列。

把线性序列推广到多维：

数组。

发现数组中大量元素具有规律，可以减少重复信息：

特殊矩阵压缩存储。

所以第 3 章其实是在讲：

                 线性表
                   │
          ┌────────┴────────┐
          │                 │
       限制操作           推广维度
          │                 │
     ┌────┴────┐           数组
     │         │             │
    栈        队列        特殊矩阵
   LIFO       FIFO            │
     │         │          压缩存储
 递归/表达式 层序/BFS

四十、本章最应该形成的 8 个“秒杀反应”

这部分建议直接作为复习检查标准。

看到固定入栈序列，判断出栈序列：不要猜，模拟 Push / Pop。

看到问合法出栈序列个数：考虑 Catalan 数。

看到顺序栈的 Push / Pop 代码：第一件事看 top 指向“栈顶元素”还是“下一个空位置”。

看到共享栈：两个栈从数组两端向中间生长；若 top 指向栈顶元素，则满时：

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

看到循环队列：马上想到三个核心式子：

f r o n t = r e a r

表示空；

(r e a r + 1) mod M a x S i z e = f r o n t

表示满；

L e n g t h = (r e a r - f r o n t + M a x S i z e) mod M a x S i z e

表示当前元素个数。

看到后缀表达式运算符：先弹的是右操作数。

看到数组地址计算：不要死背，先数“前面完整存了多少行/列”。

看到特殊矩阵压缩下标：统一使用：

前面已经存储的元素数 + 当前区域内偏移。

最后给你一个复习优先级

如果现在是第一轮学习，本章建议按下面顺序掌握：

第一优先级：出入栈序列与栈深 → 循环队列 → 中缀转后缀、后缀求值 → 对称/三角矩阵压缩。

第二优先级：顺序栈与共享栈 → 链式队列 → 多维数组地址计算。

第三优先级：链栈 → 双端队列 → 括号匹配 → 递归 → 层次遍历 → 稀疏矩阵。

资料也明确把栈的出入栈过程和出栈序列合法性、队列操作与特征、顺序/链式实现、典型应用以及特殊矩阵压缩存储作为这一章需要重点掌握的部分。

如果只用一句话概括第 3 章：

栈考 LIFO 造成的顺序约束，队列考 FIFO 与循环下标，表达式考“栈模拟”，数组考“地址映射”，特殊矩阵考“数清前面已经存了多少元素”。

第 3 章 栈、队列和数组

On this page

第 3 章栈、队列和数组