考频地图
| 考点 | 考频 | 常见问法 | 必须会的动作 |
|---|---|---|---|
| 出栈序列合法性 | ★★★★☆ | “不可能的出栈序列是” | 模拟一遍 |
| 循环队列 | ★★★★★ | “队满条件”“元素个数” | (rear − front + M) % M |
| 双端队列 | ★★★☆☆ | “输入受限双端队列不能得到的序列” | 按限制模拟 |
| 表达式求值 | ★★★★☆ | “中缀转后缀”“栈中最多有几个运算符” | 画栈的变化表 |
| 特殊矩阵压缩 | ★★★★☆ | “a[i][j] 在一维数组中的下标” | 数“它前面有几个元素” |
栈
一、顺序栈:top 的两种约定
| 约定 | 初始 | 进栈 | 出栈 | 栈满 | 栈空 |
|---|---|---|---|---|---|
| top 指向栈顶元素 | top = −1 | S[++top] = x | x = S[top−−] | top == MaxSize − 1 | top == −1 |
| top 指向栈顶的下一个位置 | top = 0 | S[top++] = x | x = S[−−top] | top == MaxSize | top == 0 |
共享栈:两个栈共用一个数组,栈底分别在两端,向中间生长;top0 = −1、top1 = MaxSize 时为空,top1 − top0 == 1 时栈满。链栈:用单链表实现,进栈出栈都在表头进行,不存在栈满(除非内存耗尽)。
二、出栈序列
1, 2, …, n 依次进栈(中途可以随时出栈),可能的出栈序列个数是 卡特兰数:
口诀:某元素出栈时,比它先进栈、还在栈里的元素,必须按逆序出栈。如 4 先出,则 1、2、3 之后必须以 3、2、1 的相对顺序出栈。
队列与循环队列
一、为什么要“循环”
顺序队列中,入队 rear 后移,出队 front 后移。几轮之后 rear 到了数组末尾,可前面明明有空位——“假溢出”。把数组首尾相接,用 (rear + 1) % MaxSize 让指针绕回去,就是循环队列。
二、四个式子(front 指向队头元素,rear 指向队尾元素的下一个位置)
区分队空与队满的另外两种办法:① 增设 size 记录元素个数(size == 0 空,size == M 满);② 增设 tag,最近一次是入队则 tag = 1(此时 front == rear 表示满),是出队则 tag = 0(表示空)。若题目约定 rear 指向队尾元素本身,则初始 rear = M − 1,入队先移再存,公式要相应调整——考试时先看清约定。
三、链式队列与双端队列
链队列:带队头指针和队尾指针的单链表,入队在表尾、出队在表头;只有一个元素时出队要同时修改 rear。
- 算元素个数一定要 + M 再取模,否则 rear < front 时得到负数。
- 牺牲一个单元后,容量为 M 的循环队列最多只能存 M − 1 个元素。
- 队列的判满条件依赖 front、rear 的具体约定,题目给出的约定优先。
栈和队列的应用
一、括号匹配
从左到右扫描:遇到左括号进栈;遇到右括号,栈顶必须是与之配对的左括号,弹出;扫描结束时栈必须为空。三种失败:右括号多(栈空时来了右括号)、左括号多(结束时栈非空)、类型不配对。
二、表达式求值:中缀 → 后缀
后缀表达式(逆波兰式)中运算符写在两个操作数之后,不需要括号,计算机用一个栈就能从左到右求值。转换规则(手算口诀:按运算顺序给每个运算加括号,再把运算符移到对应右括号后面,去掉括号):
- 操作数:直接输出。
- 左括号:直接入栈。右括号:依次弹出栈中运算符直到左括号,括号丢弃。
- 运算符:先依次弹出栈顶优先级 ≥ 它的运算符(遇到左括号停),再把它入栈。
- 扫描完:弹出栈中剩余运算符。
后缀表达式求值:扫描到操作数入栈;扫描到运算符就弹出两个操作数(先弹出的是右操作数),计算后把结果入栈。中缀表达式直接求值需要两个栈(操作数栈 + 运算符栈)。
三、递归与栈;队列的应用
函数调用时,系统把返回地址、实参、局部变量压入递归工作栈;递归深度就是栈的最大深度,递归过深会栈溢出。递归可以用栈改写成非递归。
队列的应用:树的层序遍历、图的广度优先搜索、操作系统中的缓冲区(打印机数据缓冲)、FCFS 调度、页面置换 FIFO。
数组与特殊矩阵
一、二维数组的地址
二、特殊矩阵的压缩存储
对称矩阵、三角矩阵只存一半,三对角矩阵只存对角线附近 3n − 2 个元素。所有公式都只是在回答一个问题:按存储顺序,aᵢⱼ 前面一共有多少个元素?
三、稀疏矩阵
非零元素很少时,只存非零元素的 三元组 (行, 列, 值),再加上矩阵的行数、列数、非零元个数。压缩后失去随机存取特性。另一种存法是十字链表:每个非零元素同时在所在行和所在列的链表中,便于增删。
- 先看清:矩阵下标从 0 还是 1 开始,一维数组下标从 0 还是 1 开始,按行还是按列存。
- 上三角矩阵按行优先存储时,第 i 行有 n − i + 1 个元素,前 i − 1 行共 (i − 1)(2n − i + 2)/2 个。
- 稀疏矩阵的三元组表不能随机存取。
真题与自测
一、真题问法
问法 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. 为什么递归程序可能栈溢出?
每层递归调用都要在递归工作栈中保存返回地址、参数和局部变量,递归过深时栈空间耗尽。
三、考前速览
出栈序列数 = C(2n,n)/(n+1)。
队满:(rear+1)%M == front。
长度:(rear − front + M) % M。
压缩存储:数前面有几个元素。
① 后缀求值先弹出的是右操作数。
② 牺牲一个单元,最多存 M − 1 个。
③ 先确认矩阵和数组的下标起点。