首页/数据结构/第 3 章 栈、队列和数组
408 计算机学科专业基础 数据结构 第 3 章

栈、队列和数组
操作受限的线性表

选择题 2–3 道。必会:出栈序列判断、循环队列的判满与长度、中缀转后缀、特殊矩阵压缩存储的下标。

栈和队列都是“只许在固定位置进出”的线性表。限制越多,越容易实现、越不容易出错;也正是这种限制,让它们成为表达式求值、递归、广度优先搜索的基础工具。

5 个考点模块 3 个交互模拟器 2 张图
front rear (rear+1)%M== front 时满
00
复习策略

考频地图

★★★★☆ 高频 选择题
考点考频常见问法必须会的动作
出栈序列合法性★★★★☆“不可能的出栈序列是”模拟一遍
循环队列★★★★★“队满条件”“元素个数”(rear − front + M) % M
双端队列★★★☆☆“输入受限双端队列不能得到的序列”按限制模拟
表达式求值★★★★☆“中缀转后缀”“栈中最多有几个运算符”画栈的变化表
特殊矩阵压缩★★★★☆“a[i][j] 在一维数组中的下标”数“它前面有几个元素”
一句话:栈只在一端进出(后进先出),队列一端进另一端出(先进先出)。循环队列用取模让队尾“绕回来”,并牺牲一个单元区分队空和队满。压缩存储的下标公式只有一个思路:数出这个元素前面一共存了多少个元素。
01
3.1 · 高频

栈

★★★★☆ 高频 选择题
栈:后进先出 LIFO a1(栈底) a2 a3(栈顶) 进栈 push 出栈 pop 队列:先进先出 FIFO a1 a2 a3 队头出队 队尾入队
图 3-1 栈与队列都是操作受限的线性表。

一、顺序栈:top 的两种约定

约定初始进栈出栈栈满栈空
top 指向栈顶元素top = −1S[++top] = xx = S[top−−]top == MaxSize − 1top == −1
top 指向栈顶的下一个位置top = 0S[top++] = xx = S[−−top]top == MaxSizetop == 0

共享栈:两个栈共用一个数组,栈底分别在两端,向中间生长;top0 = −1、top1 = MaxSize 时为空,top1 − top0 == 1 时栈满。链栈:用单链表实现,进栈出栈都在表头进行,不存在栈满(除非内存耗尽)。

二、出栈序列

1, 2, …, n 依次进栈(中途可以随时出栈),可能的出栈序列个数是 卡特兰数:

N = C(2n, n) / (n + 1)  n = 3 → 5,n = 4 → 14,n = 5 → 42
#
判断 4 3 5 1 2 能否是 1~5 依次进栈得到的出栈序列
栈的状态
1
要先出 4:1、2、3、4 进栈,4 出
栈:1 2 3
2
要出 3:栈顶就是 3,出
栈:1 2
3
要出 5:5 进栈再出
栈:1 2
4
要出 1:栈顶是 2,1 被压在下面
不可能

口诀:某元素出栈时,比它先进栈、还在栈里的元素,必须按逆序出栈。如 4 先出,则 1、2、3 之后必须以 3、2、1 的相对顺序出栈。

02
3.2 · 必考

队列与循环队列

★★★★★ 必考 选择题

一、为什么要“循环”

顺序队列中,入队 rear 后移,出队 front 后移。几轮之后 rear 到了数组末尾,可前面明明有空位——“假溢出”。把数组首尾相接,用 (rear + 1) % MaxSize 让指针绕回去,就是循环队列。

二、四个式子(front 指向队头元素,rear 指向队尾元素的下一个位置)

初始: front = rear = 0 入队: Q[rear] = x; rear = (rear + 1) % M 出队: x = Q[front]; front = (front + 1) % M 队空: front == rear 队满: (rear + 1) % M == front ← 牺牲一个单元 元素个数: (rear − front + M) % M

区分队空与队满的另外两种办法:① 增设 size 记录元素个数(size == 0 空,size == M 满);② 增设 tag,最近一次是入队则 tag = 1(此时 front == rear 表示满),是出队则 tag = 0(表示空)。若题目约定 rear 指向队尾元素本身,则初始 rear = M − 1,入队先移再存,公式要相应调整——考试时先看清约定。

三、链式队列与双端队列

链队列:带队头指针和队尾指针的单链表,入队在表尾、出队在表头;只有一个元素时出队要同时修改 rear。

双端队列输入受限输出受限 两端都能进、都能出只能从一端进,两端可出两端可进,只能从一端出 绿 = 入队橙 = 出队
图 3-2 双端队列及两种受限形式。
#
例:输入序列 1 2 3 4,哪些输出序列做不到?(用程序穷举得到)
结论
1
普通栈
24 种排列中只有 14 种能得到
2
输入受限的双端队列(一端进,两端出)
4 2 1 3、4 2 3 1 不能得到
3
输出受限的双端队列(两端进,一端出)
4 1 3 2、4 2 3 1 不能得到
4
两种受限双端队列都不能得到
4 2 3 1
  • 算元素个数一定要 + M 再取模,否则 rear < front 时得到负数。
  • 牺牲一个单元后,容量为 M 的循环队列最多只能存 M − 1 个元素。
  • 队列的判满条件依赖 front、rear 的具体约定,题目给出的约定优先。
03
3.3 · 高频

栈和队列的应用

★★★★☆ 高频 选择题

