栈和队列

线性表的核心特征是元素之间存在前驱后继关系，插入和删除在合法位置上都可进行。栈和队列没有放弃这种关系，只是把插入、删除的位置收窄为一端或两端。收窄之后，可观察的状态变少，操作序列的规律变强，许多原本需要额外记录的问题可以直接由结构本身表达。本章先统一位序、栈顶和队头队尾的约定，再讨论顺序与链式两种实现，最后集中分析括号匹配、表达式求值、递归回溯和队列应用。

3.1 受限线性表：把操作位置固定下来

对应课件第 4—6 页。

线性表是 n（n ≥ 0）个同类型元素组成的有序序列。一般线性表允许在任意合法位置插入和删除，因此同一个表中可以出现“在中间插入”“删除末尾”“按下标读取”等差别很大的操作。栈把插入和删除都限制在表的一端，队列把插入限制在一端、删除限制在另一端。三者的区别不在元素关系，而在允许的操作集合。

限制操作位置带来三方面好处。第一，状态容易刻画：任意时刻只需记录栈顶或队头队尾的位置，不必描述整个表中哪些位置被改动。第二，接口更窄：调用者只能通过少数操作改变结构，越界和非法访问更容易在实现内部拦住。第三，端点操作可以做到常数时间：在顺序存储上移动一个下标，或在链式存储上改动少数指针，就能完成一次插入或删除。也正因如此，栈和队列常被用作算法中的“状态容器”，而不是通用的数据存储。

需要特别区分位序和数组下标。ADT 说“第 1 个元素”时指的是位序 1；若用数组存放，它位于下标 0。栈顶元素的位序随 Push、Pop 变化，而 pTop 始终指向“下一个可写位置”。把这两套编号混用，是后文空栈判断、元素个数计算和循环队列取模错误的常见来源。

3.2 栈的定义、术语与 ADT

对应课件第 7—12 页。

栈是仅允许在表的一端进行插入和删除的线性表。允许操作的一端称为栈顶，另一端称为栈底，栈底固定不动。不含元素的栈称为空栈。若元素按 a₁、a₂、…、a_n 的顺序依次进栈，则 a₁ 在栈底、a_n 在栈顶；出栈时只能先弹出 a_n，再弹出 a_n−1，直到 a₁。这种“最后进栈的元素最先出栈”的规则称为后进先出（LIFO）。

栈顶和栈底是逻辑概念，与元素在内存中的地址高低没有必然关系。顺序栈把栈底放在数组低端、栈顶向高端增长，这只是实现选择；链栈把栈顶放在链表头部，也只是让 Push/Pop 落在便于操作的链端。结点的动态分配地址没有单调保证，不能由链接次序推断地址大小。判断一个结构是不是栈，看的是操作规则，而不是内存布局。

GetTop 与 Pop 必须分开：前者只读，后者删除。若只有 Pop，想查看栈顶就得先弹出再压回，既多一次操作，也可能在两步之间改变栈；若只有 GetTop，又无法删除元素。空栈时两者都应返回错误而不改变结构，调用者应先判空。这是“操作受限”的另一层含义：不是操作越少越好，而是提供的每个操作都必须有明确的适用条件和后果。

3.3 出栈序列的合法性与 Catalan 数

对应课件第 13 页。

给定进栈顺序 1、2、3，每个元素进栈一次、出栈一次，进出可以任意交错。问：可能的出栈序列有哪些？课件例 3.1 给出五个合法序列：123、132、213、231、321；312 不可能。以 312 为例，若第一个输出是 3，说明 1、2、3 都已进栈，此时栈从底到顶为 1、2、3，3 弹出后栈顶是 2，只能先输出 2 再输出 1，无法先输出 1。

判断一个序列是否合法，不必枚举所有进出方案，可以按输入顺序模拟：依次读入待进栈元素并压栈，只要栈顶等于输出序列的当前元素就持续弹出；若某个输出元素尚未进栈，则继续压入后续输入；输入耗尽后仍不能满足输出，则序列非法。该判定只扫描一遍，时间 O(n)，空间 O(n)。要特别注意，这里的结论以“进栈顺序固定、每个元素只进一次只出一次、不允许其他操作”为前提；若允许重复进栈或中途清空，计数规则会改变。

合法出栈序列的数目是第 n 个 Catalan 数：

n = 1、2、3、4、5 时依次为 1、2、5、14、42。n = 3 正好是例 3.1 的五个序列。Catalan 数还出现在括号匹配方案数、n 个结点构成的二叉树形态数等问题中；这些数量相同并不是巧合，而是它们都对应同一种“压栈—弹栈”结构。

3.4 顺序栈的存储表示与生命周期

对应课件第 14—19 页。

顺序栈用一段连续存储保存元素，并设置栈底指针、栈顶指针和当前容量。下面的结构沿用课件的命名，但把容量单位和指针关系写清楚：pTop 始终指向栈顶元素之后的第一个空位，而不是栈顶元素本身。

#define STACK_INIT_SIZE 256
#define STACK_INCREMENT 128

typedef char ElemType;

typedef struct SeqStack {
    ElemType *pBase;    /* 栈底，等价于数组下标 0 的地址 */
    ElemType *pTop;     /* 栈顶元素的下一个空位 */
    int stacksize;      /* 当前已分配的容量（可容纳的元素个数） */
} SeqStack;

在这样的约定下，空栈是 pTop == pBase；元素个数是 pTop - pBase；栈顶元素是 *(pTop - 1)，其位序为 pTop - pBase，数组下标为 pTop - pBase - 1；进栈前若 pTop - pBase >= stacksize，说明已无空位，需要扩容。容量为 stacksize 时可以存放 stacksize 个元素，这一点与循环队列“牺牲一个单元”的约定不同，不能混用。

初始化、销毁与清空是三个不同层次的操作。初始化分配存储并把两个指针置为同一位置；销毁释放存储并把指针置空，之后必须重新初始化才能使用；清空只把 pTop 拉回 pBase，保留已经分配的容量，便于之后继续使用。表格中的“空间状态”一列常被忽略，但它决定了操作之后能否继续 Push。

边界情况需要明确：malloc 失败时课件用 exit(OVERFLOW) 终止程序，这是一个约定；工程代码更常返回错误码交给调用者处理。销毁之后继续访问属于未定义行为，不是“空栈”。清空不会把旧元素清零，旧值仍留在内存中，只是不在有效范围内；若数据敏感，应在清空或销毁前覆盖。判断“栈是否已初始化”不能只看 pTop，因为未初始化的指针可能恰好非空。

3.5 顺序栈的进栈、出栈与取栈顶

对应课件第 20—26 页。

进栈先检查容量，必要时扩容，然后把元素写到 pTop 指向的位置，最后让 pTop 后移一格。写入和移动的顺序不能颠倒：若先移动指针再写入，新元素就落到了错误的位置，原空位未被使用。

Status Push(SeqStack *S, ElemType e) {
    if (S->pTop - S->pBase >= S->stacksize) {          /* 已满，扩容 */
        int oldCount = S->pTop - S->pBase;
        ElemType *newBase = (ElemType *)realloc(
            S->pBase, (S->stacksize + STACK_INCREMENT) * sizeof(ElemType));
        if (newBase == NULL) return ERROR;             /* 课件写作 exit(OVERFLOW) */
        S->pBase = newBase;
        S->pTop = newBase + oldCount;                  /* 重新计算，不能沿用旧地址 */
        S->stacksize += STACK_INCREMENT;
    }
    *S->pTop = e;
    S->pTop++;
    return OK;
}

