计算机 408 · 数据结构第 3 章「栈、队列和数组」学习笔记[!NOTE]栈和队列都是“限制了操作位置的线性表”栈后进先出队列先进先出。数组部分重点不是背代码而是从下标推导存储地址。学习进度能手写顺序栈、链栈和共享栈操作能掌握循环队列判空、判满及长度公式能完成中缀转后缀和后缀表达式求值能推导二维数组与特殊矩阵地址0. 全章地图受限线性表 ├─ 栈同一端进出 → LIFO → 递归、表达式、括号匹配 └─ 队列一端进另一端出 → FIFO → BFS、层序遍历、调度 数组固定维度的同类型元素 └─ 特殊矩阵压缩只存有规律或非零部分1. 栈1.1 顺序栈设top指向栈顶元素空栈时top-1判空top -1 判满top MaxSize-1 入栈data[top] x 出栈x data[top--]若教材让top指向“下一个可用位置”公式会不同必须先看初始化定义。1.2 共享栈两个栈共享一个数组栈 1 从低地址向上长栈 2 从高地址向下长。初始top1-1top2MaxSize 栈满top11 top2共享栈只在两个栈的总需求不超过数组容量时避免空间浪费。1.3 链栈通常用单链表表头作为栈顶入栈和出栈都是O(1)。带头结点与否会影响空栈判断。2. 队列2.1 循环队列牺牲一个单元设front指向队头元素rear指向下一可插入位置数组大小为MaxSize初始/空front rear 入队data[rear]x; rear(rear1)%MaxSize 出队xdata[front]; front(front1)%MaxSize 队满(rear1)%MaxSize front 队长(rear-frontMaxSize)%MaxSize 最大有效元素数MaxSize-12.2 其他判满方案增加sizesize0为空sizeMaxSize为满。增加tag最后一次操作为删除且frontrear表示空最后一次为插入且相等表示满。[!WARNING]循环队列题必须先写清front、rear指向什么以及是否牺牲一个单元不能跨约定套公式。2.3 链队列与双端队列链队列通常同时保存队头和队尾指针入队在尾部、出队在头部均为O(1)。双端队列允许两端插入和删除受限双端队列可能只允许一端插入或一端删除。常考“给定输入序列能否得到某输出序列”。3. 栈和队列的应用3.1 括号匹配遇左括号入栈遇右括号时检查栈顶是否为对应左括号并出栈。最终栈空且无中途失配才合法。3.2 中缀转后缀扫描表达式 1. 操作数直接输出 2. 左括号入栈 3. 右括号弹出直到左括号括号不输出 4. 运算符弹出栈顶中优先级更高或同级且左结合的运算符再入栈 5. 扫描结束依次弹出剩余运算符后缀求值操作数入栈遇运算符时先弹出右操作数b再弹出左操作数a计算a op b后入栈。3.3 递归每次递归调用都会保存参数、局部变量和返回地址形成调用栈。递归转非递归通常需要显式栈树的层序遍历和图的 BFS 使用队列。4. 数组与地址计算4.1 二维数组设数组A[m][n]每个元素占L字节基地址为LOC(A[0][0])行优先LOC(A[i][j]) base (i×nj)×L 列优先LOC(A[i][j]) base (j×mi)×L若下标从 1 开始先把i、j分别减 1。4.2 对称矩阵压缩n×n对称矩阵只需存下三角或上三角共n(n1)/2个元素。以按行存下三角、下标从 0 开始为例i ≥ jk i(i1)/2 j i j利用 A[i][j] A[j][i]交换 i、j 后计算4.3 三对角矩阵非零元素满足|i-j|≤1共约3n-2个。手算地址时建议逐行数前面已有多少个非零元素不要死背不同编号体系的公式。4.4 稀疏矩阵非零元素远少于总元素时可用三元组(row, col, value)或十字链表存储。压缩的收益取决于非零元素数量与额外下标开销。5. 408 高频考点补充出入栈序列判断某序列能否作为出栈序列按输入顺序模拟入栈若栈顶等于目标输出就不断弹出。全部匹配则可行。n个不同元素按固定顺序入栈的合法出栈序列数为 Catalan 数[C_n\frac{1}{n1}\binom{2n}{n}]复杂度操作顺序栈/队列链栈/链队列入栈、出栈O(1)O(1)入队、出队O(1)有首尾指针时O(1)查找内部元素O(n)O(n)6. 高频易错点易错点正确理解栈顶位置定义固定top可指栈顶或下一空位要看约定循环队列frontrear既空又满必须牺牲单元或增加标记加以区分后缀求值先弹出的是左操作数先弹出右操作数数组行优先的行数乘i应乘每行元素数即列数n压缩矩阵公式可以直接背下标起点、存上/下三角不同最好推导7. 轻量自测大小为 10、牺牲一个单元的循环队列最多存多少个元素front8、rear3、容量为 10 时队列长度是多少后缀表达式8 3 2 * -的值是多少A[5][8]按行优先存储A[3][4]前面有多少个元素下标从 0 开始展开答案9 个。(3-810)%105。8-(3×2)2。3×8428个。8. 最终记忆卡片栈 LIFO递归、表达式、括号匹配 队列 FIFOBFS、层序遍历、调度 循环队列判空、判满、长度公式必须服从同一约定 数组地址先数目标元素前面有多少元素再乘元素大小9. 加深理解栈、队列和数组的教材细节9.1. 循环队列的三套常见定义同一道题必须全程使用同一套定义方案空满队长牺牲一个单元frontrear(rear1)%Mfront(rear-frontM)%Msize计数size0sizeMsizetag标志frontrear tag0frontrear tag1按下标差修正若容量为M且牺牲一个单元真正可存M-1个元素。若题目问“入队后 rear 指向哪里”要先确认rear指向队尾元素还是下一空位教材中两种实现都出现过。9.2. 中缀转后缀的完整例子表达式A B * (C - D) - E。扫描 A 输出 A 扫描 运算符栈 扫描 B 输出 AB 扫描 * 栈 * 扫描 ( 栈 * ( 扫描 C、-、D 输出 ABCD遇 ) 弹出 - 扫描 - 弹出 *、按优先级再入 - 扫描 E 输出 ABCD*E 结束 弹出 -得到后缀式ABCD*-E-的关键不是死记而是维护“运算符栈中从栈底到栈顶优先级逐步升高遇括号除外”。结合性也会影响弹栈加减乘除通常左结合同级运算符应先弹出幂运算若题目规定右结合则同级时不能立即弹出。9.3. 递归为什么需要栈以阶乘为例调用fact(4)时系统依次保存fact(4)、fact(3)、fact(2)、fact(1)的返回地址和局部状态直到最深层返回再按后进先出的顺序计算。递归深度就是栈空间的重要来源。将递归改为非递归时显式栈必须保存递归函数原本会保存的状态例如当前结点、下一步应访问左子树还是右子树不能只保存结点指针。9.4. 数组地址公式的推导对A[i][j]按行优先存储先计算它前面完整经过了多少行再加上本行前面的元素前面完整的行i 行 × 每行 n 个元素 本行前面的元素j 个 线性下标i×nj 物理地址base (i×nj)×L三维数组A[a][b][c]按行优先时A[i][j][k]的线性下标为i×b×c j×c k。遇到多维地址题先数“最右边下标变化最快”的规则再逐层展开。9.5. 特殊矩阵压缩的推导方法不要背一套公式应对所有题。以按行存储下三角为例A[i][j] (ij)前面有第 0 行有 1 个第 1 行有 2 个...第 i-1 行有 i 个 总数 12...i i(i1)/2 再加本行前面的 j 个所以ki(i1)/2j。若存上三角、下标从 1 开始或使用列优先只需重新数前面元素数量。