一、括号匹配

从左到右扫描:遇到左括号进栈;遇到右括号,栈顶必须是与之配对的左括号,弹出;扫描结束时栈必须为空。三种失败:右括号多(栈空时来了右括号)、左括号多(结束时栈非空)、类型不配对。

二、表达式求值:中缀 → 后缀

后缀表达式(逆波兰式)中运算符写在两个操作数之后,不需要括号,计算机用一个栈就能从左到右求值。转换规则(手算口诀:按运算顺序给每个运算加括号,再把运算符移到对应右括号后面,去掉括号):

  1. 操作数:直接输出。
  2. 左括号:直接入栈。右括号:依次弹出栈中运算符直到左括号,括号丢弃。
  3. 运算符:先依次弹出栈顶优先级 ≥ 它的运算符(遇到左括号停),再把它入栈。
  4. 扫描完:弹出栈中剩余运算符。

后缀表达式求值:扫描到操作数入栈;扫描到运算符就弹出两个操作数(先弹出的是右操作数),计算后把结果入栈。中缀表达式直接求值需要两个栈(操作数栈 + 运算符栈)。

三、递归与栈;队列的应用

函数调用时,系统把返回地址、实参、局部变量压入递归工作栈;递归深度就是栈的最大深度,递归过深会栈溢出。递归可以用栈改写成非递归。
队列的应用:树的层序遍历、图的广度优先搜索、操作系统中的缓冲区(打印机数据缓冲)、FCFS 调度、页面置换 FIFO。

04
3.4 · 计算

数组与特殊矩阵

★★★★☆ 高频 计算选择

一、二维数组的地址

A[0..m−1][0..n−1],每个元素占 L 字节,首地址 LOC 行优先:LOC(aᵢⱼ) = LOC + (i × n + j) × L 列优先:LOC(aᵢⱼ) = LOC + (j × m + i) × L (下标从 1 开始时把 i、j 换成 i − 1、j − 1)

二、特殊矩阵的压缩存储

对称矩阵、三角矩阵只存一半,三对角矩阵只存对角线附近 3n − 2 个元素。所有公式都只是在回答一个问题:按存储顺序,aᵢⱼ 前面一共有多少个元素?

#
例:对称矩阵 A[1..10][1..10],按行优先存下三角到 B[0..54],求 a₃,₅ 的下标
计算
1
a₃,₅ 在上三角,由对称性等于 a₅,₃
转成 i = 5, j = 3
2
前 4 行共存了 1 + 2 + 3 + 4 个元素
10 个
3
第 5 行中 a₅,₃ 前面还有 a₅,₁、a₅,₂
2 个
4
前面共 12 个元素,B 从 0 开始
下标 12

三、稀疏矩阵

非零元素很少时,只存非零元素的 三元组 (行, 列, 值),再加上矩阵的行数、列数、非零元个数。压缩后失去随机存取特性。另一种存法是十字链表:每个非零元素同时在所在行和所在列的链表中,便于增删。

  • 先看清:矩阵下标从 0 还是 1 开始,一维数组下标从 0 还是 1 开始,按行还是按列存。
  • 上三角矩阵按行优先存储时,第 i 行有 n − i + 1 个元素,前 i − 1 行共 (i − 1)(2n − i + 2)/2 个。
  • 稀疏矩阵的三元组表不能随机存取。
05
实战

真题与自测

★★★★☆ 收口 选择题

一、真题问法

问法 1:“元素 a、b、c、d、e 依次进入初始为空的栈,若元素进栈后可停留、可出栈,直到所有元素都出栈,则所有可能的出栈序列中,以 d 开头的序列个数是?”→ d 先出则 a、b、c 在栈中且必须按 c、b、a 出,e 可以插在 d 之后的任意位置:4 种。

问法 2:“循环队列存储在数组 A[0..n−1],front 指向队头,rear 指向队尾元素。初始为空时 front、rear 应为?”→ 入队先 rear + 1 再存,所以初始 front = 0、rear = n − 1。

问法 3:“将中缀表达式 a+b−a*((c+d)/e−f)+g 转为后缀,运算符栈中最多同时有几个运算符?”→ 用上面的模拟器逐步看,最多 5 个。

二、折叠自测

1. 3 个元素依次进栈,可能的出栈序列有几种?

卡特兰数 C(6,3)/4 = 5 种。

2. 循环队列 M = 10,front = 7,rear = 3,元素个数?

(3 − 7 + 10) % 10 = 6。

3. 后缀表达式 3 4 2 * + 5 − 的值?

4×2 = 8,3+8 = 11,11−5 = 6。

4. 共享栈何时为满?

top1 − top0 == 1,即两个栈顶指针相邻。

5. 下三角矩阵 A[1..n][1..n] 按行优先存入 B[1..],aᵢⱼ(i ≥ j)的下标?

i(i − 1)/2 + j。

6. 为什么递归程序可能栈溢出?

每层递归调用都要在递归工作栈中保存返回地址、参数和局部变量,递归过深时栈空间耗尽。

三、考前速览

4 句话

出栈序列数 = C(2n,n)/(n+1)。
队满:(rear+1)%M == front。
长度:(rear − front + M) % M。
压缩存储:数前面有几个元素。

3 个易错

① 后缀求值先弹出的是右操作数。
② 牺牲一个单元,最多存 M − 1 个。
③ 先确认矩阵和数组的下标起点。