栈、队列和数组

本节导读

栈和队列是操作受限的线性表，数组是线性表的推广。大纲在这一章列了基本概念、顺序存储结构、链式存储结构、多维数组的存储、特殊矩阵的压缩存储和应用六项。

这一节的计算类题目多：出栈序列的判断与计数、循环队列的长度与判满、表达式转换与求值、数组元素地址、压缩存储的下标换算。学完你应该能把每一类都按固定步骤做出来，并且每次先看清题目对下标起点、指针含义的约定。

栈

存储与基本操作

栈只允许在一端（栈顶）插入和删除，后进先出（LIFO）。顺序栈用数组加栈顶指针 top 实现，top 有两种约定，题目会写明是哪一种：

约定	初值（空栈）	进栈	出栈	栈满
top 指向栈顶元素	top = −1	先 top 加 1，再存入	先取出，再 top 减 1	top = MaxSize − 1
top 指向栈顶元素的下一个位置	top = 0	先存入，再 top 加 1	先 top 减 1，再取出	top = MaxSize

两个栈共享一个数组时，把栈底分别放在数组两端，向中间生长：top0 初值 −1、top1 初值 MaxSize，两个栈顶相邻（top1 − top0 = 1）时栈满。链栈用单链表实现，栈顶在表头，进栈出栈都是 $O(1)$O(1)，按需申请结点，一般不考虑栈满。

出栈序列

入栈顺序固定、出栈时机任意时，判断一个序列能不能得到，最稳的办法是模拟：按序列逐个要元素，要的元素还没进栈就先把它之前的都压进去；要的元素既不在栈顶、又已经进过栈，序列就不可能。

n 个不同元素依次进栈，能得到的不同出栈序列个数是卡特兰数：

$$\frac{1}{n+1}\mathrm{C}_{2n}^{n}$$n+11​C2nn​

比如 n = 3 时是 5 种：只有「3, 1, 2」得不到。

队列

队列只允许在队尾插入、队头删除，先进先出（FIFO）。顺序队列会出现「假溢出」（前面有空位、rear 却到了数组末尾），所以实际用循环队列。下面约定 front 指向队头元素，rear 指向队尾元素的下一个位置，数组长度为 M：

操作	写法
入队	Q[rear] = x，然后 rear = (rear + 1) mod M
出队	x = Q[front]，然后 front = (front + 1) mod M
队空	front == rear
队满（牺牲一个单元）	(rear + 1) mod M == front
队列长度	(rear − front + M) mod M

区分队空和队满还有两种办法：另设元素个数 size，或设标志 tag 记录最近一次是入队还是出队，这两种办法不浪费单元。链队列一般带头结点，front 指向头结点、rear 指向尾结点，front == rear 时队空。双端队列两端都能进出；只允许一端插入的叫输入受限的双端队列，只允许一端删除的叫输出受限的双端队列。

栈和队列的应用

栈的应用：括号匹配（左括号进栈，遇到右括号与栈顶比对）；表达式求值；递归（系统栈保存每层调用的参数、局部变量和返回地址，递归改非递归时就要自己用栈）。

中缀表达式转后缀表达式，从左到右扫描，按下表处理：

读到的符号	处理
操作数	直接输出
左括号	进栈
右括号	依次弹出并输出，直到弹出左括号（括号不输出）
运算符	先弹出并输出栈中优先级不低于它的运算符（遇到左括号停），再把它进栈
扫描结束	栈中剩下的运算符依次弹出并输出

后缀表达式求值：操作数进栈；遇到运算符就弹出两个操作数计算，结果再进栈，先弹出的是右操作数。

队列的应用：树的层次遍历、图的广度优先搜索、打印机与键盘这类缓冲区、操作系统里的 FIFO 页面置换。

数组和特殊矩阵

多维数组的存储

二维数组有行优先和列优先两种存储方式。设数组 m 行 n 列、下标都从 0 起、每个元素占 L 个单元：

行优先：

$$\mathrm{LOC}(a_{ij}) = \mathrm{LOC}(a_{00}) + (i \times n + j) \times L$$LOC(aij​)=LOC(a00​)+(i×n+j)×L

列优先：

$$\mathrm{LOC}(a_{ij}) = \mathrm{LOC}(a_{00}) + (j \times m + i) \times L$$LOC(aij​)=LOC(a00​)+(j×m+i)×L

公式的本质是「前面有几个元素」。例如 A[0..4][0..5] 按行优先存储、每个元素 2 个单元、首地址 200，则 $a_{32}$a32​ 前面有 $3 \times 6 + 2 = 20$3×6+2=20 个元素，地址为 240。下标从 1 起时，先把行号、列号各减 1 再代入。

