第 3 章 栈和队列
栈 顺序栈（顺序存储结构） 存储结构：用一段连续存储单元（数组）存放栈元素 关键指针： 常见做法：top 指向当前栈顶元素位置，或指向栈顶元素的下一位置（两种约定均可，需配套一致） 上溢/下溢： 上溢（overflow）：栈满仍入栈（越界） 下溢（underflow）：栈空仍出栈（非法） 时间复杂度：入栈/出栈/取栈顶均为 O(1) 空间特性：需要预先分配容量 MaxSize，可能产生空间浪费或容量不足 共享栈 两个栈共享同一数组空间，分别从两端向中间增长 优点：在总空间固定时，能更充分利用存储空间；当一个栈空而另一个栈满的情况减少 满栈判定：两栈顶指针相遇（或满足相邻条件，依约定而定） 链栈（链式存储结构） 存储结构：用单链表实现，通常把表头作为栈顶以便 Push/Pop 在表头进行 栈顶指针：指向栈顶结点 优点： 不需要预先分配固定容量，理论上只受限于可用内存 入栈/出栈无需移动大量元素。 时间复杂度：入栈/出栈/取栈顶均为 O(1)；额外指针域带来一定存储开销 栈的典型应用与要点 括号匹配 思想：扫描表达式，遇到左括号入栈，遇到右括号则与栈顶左括号进行匹配并出栈 关键结论： 扫描结束时栈必须为空才匹配成功； 扫描中任何时刻出现“需要出栈但栈空”则匹配失败 表达式求值与表达式转换 三种常见表示： 中缀（运算符在中间，日常书写） 后缀/逆波兰式（RPN）（运算符在后，便于用栈求值） 前缀（运算符在前） 中缀 → 后缀（人为转换逻辑，核心是“运算符栈”处理优先级与括号）： 约定：运算符有优先级（如 * / 高于 + -），且多数二元运算符是左结合（同优先级从左到右计算）。括号用于改变优先级 准备： 一个输出序列（写下后缀表达式） 一个运算符栈（暂存运算符与左括号） 从左到右扫描中缀表达式的每个记号（操作数/运算符/括号）： 遇到操作数：直接追加到输出序列 遇到左括号 (：入运算符栈（它的作用是“隔断”，直到遇到对应右括号才弹出） 遇到右括号 )： 反复弹出栈顶运算符并追加到输出序列，直到弹出左括号 ( 为止（左括号本身不输出） 遇到运算符 op（如 + - * /）： 当运算符栈非空，且栈顶是运算符 topOp，并且： topOp 的优先级 高于 op，或 topOp 的优先级 等于 op 且 op 是左结合 则将 topOp 出栈并追加到输出序列；重复上述比较，直到不满足条件或遇到左括号 最后将当前运算符 op 入栈 扫描结束： 将运算符栈中剩余的运算符依次弹出并追加到输出序列（此时不应再有括号；若有通常说明表达式括号不匹配） 后缀表达式求值： 扫描：操作数入栈；遇运算符则弹出两个操作数计算后再入栈； 结束时栈顶即结果 出栈序列计数（卡特兰数） 问题表述（常见考点）：对 n 个元素按固定顺序 1,2,...,n 依次入栈（入栈顺序固定），在允许任意时刻出栈的前提下，一共有多少种不同的出栈序列？ 结论：合法出栈序列的种类数为第 n 个卡特兰数 Cn = (1 / (n + 1)) · C(2n, n) ...