扩容后必须用新基址重算 pTop。如果直接保留扩容前的 pTop，它指向的已是被释放的旧内存，后续写入就是悬空指针访问。上面的写法先保存旧元素个数，再修改 pBase，最后用 newBase + oldCount 恢复栈顶位置，避免了这一错误。

课件把进栈的时间复杂度记为 O(1)，严格说这是一个摊还结论，成立条件与扩容策略有关。若每次只增加固定的 STACK_INCREMENT 个单元，从空栈连续进栈 n 个元素，第 k 次扩容要复制约 256 + 128(k−1) 个元素，扩容次数约为 n/128，复制总量随 n 平方增长，摊还到每次进栈是 O(n) 而不是 O(1)。若采用按比例扩容（如容量翻倍），复制总量不超过 2n，摊还代价才是 O(1)，单次最坏仍是 O(n)。因此“Push 是 O(1)”应理解为：不触发扩容时 O(1)，触发时单次 O(n)，在按比例扩容的假设下摊还 O(1)。

Status Pop(SeqStack *S, ElemType *e) {
    if (S->pTop == S->pBase) return ERROR;   /* 空栈不可出栈 */
    *e = *(S->pTop - 1);                     /* 先取栈顶元素 */
    S->pTop--;                               /* 再逻辑删除 */
    return OK;
}

Status GetTop(SeqStack S, ElemType *e) {
    if (S.pTop == S.pBase) return ERROR;
    *e = *(S.pTop - 1);                      /* 只读，不改变栈 */
    return OK;
}

Pop 先把栈顶元素读入 e，再移动指针；也可以先 pTop-- 再读 *pTop，两种写法等价，都先取得原栈顶元素、再更新栈顶位置。GetTop 只读不移动。弹出之后元素值仍留在原内存单元，但已经不属于栈的有效范围，下一次 Push 会覆盖它。不要依赖“弹出后还能读到旧值”，也不要为了“安全”在 Pop 中清零整个单元而增加不必要的写操作。

3.6 链式栈、双端栈与实现选型

对应课件第 27—35 页。

链式栈把栈顶放在单链表头部，进栈和出栈都只改动头结点之后的第一个位置，因此都是 O(1)。本讲统一采用带头结点的约定：S 指向头结点，头结点不保存元素，栈顶元素是 S->next；空栈为 S->next == NULL。若去掉头结点，空栈和非空栈的首结点插入删除要分开处理，代码分支会变多，这正是附加头结点的作用。

typedef char ElemType;

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkStack;

Status Push(LinkStack S, ElemType e) {       /* S 指向头结点 */
    LNode *p = (LNode *)malloc(sizeof(LNode));
    if (p == NULL) return ERROR;
    p->data = e;
    p->next = S->next;                       /* 先接后继 */
    S->next = p;                             /* 再改头结点指针 */
    return OK;
}

Status Pop(LinkStack S, ElemType *e) {
    if (S->next == NULL) return ERROR;       /* 空栈 */
    LNode *p = S->next;                      /* p 为栈顶结点 */
    *e = p->data;
    S->next = p->next;                       /* 摘下栈顶 */
    free(p);
    return OK;
}

链栈没有“栈满”状态，只要内存分配成功就能继续进栈；代价是每个元素多一个指针域，以及 malloc、free 的分配器开销。因此“链栈插入删除 O(1)”以单次分配和释放为常数时间为前提；真实系统中分配器可能触发系统调用，常数因子比顺序栈大。

双端栈让两个栈共享一段数组：栈 1 的栈底在左端、栈 2 的栈底在右端，两个栈顶相向增长。约定栈 1 栈顶元素下标为 top1（空为 −1），栈 2 栈顶元素下标为 top2（空为 MAXSIZE），则栈 1 空是 top1 == -1，栈 2 空是 top2 == MAXSIZE，共享空间满的条件是 top1 + 1 == top2。这样两个栈可以互相调剂空闲单元，比给每个栈固定分配一半容量更灵活，但只适合恰好两个栈、且总需求有上限的场景。

需要把这里的 top1、top2 与 3.4—3.5 的 pTop 区分开：top1、top2 保存的是栈顶元素的下标，而顺序栈的 pTop 指向下一个空位，两者相差 1，空、满和计数公式不能互相套用。按本节约定，栈 1 的元素个数是 top1 + 1，栈 2 的元素个数是 MAXSIZE − top2；共享空间满时 top1 + 1 == top2，此时两栈元素合计恰好 MAXSIZE 个。若要把双端栈改成 pTop 式约定，必须整体重写空、满和计数三组条件，不能只换一个符号。

表中的“Push 摊还 O(1)”以按比例扩容（例如容量不足时翻倍）为前提：一次扩容搬移 O(n) 个元素，但可支撑随后 O(n) 次追加，均摊到每次是 O(1)。若采用固定增量扩容，每次搬移后只能支撑常数次追加，均摊代价不会随规模摊薄，不能套用这一结论；第 3.5 节已按此区分。

3.7 栈的应用（一）：逆序输出、进制转换与回文

对应课件第 36—40 页。

课件把栈的典型应用归为四类：逆序输出、最近匹配、递归回溯和系统调用。前三类在本章展开。逆序输出是一类最直接的模式：如果输出要求与读入顺序相反，就把读入的元素依次进栈，再逐个出栈；后进先出的规则会把顺序自然翻转，不需要额外的逆序数组或两次扫描。

进制转换是逆序输出的典型例子。把十进制数反复除以基数，第一次得到的余数是结果的最低位，最后一次得到的余数是最高位；用一个栈保存各次余数，再依次弹出，就得到从高位到低位的正确顺序。下面以十进制转八进制为例，ElemType 换为整数类型。

void Convert(int n, int base) {
    SeqStack S;
    InitStack(&S);
    if (n == 0) { printf("0"); return; }      /* 边界：0 不能进入循环 */
    while (n > 0) {
        Push(&S, n % base);                    /* 低位先入栈 */
        n = n / base;
    }
    while (!StackEmpty(S)) {
        ElemType digit;
        Pop(&S, &digit);
        printf("%d", digit);                   /* 高位先出栈 */
    }
    DestroyStack(&S);
}

以 1348 转八进制为例：1348 ÷ 8 余 4、商 168；168 ÷ 8 余 0、商 21；21 ÷ 8 余 5、商 2；2 ÷ 8 余 2、商 0。余数依次为 4、0、5、2，压栈后从栈顶弹出得到 2、5、0、4，即 (2504)₈。时间与栈空间都是 O(log_base n)，因为位数随对数增长；负数需要先单独处理符号，基数应限制在 2 到 36 之间，超出范围要有明确错误，而不是产生无意义的数字。

回文判定是另一个逆序模式。若字符串正读和反读相同，则把它全部压栈后再逐个弹出，弹出的顺序正好是反读顺序，逐位与原文比较即可。课件例 3.2 举了 abcba、12321、上海自来水来自海上、racecar 等例子；第 39 页用六步追踪展示了 abcba 的压栈、弹栈和逐位比较过程。