特殊矩阵的压缩存储

矩阵	存哪些元素	下标换算（矩阵下标从 1 起，一维数组 B 下标从 0 起，按行优先）
n 阶对称矩阵	下三角（含对角线），共 $\dfrac{n(n+1)}{2}$2n(n+1)​ 个	$i \ge j$i≥j 时 $k = \dfrac{i(i-1)}{2} + j - 1$k=2i(i−1)​+j−1；$i \lt j$i<j 时用 $a_{ji}$aji​
下三角矩阵	下三角，上三角的常数 c 另存一个	同对称矩阵；c 存在 $B\left[\dfrac{n(n+1)}{2}\right]$B[2n(n+1)​]
三对角矩阵	主对角线及上下各一条，共 $3n - 2$3n−2 个	$k = 2i + j - 3$k=2i+j−3

例如对称矩阵的 $a_{63}$a63​ 存在 $k = \dfrac{6 \times 5}{2} + 3 - 1 = 17$k=26×5​+3−1=17 处。稀疏矩阵非零元素很少，用三元组（行号，列号，值）或十字链表存储，压缩后就不能随机存取了。

易错提醒

• ❌ 循环队列 rear == front 就是队满。✅ 牺牲一个单元的方案里，rear == front 是队空，队满是 (rear + 1) mod M == front。因为两种情况都用同一个条件就区分不开。

• ❌ 后缀表达式求值时，先弹出的是左操作数。✅ 先弹出的是右操作数。因为右操作数后进栈，在栈顶。

• ❌ 对称矩阵里 $i \lt j$i<j 的元素也直接代入下三角的下标公式。✅ 先交换行号和列号，按 $a_{ji}$aji​ 计算。因为只存了下三角，上三角的元素要靠对称性找到它的「替身」。

• ❌ 链栈和顺序栈一样，每次进栈前都要判栈满。✅ 链栈按需申请结点，一般不考虑栈满，只在内存耗尽时失败。因为它没有预先固定的容量。

• ❌ 下标从 1 起的数组也直接套下标从 0 起的地址公式。✅ 先把行号、列号换算成「前面有几行、几列」。因为公式数的是排在它前面的元素个数。

例题精讲

例题 1（单项选择）

元素 1、2、3、4、5 依次进栈，出栈时机任意。下列序列中不可能是出栈序列的是（　）

A. 2, 1, 4, 3, 5　　B. 4, 3, 5, 1, 2　　C. 1, 2, 3, 4, 5　　D. 3, 4, 2, 5, 1

答案：B

解析：B 中 4 出栈前 1、2、3 已进栈；4、3 出栈后栈里自底向上是 1、2；5 进栈又出栈后，栈顶是 2，下一个只能是 2，不能是 1，所以 B 不可能。A、C、D 都能模拟出来，例如 D：1、2、3 进栈，3 出；4 进 4 出；2 出；5 进 5 出；1 出。

例题 2（计算）

循环队列存放在 Q[0..9] 中，front 指向队头元素，rear 指向队尾元素的下一个位置。当前 front = 7、rear = 3，队列中有几个元素？再入队 2 个、出队 3 个之后，front 和 rear 各是多少？

答题要点示范：长度 $(3 - 7 + 10) \bmod 10 = 6$(3−7+10)mod10=6 个。入队 2 个：rear = (3 + 2) mod 10 = 5；出队 3 个：front = (7 + 3) mod 10 = 0。此时长度 5 − 0 = 5，与 6 + 2 − 3 = 5 对得上。

例题 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 −
/	+ /	a b c d − *
e	+ /	a b c d − * e

扫描结束，依次弹出 / 和 +，后缀表达式为 a b c d − * e / +。

点评：读到 / 时，栈顶的 * 与它优先级相同，要先弹出 *，所以乘法在前，这正是「同级运算从左到右」。

本节小结

• 顺序栈的 top 有两种约定，进栈、出栈、栈满的写法跟着约定走；共享栈两栈顶相邻时满；链栈一般不考虑栈满。
• 出栈序列用模拟法判断；n 个元素的出栈序列有 $\dfrac{1}{n+1}\mathrm{C}_{2n}^{n}$n+11​C2nn​ 种。
• 循环队列：队空 front == rear，队满 (rear + 1) mod M == front，长度 (rear − front + M) mod M。
• 中缀转后缀靠运算符栈，后缀求值靠操作数栈，先弹出的是右操作数；层次遍历、广度优先搜索用队列。
• 数组地址数「前面有几个元素」；对称矩阵 $k = \dfrac{i(i-1)}{2} + j - 1$k=2i(i−1)​+j−1，三对角矩阵 $k = 2i + j - 3$k=2i+j−3，都要先看清下标起点。