Status IsPalindrome(const char *s, int n) {
    SeqStack S;
    InitStack(&S);
    for (int i = 0; i < n; i++) Push(&S, s[i]);
    for (int i = 0; i < n; i++) {
        ElemType c;
        Pop(&S, &c);
        if (c != s[i]) {                       /* 提前失败也要释放资源 */
            DestroyStack(&S);
            return ERROR;
        }
    }
    DestroyStack(&S);
    return OK;
}

该算法进栈 n 次、出栈 n 次，时间 O(n)，额外空间 O(n)。可以只把前一半字符压栈，再从中间向外比较，空间降为 O(n/2)，但在渐进意义下仍是 O(n)；若改用双指针从两端向中间比较，额外空间可降到 O(1)，代价是不再使用栈。课件第 40 页也提示了这两种改进方向。还有一个实现边界：若 ElemType 是 char，栈中保存的是字节而不是字符，中文等多字节字符会被拆开比较；处理 Unicode 文本时应按字符编码单元或码点处理，不能直接套用单字节版本。

3.8 栈的应用（二）：括号匹配

对应课件第 41—43 页。

括号匹配要判断三种错误：类型不匹配，如 ([)]；缺少右括号，如 ((；多余右括号，如 ())。只统计左右括号数量是不够的，([)] 的数量相等但嵌套关系错误。正确的结构要求每个右括号与“最近一个尚未匹配的左括号”配对，这正好是后进先出的规则：左括号遇到时压栈，右括号遇到时与栈顶比较并弹出。

算法结束时必须再检查一次栈是否为空：如果还有左括号，说明缺少右括号；如果右括号到来时栈已空，说明右括号多余；如果栈顶左括号与当前右括号类型不同，说明嵌套或类型错误。这三种失败分别对应三道检查，缺一不可。

int IsMatched(char left, char right) {
    return (left == '(' && right == ')')
        || (left == '[' && right == ']')
        || (left == '{' && right == '}');
}

Status CheckParenMatching(const char *s) {
    SeqStack S;
    InitStack(&S);
    for (int i = 0; s[i] != '\0'; i++) {
        char ch = s[i];
        if (ch == '(' || ch == '[' || ch == '{') {
            Push(&S, ch);
        } else if (ch == ')' || ch == ']' || ch == '}') {
            if (StackEmpty(S)) {                /* 多余右括号 */
                DestroyStack(&S);
                return ERROR;
            }
            char left;
            Pop(&S, &left);
            if (!IsMatched(left, ch)) {         /* 类型不匹配 */
                DestroyStack(&S);
                return ERROR;
            }
        }
    }
    Status result = StackEmpty(S) ? OK : ERROR; /* 结束仍非空：缺右括号 */
    DestroyStack(&S);
    return result;
}

时间 O(n)，因为每个字符最多进栈一次、出栈一次；最坏空间 O(n)，出现在全部为左括号的情况，平均空间与最大嵌套深度成正比。空串按“没有不匹配括号”处理为成功；如果业务要求必须至少出现一对括号，应在调用前另加长度或计数检查，不能把“空串成功”当作错误。

匹配器只识别三种括号；字母、数字、空白等一般字符在循环中直接跳过（例如 a(b)c 判定为成功），字符串字面量、注释、转义字符和标签属性都不属于本实验的语法。若把它用于真实源码，应先做词法分析，把字符串和注释里的括号排除；否则 "(" 这样的字符内容会被误当成左括号，得到与程序语义无关的结论。

该算法可以直接扩展到 HTML/XML 标签匹配：把“字符”换成“标签名字符串”，遇到开始标签压栈，遇到结束标签与栈顶名字比较，自闭合标签按规则单独处理。此时还需要处理属性、注释和大小写等语法细节，已经超出“括号匹配”的范围；课程中的三种括号版本是它的最小模型。

3.9 栈的应用（三）：中缀表达式求值

对应课件第 44—47 页。

中缀表达式把运算符写在两个操作数之间，如 3+4*2-(1+1)#（# 是结束标志）。求值必须同时处理三件事：乘除优先于加减；同级运算符从左到右结合；括号内的子表达式优先计算。只用一个操作数栈无法决定“现在能不能算”，因为 3+4 之后遇到 * 时，+ 必须等待右边的乘法完成。解决办法是再用一个运算符栈，暂存尚未能执行的运算符。

课件采用双栈方案：OPND 存放操作数或运算结果，OPTR 存放运算符，并先在 OPTR 中压入 # 作为栈底哨兵。每读到一个运算符 θ₂，就与 OPTR 栈顶 θ₁ 比较优先级：θ₁ 高于 θ₂ 时，先弹出 θ₁ 并执行一次运算；θ₁ 低于 θ₂ 时，把 θ₂ 压栈；相等时脱括号或结束。优先级表如下，行是栈顶运算符，列是当前运算符。

表中的“>”表示先算栈顶运算，“<”表示把当前运算符压栈，“=”表示脱去一对括号或遇到结束标志。相同优先级的 + 与 − 之间、* 与 / 之间都记为“>”，这就是左结合的体现：先出现的同级运算符先执行。括号的优先级不是数值大小，而是阻止运算符提前执行：( 在栈内时，任何运算符都不能越过它；( 与 ) 相遇才脱括号。

以 3+4*2-(1+1)# 为例，逐步执行如下。每一步中，OPTR 自底向顶列出，OPND 自底向顶列出。

执行一次二元运算时，先从 OPND 弹出右操作数，再弹出左操作数，计算“左 op 右”。顺序不能反，否则减法和除法的结果会错。遇到 ) 时，反复弹出并执行运算符，直到遇到 (，然后把 ( 弹出但不计算。读到结束标志 # 时，先把 OPTR 中剩余运算符依次弹出归约，直到栈中只剩栈底的 #；结束条件必须同时满足三条：输入已经全部消费完、OPTR 只余哨兵 #、OPND 恰好剩一个值。三者都成立时，这个值就是求值结果；否则说明表达式缺少运算符、括号不匹配或操作数个数不对，应报错。例如 3# 是合法的单操作数表达式：读入 # 时 OPTR 只有哨兵 #、OPND 只有 3，直接返回 3；3+4# 则先归约 + 得到 7，再遇哨兵结束。若归约到栈底 # 时还有未处理内容，或结束时 OPND 不是恰好一个值，同样报错。

课件算法假设操作数是非负整数，3+4*2-(1+1)# 这样的输入是它的设计范围。本讲义把输入范围固定为：非负整数字面量（多位数要连续读取，不能逐字符当数字）、二元运算符 + − * /、圆括号和结束标志 #；不接受一元正负号，-3+5# 应明确报错，而不是按“0−3+5”静默计算；空白可跳过；非法字符、左右括号不配对、空表达式、除数为 0 都返回错误。运算结果允许是有限小数：5/2 = 2.5，1/2 + 1/2 = 1。若用浮点数实现，0.1 + 0.2 这类十进制小数可能得到 0.30000000000000004，报告中应按精度格式化或说明这是浮点近似，不能把二进制浮点数当作精确十进制数。若坚持整数运算，则必须明确除法是向零截断还是向下取整，并说明 / 只做整除；这与“结果可为小数”的口径二选一，不能在同一实验里混用。

3.10 栈的应用（四）：后缀表达式与递归的显式栈实现

对应课件第 48—50 页。

后缀表达式把运算符写在两个操作数之后，例如中缀式 3+4*2-(1+1) 对应的后缀式为 3 4 2 * + 1 1 + -（课件第 44 页给出该例）。后缀式不需要括号，也不需要在读到运算符时比较优先级：从左到右扫描，遇到操作数就压栈，遇到运算符就弹出两个操作数计算，再把结果压栈。读到 * 时栈中自底向顶是 3、4、2，先弹出 2 作为右操作数、再弹出 4 作为左操作数，算 4*2=8；读到 + 时弹出 8 和 3，算 3+8=11；括号部分 1 1 + 算得 2；最后 - 弹出 2 和 11，算 11−2=9。

Status EvalPostfix(const char *expr, ElemType *result) {
    SeqStack S;
    InitStack(&S);
    const char *p = expr;
    while (*p != '\0') {
        if (*p == ' ') { p++; continue; }
        if (isdigit((unsigned char)*p)) {
            ElemType num = 0;
            while (isdigit((unsigned char)*p)) {
                num = num * 10 + (*p - '0');
                p++;
            }
            Push(&S, num);
        } else {
            ElemType right, left;
            if (StackEmpty(S)) return ERROR;
            Pop(&S, &right);
            if (StackEmpty(S)) return ERROR;
            Pop(&S, &left);
            ElemType value;
            switch (*p) {
                case '+': value = left + right; break;
                case '-': value = left - right; break;
                case '*': value = left * right; break;
                case '/':
                    if (right == 0) return ERROR;   /* 除零 */
                    value = left / right; break;
                default: return ERROR;             /* 非法字符 */
            }
            Push(&S, value);
            p++;
        }
    }
    if (StackLength(S) != 1) return ERROR;          /* 多余操作数或缺少操作数 */
    Pop(&S, result);
    DestroyStack(&S);
    return OK;
}

这段代码为突出求值逻辑，省略了 InitStack、Push 的返回值检查，也没有统一的失败清理；实际实现应检查初始化和压栈是否成功，并让所有错误分支跳到统一的 cleanup 出口执行 DestroyStack，避免提前 return 造成资源泄漏。上面的代码按整数演示；若采用“结果可为小数”的口径，应把操作数类型改为 double，在除法前检查除数，并在输出时按精度格式化。

后缀求值的时间是 O(n)，空间取决于扫描过程中同时未归约的操作数的最大数量，也就是操作数栈的最大深度，最坏为 O(n)（例如先连续读入大量操作数、最后才遇到运算符）。它不等于括号嵌套深度，也不等于表达式树深度——那些只是常见表达式下的一种直觉参照，不能替代“栈中最多同时存多少个数”这一判据。它的校验也很直接：扫描结束时栈中必须恰好剩下一个操作数；中途运算符弹出第二个操作数时栈为空，说明该运算符缺少左操作数。这两种错误在只求值时容易被忽略，却是判断输入是否合法的重要条件。

中缀式与后缀式的关系可以这样看：中缀求值中的运算符栈，本质上是在“推迟”暂时不能执行的运算；如果把这些被推迟的运算符在出栈时直接输出而不是执行，就得到后缀式。两者共享同一套优先级和左结合规则，区别只是输出运算符还是执行运算符。课程第 48 页只展开后缀求值，转换规则可作为同一框架的延伸理解，不必另记一套新规则。

递归与栈的关系更直接。函数调用时，系统用调用栈保存返回地址、参数和局部变量；递归函数每深入一层，就压入一个新的活动记录，返回时弹出。以阶乘为例，f(4) 依次调用 f(3)、f(2)、f(1)、f(0)，系统栈中同时存在 5 个活动记录；f(0) 返回后逐层相乘，栈逐层弹出。若没有基线条件，递归不会终止，栈最终溢出。

课件第 49—50 页对比了递归与显式栈：递归写法短、与数学定义接近，但递归深度受系统栈限制；显式栈把“待处理的参数和状态”存到用户自己管理的数据结构中，可以控制容量、暂停和恢复，也便于在嵌入式环境或深度可能很大的场景使用。转换的一般方法是把“调用”映射为压栈、“返回”映射为弹栈，并把参数、阶段编号和局部变量打包成一个结构体。代价是代码更长、状态机更复杂，因此只有在深度不可控或需要精确控制内存时才值得改写。

还要澄清一个常见误解：显式栈不一定比递归更省空间。递归使用的系统栈和显式栈保存的活动记录数量级相同，改写的主要收益是容量可控、可暂停恢复以及避开系统调用栈的深度上限；只有把递归状态进一步压缩（例如尾递归转循环、用少量变量代替整帧）时，辅助空间才可能真正下降。

3.11 回溯与 N 皇后：用栈保存搜索路径

对应课件第 51—52 页。

回溯法把问题的求解过程组织成一棵搜索树：每一步选择一个候选值，进入下一层；若当前选择导致后续无解，就退回上一层换下一个候选值。这里的“进入下一层”对应压栈，“退回上一层”对应弹栈，因此回溯与栈的关系不是类比，而是同一个过程。回溯通常还配合剪枝：在进入下一层之前就判断当前选择是否已经违反约束，若违反则不再展开，直接尝试下一个候选。

N 皇后问题是在 N×N 棋盘上放置 N 个皇后，使任意两个皇后不在同一行、同一列或同一条斜线上。按行放置可以天然保证不同行，于是只需为第 r 行选择一个列号，并检查它与前面已放置的皇后是否同列或同斜线。判断两个皇后 (r₁, c₁)、(r₂, c₂) 是否冲突：同列当且仅当 c₁ = c₂；同斜线当且仅当 |c₁ − c₂| = r₂ − r₁。

#define N 4
int col[N];          /* col[r] 为第 r 行皇后所在列，行列均从 0 开始编号 */
int solutionCount = 0;

int Conflict(int r, int c) {
    for (int i = 0; i < r; i++) {
        if (col[i] == c) return 1;                          /* 同列 */
        if (c - col[i] == r - i) return 1;                  /* 主对角线 */
        if (col[i] - c == r - i) return 1;                  /* 副对角线 */
    }
    return 0;
}

void Queen(int r, int n) {
    if (r == n) {                                           /* 找到一个解 */
        solutionCount++;
        return;
    }
    for (int c = 0; c < n; c++) {
        if (!Conflict(r, c)) {
            col[r] = c;                                     /* 压栈：记录选择 */
            Queen(r + 1, n);                                /* 进入下一行 */
        }
    }                                                       /* 循环结束即弹栈 */
}

void SolveQueens(int n) {
    if (n < 1 || n > N) {          /* col 数组只有 N 个单元，必须先检查 */
        printf("n 必须在 1..%d 之间\n", N);
        return;
    }
    solutionCount = 0;
    Queen(0, n);
}

上面的数组下标从 0 开始，列号 c 对应位序 c+1。SolveQueens(n) 先检查 1 ≤ n ≤ N：本实现把棋盘规模固定为编译期常量 N = 4，col 只有 4 个单元，若 n 超出范围继续递归就会写越界；实际题目要求更大的 n 时，应把 col 改为按 n 动态分配，或至少把上限 N 调大并同步检查。Queen(r, n) 的每一层只负责第 r 行；当 r == n 时所有行都已放置，得到一个解。col 数组就是显式的路径栈：递归深度为 r，col[0..r−1] 保存当前路径，返回上一层时不需要显式清除 col[r]，因为下一次赋值会覆盖它。

以 N = 4、列号从 1 开始、按升序尝试为例，前若干步的搜索过程如下。表中“栈”表示当前已放置的 (行, 列)，自底向顶对应递归深度。

N = 4 共有两个解：(2,4,1,3) 与 (3,1,4,2)（列号）。N = 1 有一个解；N = 2 和 N = 3 无解；N = 8 有 92 个解。分析复杂度时不要把阶乘写成“固定底数的指数”：简单实现逐行尝试每一列，未剪枝的全排列上界是 N! 量级（阶乘阶），每放置一个皇后还要与前面 O(N) 个皇后比较，因此包括检查在内的上界是 O(N · N!)。剪枝会砍掉大量分支，实际访问的结点数通常远小于 N!，但这只说明“上界很松、实际更快”，并不能据此给出未证明的紧界。N! 与 c^N 都增长很快，但它们是不同的阶，不能把 N! 直接说成“指数级”中的固定底数指数。空间方面，递归深度为 O(N)，col 数组为 O(N)，合计 O(N)。

若把递归改成显式栈，栈中应保存“当前行以及下一候选列”而不只是路径：弹出后要能从上次尝试的列继续，否则会重复搜索。递归写法由系统栈自动保存循环变量和返回位置，改成显式栈时这部分状态必须手工保存，这正是“递归转非递归”容易出错的地方。

3.12 队列的定义、术语与抽象数据类型

对应课件第 53—57 页。

队列与栈同属操作受限的线性表，区别在于“受限的位置”不同：栈只允许在同一端插入和删除，队列则规定在一端插入、在另一端删除。允许插入的一端称为队尾，允许删除的一端称为队头。元素入队的顺序是 a₁、a₂、…、a_n，其中 a₁ 是队头、a_n 是队尾；出队的顺序也是 a₁、a₂、…、a_n。因此队列遵循先进先出（First In First Out，FIFO）规则，先到达的元素先离开。

队列在现实中随处可见：银行窗口前排队、食堂打饭、电梯口等候、购票系统出票，都要求“先来先服务”。操作系统中的打印任务队列、进程就绪队列、消息队列也是同一结构。课件第 54 页用这些场景说明：队列的价值不是存储本身，而是用固定的顺序规则协调多个参与者，使先到达的请求不会因为后到达者插入而无限期推迟。

课件第 55 页给出队列的基本术语，并明确本章统一采用的指针约定。顺序循环队列中，front 指向队头元素所在的下标；rear 指向队尾元素的下一个空位（即下一次入队要写入的位置）。因此队空的条件是 front == rear，队满的条件是 (rear + 1) % MAXQSIZE == front，后者是为区分空满而牺牲一个单元的结果。链式队列中，front 指向附加头结点，rear 指向最后一个数据结点；空队列时两者相等且都指向头结点。本章所有代码与图示都按这一套约定书写，不同教材可能把 rear 定义为指向真实队尾元素，换用别的约定时必须同步修改判空、判满和长度公式。

GetHead 与 DeQueue 都涉及队头，但前者只读取、不改变 front，后者会移动 front 并释放或废弃原队头。许多实现错误地把“查看队头”写成“出队一次再放回去”，这对顺序队列看似无害，对链式队列却会真正释放结点，必须按操作语义严格区分。

3.13 顺序队列的假溢出与循环队列

对应课件第 58—63 页。

用数组实现队列时，最直接的做法是让 front 和 rear 随入队、出队不断向后移动，不回头。这样做很快，但会出现“假溢出”：队尾指针已经到达数组末端，而数组前端由于多次出队留出了空位；这些空位无法被再次利用，于是明明还有空间却无法入队。课件第 59 页用 M = 6 的数组演示：初始 front = rear = 0，连续入队 3 个元素后 rear = 3；再连续出队 3 个元素后 front = 3、rear = 3，队列变空，但 front 之前为 0、1、2 的三个单元已经永久浪费；继续入队时 rear 仍向右走，走到数组末端就误判为“满”。

解决假溢出的办法是把数组在逻辑上看成一个环：下标加到末端后回到 0，用取模运算实现。入队时先写 pBase[rear]，再执行 rear = (rear + 1) % MAXQSIZE；出队时先取 pBase[front]，再执行 front = (front + 1) % MAXQSIZE。只要数组容量大于 1，指针就能在环上循环使用，前端空出的单元会被后续入队重新占用。课件第 60 页用钟表作类比：12 点之后回到 1 点，下标 0 到 MAXQSIZE−1 之后回到 0。

环上的位置关系不能再用“rear − front”直接表示元素个数，因为 rear 可能已经绕到 front 前面。正确公式是

其中加上 MAXQSIZE 是为了保证被减数非负，再取模把结果限制在 0 到 MAXQSIZE−1 之间。例如 MAXQSIZE = 8、front = 3、rear = 2 时，长度为 (2 − 3 + 8) % 8 = 7，说明队列已满，而不是空。只看 front 与 rear 是否相等无法区分“空”和“满”，这是循环队列必须额外处理的核心问题。

循环队列的入队和出队都不需要移动元素，只改变下标，因此单次操作是 O(1)；代价是每次下标移动多一次取模运算，且队列容量受固定数组限制。取模是整数除法，通常比加减法慢，但仍是常数时间；在性能敏感的底层代码中，若容量取 2 的幂，可以用“与 (MAXQSIZE−1)”代替取模，但这是实现层面的优化，不属于数据结构本身。

3.14 循环队列的空满判定与基本操作

对应课件第 64—68 页。

队空时 front == rear；如果允许队满时也出现 front == rear，两种状态就无法区分。课件第 64 页给出两种方案。方案一增加一个计数器或长度字段：队空时长度为 0，队满时长度为 MAXQSIZE，空间利用率最高，但每次入队、出队都要同步维护这个字段，增加一处可能出错的状态。方案二牺牲一个存储单元：规定队列最多存放 MAXQSIZE−1 个元素，当 (rear + 1) % MAXQSIZE == front 时就认为队满。方案二不需要额外字段，判空判满各一个条件，代价是浪费一个单元。本章采用方案二，因为它的状态最少、验证最容易，而浪费一个单元在大多数应用中可以接受。

如果采用计数器方案，必须连同指针约定一起替换：例如令 rear 指向真实队尾元素、用 length 判断空满（空 length == 0，满 length == MAXQSIZE，M 个单元可全部存满），此时入队、出队和长度公式都随之改变；也可以用 tag 记录最后一次操作（front == rear 且 tag = 0 为空、tag = 1 为满）。无论采用哪种替代方案，都不能与本章“牺牲一个单元、(rear + 1) % MAXQSIZE == front”的判满公式混用：一边声称能存满 M 个元素，一边又用该式判满，状态定义就自相矛盾。

#define MAXQSIZE 8   /* 数组容量；实际最多存放 MAXQSIZE - 1 个元素 */

typedef struct {
    ElemType *pBase;     /* 动态数组基址 */
    int front;           /* 队头元素的下标 */
    int rear;            /* 队尾元素下一个空位的下标 */
} SqQueue;

Status InitQueue(SqQueue *Q) {
    Q->pBase = (ElemType *)malloc(sizeof(ElemType) * MAXQSIZE);
    if (Q->pBase == NULL) exit(OVERFLOW);
    Q->front = Q->rear = 0;
    return OK;
}

Status EnQueue(SqQueue *Q, ElemType e) {
    if ((Q->rear + 1) % MAXQSIZE == Q->front) return ERROR;   /* 队满 */
    Q->pBase[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXQSIZE;
    return OK;
}

Status DeQueue(SqQueue *Q, ElemType *e) {
    if (Q->front == Q->rear) return ERROR;                    /* 队空 */
    *e = Q->pBase[Q->front];
    Q->front = (Q->front + 1) % MAXQSIZE;
    return OK;
}

int QueueLength(const SqQueue *Q) {
    return (Q->rear - Q->front + MAXQSIZE) % MAXQSIZE;
}

以 MAXQSIZE = 8 为例，依次执行：入队 A 到 G（7 个元素，此时 front = 0、rear = 7，已满）；连续出队 A、B、C（front = 3、rear = 7，剩 4 个）；入队 H（写入下标 7，rear 变为 0）；入队 I（写入下标 0，rear 变为 1）；入队 J（写入下标 1，rear 变为 2）。此时 (rear + 1) % 8 = 3 == front，队列再次满，元素 D、E、F、G、H、I、J 分别占据下标 3、4、5、6、7、0、1，而下标 2 暂时空着。它此刻是 rear 所指的位置：在“牺牲一个单元”的约定下，满状态时 rear 指向的格子不存元素，用“下一个位置是否会追上 front”来判断满。这个格子并不是固定保留的：再出队一次后 front 变为 4，队列不再满，下一次入队就会把新元素写入下标 2、rear 变为 3。可见空位随 front、rear 一起移动，牺牲的是容量中的一个元素，而不是某个固定下标。

出队后原位置的数据仍然留在数组中，但已经不在 [front, rear) 的有效区间内，后续入队会覆盖它；因此不能依赖“出队后的值”做任何判断。front 和 rear 是下标而不是指针，超过 MAXQSIZE−1 后必须取模回到 0；如果某处直接写 rear++ 而漏掉取模，就会越界访问，这是循环队列最常见的实现错误。

3.15 链式队列

对应课件第 69—76 页。

顺序循环队列的容量固定，适合最大长度可预估的场景；如果元素个数波动很大、无法预估上限，链式队列更合适。队列要求在队尾插入、在队头删除，单链表恰好能在表头 O(1) 删除，但普通单链表在表尾插入需要先找到前驱，因此必须额外保存一个指向表尾的 rear 指针。课件第 70 页的结构是带头结点的单链表：front 指向附加头结点，头结点的 next 指向第一个数据结点；rear 指向最后一个数据结点。空队列时没有数据结点，front == rear == 头结点。

typedef struct QNode {
    ElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front;   /* 指向附加头结点 */
    QueuePtr rear;    /* 指向最后一个数据结点 */
} LinkQueue;

Status InitQueue(LinkQueue *Q) {
    Q->front = Q->rear = (QNode *)malloc(sizeof(QNode));
    if (Q->front == NULL) exit(OVERFLOW);
    Q->front->next = NULL;          /* 头结点不存数据 */
    return OK;
}

Status EnQueue(LinkQueue *Q, ElemType e) {
    QNode *s = (QNode *)malloc(sizeof(QNode));
    if (s == NULL) exit(OVERFLOW);
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;              /* 链到表尾之后 */
    Q->rear = s;                    /* rear 始终指向最后一个数据结点 */
    return OK;
}

Status DeQueue(LinkQueue *Q, ElemType *e) {
    if (Q->front == Q->rear) return ERROR;   /* 队空 */
    QNode *p = Q->front->next;               /* 第一个数据结点 */
    *e = p->data;
    Q->front->next = p->next;
    if (Q->rear == p) Q->rear = Q->front;    /* 删除的是最后一个结点 */
    free(p);
    return OK;
}

DeQueue 中“若 rear == p 则 rear = front”这一步最容易被漏掉。考虑队列中只有一个数据结点的情况：删除后队列变空，front->next 变成 NULL，但 rear 仍指向刚被 free 的结点，成为悬空指针；下一次入队会通过 rear->next 访问已释放内存，属于未定义行为。把 rear 拉回头结点，既恢复了 front == rear 的空队列表示，也保证后续入队安全。

附加头结点的作用是统一操作：没有头结点时，向空队列插入第一个元素、删除最后一个元素都要单独判断并修改 front；有头结点后，所有插入都发生在某个结点之后，所有删除都发生在头结点之后，代码不需要为“第一个结点”写特例。代价是多一个结点、多一次内存分配，以及每个元素多一个指针的存储开销。链式队列不会“队满”（除非内存耗尽），EnQueue 和 DeQueue 都是严格的 O(1)，不需要均摊分析。

课件第 75—76 页对循环队列与链式队列作了对比。存储上，循环队列用连续数组，链式队列用离散结点；容量上，循环队列固定为 MAXQSIZE−1，链式队列只受可用内存限制；空间效率上，数组没有指针开销但可能预留过多，链表按需分配但每结点多一个指针；时间上两者入队、出队都是 O(1)；实现难度上，循环队列的取模与空满判定更易错，链式队列的指针更新更易错。选型时，若最大长度稳定且可预估、追求缓存局部性，用循环队列；若长度波动大或频繁插入删除、不希望预留大数组，用链式队列。

3.16 队列的应用：滑动窗口、缓冲区与层次遍历

对应课件第 77—86 页。

课件把队列的典型应用分为四类：缓冲区管理、滑动窗口、层次遍历和任务调度。它们的共同点是“按到达顺序处理”，但队列在其中承担的角色不同：缓冲区保存尚未处理的数据，滑动窗口只保留最近一段数据，层次遍历保存待访问的结点，任务调度保存等待执行的请求。

滑动窗口求移动平均是课件第 79—84 页的重点，但课件在这里用了两组不同的题设，必须分开理解。第 79 页的演示是：传感器每隔 1 秒采集一次，窗口 k = 3，采集值为 20.0、22.5、21.0、23.5、24.0，课件还给出了逐步队列状态；该页在窗口未满时只累加、不输出（前两次显示“--”），从第 3 个样本起才开始输出平均值（21.17、22.33、22.83），即“等待满窗”策略。第 80—82 页的教材例是：传感器每秒上报 10 次，应用每秒读取一次，第 82 页算法用 HIST_TIMES（= 100）作为窗口常量。这里存在原始材料的内部不一致：第 80 页同时出现“前 10 次”与“前 100 次”两种窗口表述，第 82 页算法取 100；100 次采样按每秒 10 次计算覆盖 10 秒，而第 79 页的 k = 3 覆盖 3 秒，两者既不是同一题设，也不能把“最近 k 个样本”直接当成“最近 k 秒”。因此本节用通用窗口 k 叙述算法：k = 3 只对应第 79 页演示，k = 100 只作为第 82 页的课件常量并注明其时间跨度。在平均值的计算口径上，本节与配套实验统一采用暖启动：窗口未满时，分母取当前已收集的样本数（而不是 k），窗口满后分母才固定为 k；课件第 79 页与第 82 页的算法都采用“预热期不输出”的等待策略（第 82 页在预热期返回 DATA_NOT_ENOUGH，分母始终取 HIST_TIMES）。两种口径都能自洽，但必须在题设中写明，不能把“未满窗口按 k 平均”与“按当前项数平均”混用。

先看第 79 页的 k = 3 演示：采样值 20.0、22.5、21.0、23.5、24.0，每秒采集 1 次、窗口覆盖 3 秒。按暖启动口径，第 1 个值入队后分母为 1，平均值为 20.00；第 2 个值入队后分母为 2，平均值 42.5/2 = 21.25；第 3 个值入队后窗口满，分母为 3，平均值 63.5/3 ≈ 21.17。从第 4 个值起窗口始终满，分母保持 3：23.5 到来时先让最旧的 20.0 出队（总和减为 43.5），再让 23.5 入队（总和变为 67.0），平均值为 67.0/3 ≈ 22.33；第 5 个值同理，22.5 出队、24.0 入队，总和 68.5，平均值约 22.83。每一步只有一次出队、一次入队、两次加减和一次除法，与 k 无关。

如果严格按课件第 79 页“等待满窗”口径，前两个样本只入队、不输出（界面显示“--”），第一个输出出现在第 3 个样本：63.5/3 ≈ 21.17；之后第 4、5 个样本分别输出 22.33、22.83。因此两种口径在窗口满后的数值完全相同，差别只在预热期的前 k−1 个样本是否给出“样本不足的临时平均”。本讲义后面的实验采用暖启动，是为了让每一步都有可观察的输出，并明确展示分母从 1 变到 k 的过程；课件演示则选择等待满窗。

对应的算法可以写成两个函数：AddTempToQueue 在队满时先出队最旧值、再从队尾入队新值，并增减总和；OutputTemperature 按暖启动口径，在没有样本时返回“数据不足”，否则返回总和除以当前元素个数。注意保存总和的是全局或队列附属的累加变量，它必须与队列内容严格同步：任何一次入队或出队漏改总和，后续所有平均值都会错，而且错误会持续累积。例如，暖启动下代码中的分母是 length，而窗口满时 length == WINDOW，所以同一个公式同时覆盖预热期与满窗期。这里的队列是一个独立的温度队列：元素类型 ElemType 取 double（温度有小数，不能沿用前面字符栈、字符队列的 char 或整型，否则小数部分会被截断），窗口大小为 WINDOW 时物理数组容量取 WINDOW + 1，即 MAXQSIZE = k + 1（牺牲一个单元区分空满），队中最多同时保存 k 个采样值。下面的实现沿用课件第 82 页的窗口常量 WINDOW = 100；把 WINDOW 改为 3、MAXQSIZE 改为 4，即可直接运行第 79 页的 k = 3 演示，两个题设的差别只在窗口大小与采样频率。

#define WINDOW 100      /* 通用窗口 k；第 82 页教材例取 100（每秒 10 次采样时覆盖 10 秒） */
#define MAXQSIZE (WINDOW + 1)   /* 独立温度队列：ElemType 取 double，物理容量 k+1，最多存 k 个样本 */
double gSum = 0.0;

Status AddTempToQueue(SqQueue *Q, double e) {
    if ((Q->rear + 1) % MAXQSIZE == Q->front) {   /* 窗口满：移出最旧值 */
        gSum -= Q->pBase[Q->front];
        Q->front = (Q->front + 1) % MAXQSIZE;
    }
    Q->pBase[Q->rear] = e;
    gSum += e;
    Q->rear = (Q->rear + 1) % MAXQSIZE;
    return OK;
}

Status OutputTemperature(const SqQueue *Q, double *avg) {
    int length = (Q->rear - Q->front + MAXQSIZE) % MAXQSIZE;
    if (length == 0) return DATA_NOT_ENOUGH;   /* 尚无样本，不能作分母 */
    *avg = gSum / length;                    /* 暖启动：分母是当前项数；满窗时 length == WINDOW */
    return OK;
}

上面的代码采用暖启动口径：窗口未满时输出也照常进行，分母是当前项数 length；窗口满后 length == WINDOW，分母自然固定为 WINDOW。这与课件第 82 页“预热期不输出、分母恒为 HIST_TIMES”的策略不同：后者把前 k 个样本视为预热，期间不给出平均值；前者在第一个样本后就有输出，但早期平均值只代表极少数样本，波动会比较大。两种策略都成立，关键是分母的含义必须在题设和界面上写明，绝不能一边显示“窗口 k 的平均”一边用不足 k 个样本去除。该方案的复杂度是：每次采样 O(1)，每次输出 O(1)，额外空间 O(k)。若不做总和维护，每次输出都要遍历窗口，单次 O(k)、整体 O(nk)。课件还强调：滑动窗口的“队列满”正是“已经有 k 个历史值”的时刻，因此判满与“数据足够”可以共用同一个长度判断；同时，满时先出队再入队，顺序不能反，否则会覆盖尚未移出的最旧值。

缓冲区管理是队列的另一个核心应用。课件第 85—86 页描述了生产者—消费者模型：生产者把数据放入循环队列，消费者从队头取出；队列满时生产者等待（或丢弃/覆盖，取决于策略），队列空时消费者等待；FIFO 保证数据按到达顺序处理，不会因为处理速度波动而乱序。键盘输入缓冲、网络数据包缓冲、打印任务队列都采用这一模型。这里的等待与唤醒是并发环境下的同步问题，需要条件变量、信号量或互斥锁配合，循环队列本身只负责存取顺序；本节的伪代码是单线程逻辑示意，不包含线程同步。缓冲区满时还可选择丢弃新数据或覆盖最旧数据，具体策略必须写明，不能把“生产者等待”当成唯一实现。缓冲区容量的选择是延迟与吞吐的权衡：容量太小会频繁阻塞或丢数据，容量太大则占用内存并增加排队延迟。

层次遍历在课件第 78 页作为队列应用方向列出（树和图的广度优先遍历），正文未展开算法。其要点是：队列保存“当前层尚未处理的结点”，处理一个结点时把它的孩子依次入队；由于队列先进先出，同一层的结点一定先于下一层被处理，输出顺序就是层次顺序。这部分作为补充理解即可，具体遍历实现属于树与图章节的内容。

3.17 栈与队列的对比及系统层面的应用

对应课件第 87—93 页。

栈与队列都是操作受限的线性表，很多实现细节可以互相借鉴，但访问规则完全不同。把两者放在一起对照，可以避免“把栈顶和队头混为一谈”“把 LIFO 当成 FIFO”这类概念错误。

两者的共同点同样重要：它们都只允许在端点操作，不支持按下标随机访问；都可以用顺序或链式方式实现；核心操作在不触发扩容时都是 O(1)；都需要明确的判空、判满和长度定义；抽象数据类型的描述方法完全一致。理解这些共同点，就能把顺序表、链表章节的知识直接迁移过来，只需替换“允许操作的位置”和“边界条件”。

差异的关键在于“谁先离开”。栈只关心最近一次操作，因此天然适合需要回退的场景：函数调用返回、递归、撤销、括号闭合、表达式求值的运算符栈。队列强调到达顺序，因此适合需要公平排队的场景：进程就绪队列、打印任务、消息中间件、网络数据包缓冲。课件第 90 页列举了编程语言和系统中的体现，例如 Java、C++ 的函数调用栈，Python 的递归深度限制，浏览器的前进后退（两个栈），编辑器的撤销与重做（两个栈），编译器的运算符栈；队列方面有操作系统的先来先服务调度、Java 的 Queue 接口与 LinkedList、Python 的 collections.deque、TCP 的滑动窗口以及 Kafka、RabbitMQ 等消息队列。

第 91 页提醒：递归过深导致栈溢出，根本原因是系统调用栈的容量有限，而不是递归本身“不能用”。遇到这种情况，可以减小递归深度、改用尾递归（若语言支持优化），或按第 49—50 页的方法把递归改写为显式栈。课件第 92—93 页补充了历史背景：栈和队列都先在系统软件中大量使用——栈与编译器、递归调用和表达式计算相关，队列与操作系统调度、缓冲区管理相关——后来才被整理成教材中的抽象结构。具体年代、人物与文献细节请参阅课件列出的资料，本讲义不再罗列难以核实的年份，以免把“某年首次提出”一类说法当成课程结论。

3.18 状态约定、复杂度与常见错误

对应课件第 94—95 页。

本章的公式和状态约定可以集中成一张表。使用前先确认教材采用哪种约定，不同约定下公式必须整体替换，不能混用。

复杂度方面，栈和队列的进、出、取顶/取头都是 O(1)；顺序栈扩容的单次代价是 O(n)，按比例扩容时摊还 O(1)，固定增量扩容时摊还代价会随规模上升；中缀、后缀求值都是 O(n)，空间取决于栈的最大深度，最坏 O(n)——不能简单说成“括号嵌套深度”；N 皇后的简单实现未剪枝时全排列上界为 N! 量级，加上逐次冲突检查为 O(N · N!) 上界，剪枝只减少实际访问结点，不给未证明的紧界；滑动窗口每次采样 O(1)；两个栈模拟队列的 DeQueue 摊还 O(1)、最坏 O(n)。把这些结论连同成立条件一起记忆，比只记阶更可靠。

常见错误可以归为四类。第一类是约定不统一：把“pTop 指向栈顶元素”与“pTop 指向下一个空位”混用，导致判空、判满、长度三处公式同时错位；或者把 pTop 的下一空位公式套到双端栈 top1/top2 上（后者是栈顶元素下标）；循环队列的 rear 若被定义为指向真实队尾元素，判满和长度公式都要改。第二类是执行顺序错误：Push 必须先写 *pTop 再 pTop++，若先移动指针再写入，新元素会落到错误位置；Pop 的关键是读取原栈顶，并使读取偏移与指针移动后的约定一致：先读 *(pTop−1) 再 pTop--，或者先 pTop-- 再读 *pTop（此时 pTop 已指向原栈顶元素）；写成数组下标也是同理——先读 items[top−1] 再 --top，或先 --top 再读 items[top]，不能把后一种正确写法当成错误。链队列删除尾结点后忘记把 rear 拉回头结点，同样会破坏结构。第三类是边界缺失：空栈 Pop、空队 DeQueue、队满仍 EnQueue、除数为 0、括号不配对、多位数只读一位，这些问题在样例上不出现，却会在真实输入中暴露。第四类是资源管理错误：DestroyStack 只把指针置空而不 free，ClearStack 误释放数组，realloc 后继续使用旧 pTop，链式结构删除结点后继续访问已释放内存。

避免这些错误的方法是给每个结构写下“不变量”，例如：顺序栈中 pBase <= pTop <= pBase + stacksize，且 [pBase, pTop) 内恰好是当前元素；循环队列中有效元素是沿环从 front 走到 rear 之前经过的单元；链队列中 rear 始终指向最后一个数据结点，空时 front == rear == 头结点。每次修改指针后检查不变量是否仍成立，比逐个记错误案例更有效。

3.19 综合练习与解答

对应课件第 96—104 页。

以下九题按课件课堂练习整理，先独立作答，再展开对照。第 9 题在课件第 104 页，属于栈与队列的综合应用。

练习 1：出栈序列

入栈顺序为 1、2、3，列出所有合法出栈序列，并说明为什么 3、1、2 不可能。

练习 2：顺序栈操作追踪

从空栈开始依次执行 Push(1)、Push(2)、Pop、Push(3)、Push(4)、Pop、Pop，写出每次 Pop 的返回值和最终栈中剩余元素。

练习 3：链式栈的 GetTop

写出带头结点链式栈的 GetTop，并说明它与顺序栈 GetTop 的区别，以及链式栈是否需要判满。

Status GetTop(LinkStack S, ElemType *e) {
    if (S->next == NULL) return ERROR;   /* 空栈 */
    *e = S->next->data;                  /* 栈顶在表头之后 */
    return OK;
}

练习 4：括号匹配追踪

对 {[()]{()()}} 逐步写出栈的状态，判断是否匹配；若把中间部分改成 [(])，会在哪一步失败？

练习 5：后缀表达式求值

对 5 1 2 + 4 * + 3 - 逐步求值，写出操作数栈的变化和最终结果。

练习 6：十进制转八进制

用栈把十进制数 1348 转换为八进制，写出余数的入栈顺序和最终结果。

练习 7：循环队列入队/出队

MAXQSIZE = 6，初始 front = rear = 0，依次执行 EnQueue(A)、EnQueue(B)、EnQueue(C)、DeQueue、EnQueue(D)、EnQueue(E)，逐步写出 front、rear 和队列长度。

练习 8：循环队列的状态计算

MAXQSIZE = 8，front = 3、rear = 7。求当前元素个数；再入队 2 个元素后 rear 是多少；此时还能否再入队 1 个？

练习 9：两个栈模拟队列

用两个栈 S1、S2 模拟队列，给出 EnQueue、DeQueue 的思路，并分析复杂度。

参考资料与章节对应

本讲义依据课程课件《数据结构》第 3 章整理，页码为原始 PDF 从 1 起的页序（共 105 页），与“PDF 第 N 页”标记一致。对应关系如下。

几点说明。其一，第 78 页只把“层次遍历”列为队列应用方向，未展开具体算法，本节把它标为补充理解。其二，第 79—84 页的温度窗口例子与第 85—86 页的生产者—消费者缓冲按课件展开；第 79 页的 k = 3 演示与第 80—82 页的 100 次窗口按不同题设分别说明，未把采样率与窗口大小拼成同一题设；本节与配套实验采用暖启动（未满窗口分母取当前样本数），课件第 79 页与第 82 页采用预热期不输出（第 82 页分母恒为窗口常量），两种口径已在正文中并列说明。其三，第 96—104 页九道练习的解答由题意推导，其中第 9 题对应第 104 页。本节中标为补充的内容是对课件的解释性扩展，不改变课件原有结论。

本章配套笔记见第三章笔记。