Algorithm / List / Stack / Queue 复习笔记

Algorithm / List / Stack / Queue 复习笔记#

0. 总览#

这份笔记把以下四块按课程学习顺序整理成一份连续笔记：

1. Algorithm Analysis：算法定义、复杂度、渐进记号、循环/递归分析、最大子列和、二分搜索。
2. List ADT：ADT 思想、数组表、单链表、双向循环链表、多项式、多重链表、游标实现。
3. Stack ADT：LIFO、数组/链表栈、括号匹配、后缀表达式、中缀转后缀、函数调用栈。
4. Queue ADT：FIFO、数组/链表队列、循环队列、层序遍历、BFS、LRU-K。

逻辑顺序是：先学会如何分析算法，再学线性表这个一般 ADT；Stack 和 Queue 是 List 的两个受限版本，所以放在 List 后面。后续树、堆、图的复杂度分析都会反复用到这里的 Big-O、循环规则和递归式。

1. Algorithm 与 Program#

1.1 Algorithm 的定义#

课程 PPT 的定义：

An algorithm is a finite set of instructions that, if followed, accomplishes a particular task.

一个算法必须满足五个条件：

注意：

• Program 用某种编程语言写出，不一定有限。例如 operating system 可以一直运行。
• Algorithm 可以用自然语言、流程图、程序语言或 pseudo-code 描述。

1.2 Selection Sort 例子#

PPT 用 selection sort 说明算法描述。

任务：

Sort a set of n >= 1 integers in increasing order.

思想：

From those integers that are currently unsorted,
find the smallest and place it next in the sorted list.

伪代码：

for (i = 0; i < n; i++) {
    Examine list[i] to list[n - 1]
    and suppose that the smallest integer is at list[min];
    Interchange list[i] and list[min];
}

复杂度：

• 外层执行 $n$ 次。
• 第 $i$ 次从未排序区间中找最小值，长度约为 $n-i$。
• 总比较次数是：

所以：

额外空间：

2. What to Analyze#

2.1 分析什么#

PPT 区分两类时间：

• Machine & compiler-dependent run times：依赖机器、编译器、系统环境。
• Time & space complexities：尽量和机器、编译器无关。

算法分析通常关注：

Tavg(N)
Tworst(N)

其中：

• $T_{avg}(N)$ 是平均情况时间复杂度。
• $T_{worst}(N)$ 是最坏情况时间复杂度。
• 如果输入不止一个规模参数，复杂度函数也可以有多个参数。

2.2 课程分析假设#

PPT 的假设：

1. instructions are executed sequentially
2. each instruction is simple, and takes exactly one time unit
3. integer size is fixed and we have infinite memory

这些假设不是现实机器的完整模型，但足够用来比较增长趋势。

3. 精确计数到渐进分析#

3.1 Matrix Addition#

PPT 例子：

void add(int a[][MAX_SIZE],
         int b[][MAX_SIZE],
         int c[][MAX_SIZE],
         int rows, int cols)
{
    int i, j;
    for (i = 0; i < rows; i++)
        for (j = 0; j < cols; j++)
            c[i][j] = a[i][j] + b[i][j];
}

PPT 给出的精确计数：

outer loop test: rows + 1
inner loop test: rows * (cols + 1)
assignment:       rows * cols

所以：

渐进复杂度：

如果 \(rows >> cols\)，交换循环顺序并不会改变渐进复杂度，但可能影响缓存局部性和常数时间；课程在这里主要强调多参数复杂度要保留参数关系。

3.2 Iterative Sum#

PPT 例子：

float sum(float list[], int n)
{
    float tempsum = 0;
    int i;

    for (i = 0; i < n; i++)
        tempsum += list[i];

    return tempsum;
}

精确计数：

渐进复杂度：

空间复杂度：

3.3 Recursive Sum#

PPT 例子：

float rsum(float list[], int n)
{
    if (n)
        return rsum(list, n - 1) + list[n - 1];
    return 0;
}

PPT 给出的计数：

渐进复杂度：

但递归版每一步有函数调用开销，而且使用系统栈：

所以不要因为 $2n+2 < 2n+3$ 就误以为递归一定更快。复杂度主要比较增长趋势，不等于真实运行时间的全部。

4. Asymptotic Notation#

4.1 为什么需要渐进记号#

PPT 的问题：

Suppose Tp1(N) = c1N^2 + c2N
and     Tp2(N) = c3N.
Which one is faster?

不管常数 $c_1,c_2,c_3$ 是什么，只要 $N$ 足够大，$N^2$ 最终会比 $N$ 增长更快。

所以分析重点是：

growth in run time as N changes

4.2 Big-O#

定义：

如果存在正常数 $c$ 和 $n_0$，使得对所有 $N \ge n_0$：

直观理解：

• $O(f(N))$ 是渐进上界。
• 通常用于表示最坏增长不超过某个量级。

例子：

也可以说 $2N+3=O(N^2)$，但课程强调我们总是取最小、最紧的常用上界。

4.3 Big-Omega#

定义：

如果存在正常数 $c$ 和 $n_0$，使得对所有 $N \ge n_0$：

直观理解：

• $\Omega(g(N))$ 是渐进下界。
• 课程强调我们总是取最大的、最紧的常用下界。

4.4 Big-Theta#

定义：

当且仅当：

直观理解：

• $\Theta$ 是 tight bound。
• 既有上界，也有下界。

例子：

4.5 little-o#

定义：

如果：

并且：

直观理解：

• $o(p(N))$ 表示严格小阶。
• 例如 $N = o(N^2)$。

5. 渐进分析规则#

5.1 加法与乘法规则#

PPT 规则：

如果：

那么：

也就是连续语句复杂度取较大者。

乘法规则：

常用于嵌套循环。

5.2 多项式规则#

如果 $T(N)$ 是 $k$ 次多项式，则：

例子：

5.3 对数增长#

PPT 结论：

其中 $k$ 是任意常数。

含义：

• logarithms grow very slowly。
• 二分搜索、平衡树、堆的高度都常出现 $\log N$。

5.4 循环分析通用规则#

For Loops#

一个 for 循环的时间：

循环体时间 * 迭代次数

例子：

for (i = 0; i < N; i++) {
    x++;
}

复杂度：

Nested For Loops#

嵌套循环的时间通常是各层次数相乘：

for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        x++;

复杂度：

如果内层次数依赖外层：

for (i = 0; i < N; i++)
    for (j = i; j < N; j++)
        x++;

总次数：

Consecutive Statements#

连续语句相加，最后取最大阶：

statement1;  /* O(N) */
statement2;  /* O(N^2) */

总复杂度：

If / Else#

PPT 规则：

if (Condition)
    S1;
else
    S2;

时间不超过：

test + max(time(S1), time(S2))

5.5 递归分析#

PPT 的 Fibonacci 例子：

long int Fib(int N)
{
    if (N <= 1)
        return 1;
    else
        return Fib(N - 1) + Fib(N - 2);
}

递推式：

并且：

所以朴素递归 Fibonacci 是指数级。

直观原因：

• 大量子问题重复计算。
• Fib(N-2)、Fib(N-3) 等会在不同分支中反复出现。

复杂度：

通常粗略写成指数级：

空间复杂度是递归深度：

6. Compare the Algorithms: Maximum Subsequence Sum#

6.1 问题定义#

PPT 问题：

Given possibly negative integers:

find the maximum value of a contiguous subsequence sum.

课程约定：

Max sum is 0 if all the integers are negative.

6.2 Algorithm 1: 三重循环#

代码结构：

int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, i, j, k;
    MaxSum = 0;

    for (i = 0; i < N; i++) {
        for (j = i; j < N; j++) {
            ThisSum = 0;
            for (k = i; k <= j; k++) {
                ThisSum += A[k];
            }
            if (ThisSum > MaxSum) {
                MaxSum = ThisSum;
            }
        }
    }
    return MaxSum;
}

含义：

• 枚举起点 $i$。
• 枚举终点 $j$。
• 每次重新求 $A[i]$ 到 $A[j]$ 的和。

复杂度：

空间复杂度：

6.3 Algorithm 2: 二重循环#

改进点：

• 固定起点 $i$ 后，随着 $j$ 向右移动，增量维护 ThisSum。
• 不再每次从 $i$ 到 $j$ 重新求和。

代码结构：

int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, i, j;
    MaxSum = 0;

    for (i = 0; i < N; i++) {
        ThisSum = 0;
        for (j = i; j < N; j++) {
            ThisSum += A[j];
            if (ThisSum > MaxSum) {
                MaxSum = ThisSum;
            }
        }
    }
    return MaxSum;
}

复杂度：

空间复杂度：

6.4 Algorithm 3: Divide and Conquer#

核心想法：

最大子列和只可能在三种位置：

1. 完全在左半边。
2. 完全在右半边。
3. 跨过中点。

递归求左右两边；跨中点的最大和可以线性扫描得到。

递推式：

展开：

空间复杂度：

因为递归深度约为 $\log N$。

6.5 Algorithm 4: On-line Algorithm#

PPT 代码：

int MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, j;
    ThisSum = MaxSum = 0;

    for (j = 0; j < N; j++) {
        ThisSum += A[j];

        if (ThisSum > MaxSum) {
            MaxSum = ThisSum;
        } else if (ThisSum < 0) {
            ThisSum = 0;
        }
    }
    return MaxSum;
}

这个算法也常叫 Kadane algorithm。

关键判断：

• 如果当前前缀和 \(ThisSum < 0\)，它只会拖累后面的子列。
• 所以直接丢弃，从下一个位置重新开始。

复杂度：

空间复杂度：

PPT 强调：

• A[] is scanned once only.
• At any point in time, the algorithm can correctly give an answer to the subsequence problem for the data it has already read.

所以它是 on-line algorithm。

6.6 四个算法对比#

这组例子是算法分析的核心模板：同一个问题，不同算法的复杂度差异可以非常大。

7. Logarithms in Running Time#

7.1 Binary Search#

PPT 问题：

给定有序数组：

查找元素 $X$。

输出：

• 如果 $X==A[i]$，返回 $i$。
• 如果不存在，返回 $-1$。

7.2 迭代模板#

int BinarySearch(const ElementType A[], ElementType X, int N)
{
    int Low, Mid, High;
    Low = 0;
    High = N - 1;

    while (Low <= High) {
        Mid = (Low + High) / 2;

        if (A[Mid] < X) {
            Low = Mid + 1;
        } else if (A[Mid] > X) {
            High = Mid - 1;
        } else {
            return Mid;
        }
    }
    return -1;
}

每次循环都把搜索区间大约减半：

所以最坏情况：

空间复杂度：

7.3 什么时候适合二分搜索#

PPT 说明：

Binary search is very useful when the data are static and sorted.

适用条件：

1. 数据支持随机访问，例如数组。
2. 数据已经排序。
3. 查找次数足够多，使排序或维护有序的成本值得。

和本仓库近期项目的关系：

• project/project1/code/search.c 中有 iterative/recursive binary search。
• 递归二分的时间也是 $O(\log N)$，但额外空间是递归栈 $O(\log N)$。
• 迭代二分额外空间是 $O(1)$。

8. Checking Your Analysis#

8.1 倍增检查法#

PPT 方法 1：

当输入规模从 $N$ 变成 $2N$：

这不是严格证明，但可以用实验检查自己的分析是否合理。

8.2 归一化检查法#

PPT 方法 2：

如果猜测：

就检查：

是否趋向相对稳定。

本仓库 project/project1/works/Normal-1 Performance Measurement (Search).md 就是类似思路：通过实验比较顺序搜索、二分搜索、递归和迭代版本的运行时间。

9. Abstract Data Type#

9.1 Data Type#

课程 PPT 的定义：

例子：

int = {0, +/-1, +/-2, ..., INT_MAX, INT_MIN}
      union {+, -, *, /, %, ...}

9.2 ADT#

PPT 定义：

An Abstract Data Type is a data type that is organized in such a way that the specification on the objects and specification of the operations on the objects are separated from the representation of the objects and the implementation of the operations.

直观理解：

• ADT 关心“能做什么”。
• 实现关心“怎么做”。
• 使用者不应该依赖内部表示。

和近期专题的关系：

• Stack ADT：只允许在 top 插入/删除。
• Queue ADT：rear 插入、front 删除。
• List ADT：允许按位置、按结点关系进行更一般的操作。
• Tree ADT：对象和操作又换成树结构，但思想仍是对象和操作分离。

10. The List ADT#

10.1 对象#

PPT 写作：

(item0, item1, ..., itemN-1)

也就是一个有限序列。

10.2 操作#

PPT 列出的操作：

1. Finding the length, $N$, of a list.
2. Printing all the items in a list.
3. Making an empty list.
4. Finding the $k$-th item from a list, $0 \le k < N$.
5. Inserting a new item after the $k$-th item of a list, $0 \le k < N$.
6. Deleting an item from a list.
7. Finding next of the current item from a list.
8. Finding previous of the current item from a list.

PPT 问了一个小问题：

Why after?

原因和链表实现有关：如果已经给出当前位置结点，在它后面插入只需要改常数个指针；在它前面插入则常常需要先找到前驱。

11. Simple Array Implementation of Lists#

11.1 表示法#

PPT 的顺序映射：

array[i] = item_i

数组中逻辑相邻的元素在物理地址上也相邻：

array + i     -> item_i
array + i + 1 -> item_{i+1}

11.2 优点#

按下标查找很快：

因为数组支持随机访问。

11.3 缺点#

PPT 强调两个问题：

1. MaxSize has to be estimated.
2. Insertion and Deletion not only take $O(N)$ time, but also involve a lot of data movements.

插入第 $k$ 个位置后面时，要把后面的元素整体后移：

删除时，要把后面的元素整体前移：

11.4 数组 List 复杂度#

空间复杂度：

12. Linked Lists#

12.1 基本结构#

PPT 中每个链表结点包含：

Data
Pointer

C 结构示例：

typedef struct list_node *list_ptr;

struct list_node {
    char data[4];
    list_ptr next;
};

list_ptr ptr;

链表结点在内存中的位置不必连续。PPT 提醒：

Locations of the nodes may change on different runs.

12.2 创建和链接结点#

PPT 示例：

list_ptr N1, N2;

N1 = (list_ptr)malloc(sizeof(struct list_node));
N2 = (list_ptr)malloc(sizeof(struct list_node));

/* conceptually:
   N1->data = "ZHAO";
   N2->data = "QIAN";
*/

N1->next = N2;
N2->next = NULL;
ptr = N1;

注意在真实 C 代码中，数组字段不能直接用 \(=\) 赋字符串，应该使用 strcpy 或初始化时赋值。

12.3 插入#

在结点 node 后插入 temp：

temp->next = node->next;
node->next = temp;

顺序不能反。

如果先做：

node->next = temp;
temp->next = node->next;

那么第二句会变成：

temp->next = temp;

原来 node 后面的链会丢失。

复杂度：

前提是已经拿到了 node 指针。

12.4 插入新的第一个元素#

如果没有 dummy head node，插入头结点需要单独处理：

temp->next = head;
head = temp;

如果有 dummy head node，可以统一写成“在 header 后插入”：

temp->next = header->next;
header->next = temp;

这就是 header node 的好处：减少边界情况。

12.5 删除#

PPT 中删除 node 时，需要已知它的前驱 pre：

pre->next = node->next;
free(node);

复杂度：

前提是已经拿到了 pre。

如果只知道要删除的值，通常要先从头扫描：

12.6 删除第一个结点#

没有 dummy head node 时：

node = head;
head = head->next;
free(node);

有 dummy head node 时：

node = header->next;
header->next = node->next;
free(node);

因此 PPT 的回答是：

We can add a dummy head node to a list.

12.7 单链表复杂度#

空间复杂度：

每个结点还要额外存一个 next 指针。

13. Doubly Linked Circular Lists#

13.1 为什么需要双向链表#

PPT 的动机：

如果有链表：

1 -> 2 -> 3 -> ... -> m

当你已经在第 $m$ 个结点时，如果要找它的前驱 $m-1$：

• 单链表只能从头重新走一遍。
• 双向链表可以直接走 llink。

这对删除当前结点尤其重要，因为删除通常要改前驱的链接。

13.2 结构#

PPT 结构：

typedef struct node *node_ptr;

struct node {
    node_ptr llink;
    element item;
    node_ptr rlink;
};

关系：

ptr == ptr->llink->rlink
ptr == ptr->rlink->llink

13.3 Circular + Head Node#

双向循环链表常带 head node：

H <-> item1 <-> item2 <-> item3
^                         |
|_________________________|

空链表：

H->llink = H
H->rlink = H

好处：

• 插入第一个结点和普通插入统一。
• 删除最后一个结点和普通删除统一。
• 找 previous 是 $O(1)$。

13.4 双向循环链表复杂度#

空间复杂度：

每个结点多存两个指针，常数空间开销比单链表更大。

14. Polynomial ADT#

14.1 对象#

PPT 定义：

可以看成一组有序对：

<e_i, a_i>

其中：

• $a_i$ 是 coefficient。
• $e_i$ 是 exponent。
• $e_i$ 是非负整数。

14.2 操作#

PPT 列出的操作：

1. Finding degree, $\max\{e_i\}$.
2. Addition of two polynomials.
3. Subtraction between two polynomials.
4. Multiplication of two polynomials.
5. Differentiation of a polynomial.

14.3 Representation 1: Array#

PPT 表示：

typedef struct {
    int CoeffArray[MaxDegree + 1];
    int HighPower;
} *Polynomial;

含义：

• CoeffArray[i] 存 $x^i$ 的系数。
• HighPower 存最高次数。

优点：

• 如果多项式比较 dense，实现加法、乘法都直接。
• 按指数访问系数是 $O(1)$。

缺点：

• 对 sparse polynomial 很浪费。

PPT 例子：

P1(x) = 10x^1000 + 5x^14 + 1
P2(x) = 3x^1990 - 2x^1492 + 11x + 5

虽然非零项很少，但数组必须开到很高次数。

乘法复杂度：

如果两个多项式次数分别为 $N_1,N_2$：

这里按最高次数计算，遇到稀疏多项式会做大量无意义的零项计算。

14.4 Representation 2: Linked List#

PPT 表示每一项为一个结点：

typedef struct poly_node *poly_ptr;

struct poly_node {
    int Coefficient;
    int Exponent;
    poly_ptr Next;
};

链表按 exponent 排序。

优点：

• 只存非零项，适合 sparse polynomial。
• 多项式加法可以像 merge sorted lists 一样做。

如果两个多项式分别有 $m,n$ 个非零项：

其中 $m,n$ 是非零项个数，不是最高次数。

15. Multilists#

15.1 动机#

PPT 例子：

40,000 students
2,500 courses

需要：

1. Print the students' name list for each course.
2. Print the registered classes' list for each student.

如果用二维数组：

int Array[40000][2500];

空间巨大：

并且很多位置可能为空。

15.2 Multilist 思想#

每个 registration record 同时属于两条链：

• 某个学生的课程链。
• 某门课的学生链。

这样一个结点可以被两个方向访问。

适合场景：

• 稀疏关系。
• 需要同时按行和按列遍历。

PPT 让自学 sparse matrix representation，它和 multilist 是同类思想。

复杂度视具体操作而定：

• 按某个学生列出课程：$O(k_s)$，其中 $k_s$ 是该学生选课数。
• 按某门课列出学生：$O(k_c)$，其中 $k_c$ 是该课学生数。
• 空间复杂度：$O(R + S + C)$，其中 $R$ 是注册记录数，$S$ 是学生数，$C$ 是课程数。

16. Cursor Implementation of Linked Lists#

16.1 动机#

PPT 说 linked list 必须具备两个特征：

1. The data are stored in a collection of structures. Each structure contains data and a pointer to the next structure.
2. A new structure can be obtained from the system's global memory by malloc and released by free.

Cursor implementation 用数组下标模拟指针，不直接用真实 pointer。

16.2 结构#

PPT 表示：

struct Node {
    ElementType Element;
    int Next;
};

struct Node CursorSpace[SpaceSize];

其中：

• CursorSpace[i].Element 是数据。
• CursorSpace[i].Next 是下一个结点的数组下标。
• 0 号位置通常作为 freelist 的 header。

16.3 Cursor malloc#

PPT 伪代码：

p = CursorSpace[0].Next;
CursorSpace[0].Next = CursorSpace[p].Next;

含义：

• freelist 的第一个可用结点编号是 \(p\)。
• 把它从 freelist 中取出。

复杂度：

16.4 Cursor free#

PPT 伪代码：

CursorSpace[p].Next = CursorSpace[0].Next;
CursorSpace[0].Next = p;

含义：

• 把编号为 \(p\) 的结点重新挂回 freelist 头部。

复杂度：

PPT 说明：

The cursor implementation is usually significantly faster
because of the lack of memory management routines.

原因是它避免频繁调用系统级 malloc/free，但代价是需要预先估计 SpaceSize，且空间上限固定。

16.5 Cursor 与 Pointer 接口一致#

PPT 特别强调：

The interface for the cursor implementation is identical to the pointer implementation.

这正是 ADT 的意义：

• 外部操作接口不变。
• 内部表示可以从 pointer linked list 换成 cursor linked list。

17. List 实现复杂度总表#

选择原则：

• 需要大量随机访问：array list。
• 需要频繁在已知位置插入/删除：linked list。
• 需要频繁找前驱或删除当前结点：doubly linked list。
• 不想频繁系统 malloc/free 或语言环境没有指针：cursor implementation。

18. 从 List 到 Stack / Queue#

List ADT 允许比较一般的位置操作；Stack 和 Queue 可以看成对 List 操作位置施加限制后得到的 ADT。

因此下面的 Stack 和 Queue 不是新的孤立内容，而是 List ADT 在不同约束下的两种常用形态。

19. Stack ADT#

1.1 定义#

课程 PPT 的定义：

• A stack is a Last-In-First-Out (LIFO) list.
• It is an ordered list in which insertions and deletions are made at the top only.

也就是：

last in, first out

只能在栈顶插入和删除，所以最后压入的元素最先被弹出。

1.2 对象与操作#

对象：

• A finite ordered list with zero or more elements.

核心操作：

int IsEmpty(Stack S);
Stack CreateStack(void);
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);

PPT 特别说明：

• 对空栈执行 Pop 或 Top 是 stack ADT error。
• 对满栈执行 Push 是 implementation error，不是 ADT 本身的错误。

1.3 操作复杂度#

在正常的数组栈或链表栈中，栈顶位置可以直接访问，所以基本操作都是常数时间。

这里 $C$ 是数组容量，$N$ 是当前元素个数。若实现中使用动态扩容，单次 Push 可能是 $O(N)$，但摊还复杂度通常仍为 $O(1)$；课程 PPT 的数组实现按固定容量讨论。

20. Stack 的实现#

2.1 Linked List Implementation#

PPT 使用带 header node 的链表实现。

结构想法：

S(header) -> first node -> second node -> ... -> NULL

其中 \(S->Next\) 指向栈顶。

Push 的核心步骤：

TmpCell->Element = X;
TmpCell->Next = S->Next;
S->Next = TmpCell;

Top：

if (S->Next == NULL) {
    Error("Empty stack");
}
return S->Next->Element;

Pop：

if (S->Next == NULL) {
    Error("Empty stack");
} else {
    FirstCell = S->Next;
    S->Next = S->Next->Next;
    free(FirstCell);
}

复杂度：

• Push：$O(1)$。
• Top：$O(1)$。
• Pop：$O(1)$。

PPT 提醒：malloc 和 free 的调用比较贵。一个改进思路是维护另一个 stack 作为 recycle bin，把删除的结点暂存起来复用，减少频繁内存分配。

2.2 Array Implementation#

课程 PPT 的结构：

struct StackRecord {
    int Capacity;          /* size of stack */
    int TopOfStack;        /* top pointer */
    ElementType *Array;    /* array for stack elements */
};

约定：

• \(TopOfStack == -1\) 表示空栈。
• Push 时先 \(++TopOfStack\)，再写入元素。
• Pop 时删除当前栈顶，再 --TopOfStack。

典型代码：

void Push(ElementType X, Stack S) {
    if (IsFull(S)) {
        Error("Full stack");
    } else {
        S->Array[++S->TopOfStack] = X;
    }
}

ElementType Top(Stack S) {
    if (IsEmpty(S)) {
        Error("Empty stack");
    }
    return S->Array[S->TopOfStack];
}

void Pop(Stack S) {
    if (IsEmpty(S)) {
        Error("Empty stack");
    } else {
        S->TopOfStack--;
    }
}

PPT 强调：

1. Stack model must be well encapsulated.
2. 除了 stack routines，其他代码不应该直接访问 Array 或 TopOfStack。
3. Push、Pop、Top 前必须做 error check。

复杂度：

• Push：$O(1)$。
• Top：$O(1)$。
• Pop：$O(1)$。
• 初始化数组：分配容量为 $C$ 的数组，空间 $O(C)$。

21. Stack 的典型应用#

3.1 Balancing Symbols#

问题：

检查圆括号 ()、方括号 []、花括号 {} 是否匹配。

PPT 算法：

Make an empty stack S;

while (read in a character c) {
    if (c is an opening symbol) {
        Push(c, S);
    } else if (c is a closing symbol) {
        if (S is empty) {
            ERROR;
            exit;
        } else {
            if (Top(S) doesn't match c) {
                ERROR;
                exit;
            } else {
                Pop(S);
            }
        }
    }
}

if (S is not empty) {
    ERROR;
}

核心不变量：

• 栈中保存的是“已经出现但尚未匹配”的 opening symbols。
• 当前 closing symbol 必须匹配最近的 opening symbol，所以用栈。

复杂度：

每个字符最多入栈一次、出栈一次。

空间复杂度：

最坏情况下，表达式前半段全是 opening symbols。

PPT 说明这是一个 on-line algorithm，因为读到当前位置就能发现一部分错误，不需要等所有输入都读完。

3.2 Postfix Evaluation#

PPT 示例：

infix:   a + b * c - d / e
prefix:  - + a * b c / d e
postfix: a b c * + d e / -

Postfix expression 又叫 Reverse Polish notation。

后缀表达式求值算法：

1. 从左到右扫描 token。
2. 遇到 operand，压栈。
3. 遇到 operator，弹出两个 operand。
4. 计算结果，再把结果压回栈。
5. 扫描结束后，栈顶就是最终结果。

注意弹出顺序：

left operand  = second pop
right operand = first pop

例如处理 a b -：

先弹出 b，再弹出 a，计算 a - b

PPT 示例：

6 2 / 3 - 4 2 * +

计算过程：

6 2 /       -> 3
3 3 -       -> 0
4 2 *       -> 8
0 8 +       -> 8

复杂度：

PPT 强调：postfix evaluation 不需要知道 precedence rules，因为运算顺序已经体现在表达式里。

空间复杂度：

最坏情况下会有很多 operand 连续入栈。

3.3 Infix to Postfix Conversion#

目标：

把中缀表达式转成后缀表达式，方便后续用栈求值。

PPT 例子：

a + b * c - d

转换结果：

a b c * + d -

两个基本观察：

1. Operands 在 infix 和 postfix 中的相对顺序不变。
2. 优先级高的 operators 在 postfix 中应该更早出现。

算法思想：

• operand：直接输出。
• operator：和栈顶 operator 比较优先级，必要时弹出栈顶并输出，再把当前 operator 入栈。
• left parenthesis (：入栈。
• right parenthesis )：不断弹栈输出，直到遇到 (；然后丢弃这一对括号。
• 输入结束：把栈中剩余 operators 全部弹出输出。

伪代码：

for each token x in input {
    if (x is operand) {
        output x;
    } else if (x == '(') {
        Push(x, S);
    } else if (x == ')') {
        while (Top(S) != '(') {
            output Top(S);
            Pop(S);
        }
        Pop(S);  /* discard '(' */
    } else if (x is operator) {
        while (!IsEmpty(S) &&
               Top(S) is operator &&
               precedence(Top(S)) >= precedence(x)) {
            output Top(S);
            Pop(S);
        }
        Push(x, S);
    }
}

while (!IsEmpty(S)) {
    output Top(S);
    Pop(S);
}

复杂度：

因为每个 token 最多入栈一次、出栈一次。

空间复杂度：

栈中保存尚未输出的 operators 和 left parentheses。

3.4 Parentheses 与优先级细节#

PPT 的第二个例子：

a * ( b + c ) / d

转换结果：

a b c + * d /

难点在于 (：

1. 除非正在处理 )，否则不要从栈中弹出 (。
2. 当 ( 还没有入栈时，它作为 incoming symbol 应该有最高优先级，这样能直接入栈。
3. 当 ( 已经在栈中时，它作为 in-stack symbol 应该有最低优先级，这样不会阻止后面的运算符入栈。

所以 PPT 建议区分：

• in-stack precedence
• incoming precedence

结合性也要小心：

• \(a - b - c\) 应转换成 \(a b - c -\)，因为减法左结合。
• \(2 ^ 2 ^ 3\) 应转换成 \(2 2 3 ^ ^\)，不是 \(2 2 ^ 3 ^\)，因为指数运算右结合。

本仓库里的参考实现：

• w3_stack_and_queue/mid_to_post.c

它处理 \(+ - * /\) 和括号，核心逻辑就是“优先级不低于当前运算符的栈顶运算符先弹出”。

3.5 Function Calls: System Stack#

函数调用也依赖栈。

每一次函数调用都会形成一个 stack frame，通常包含：

• return address
• local variables
• old frame pointer
• 参数和临时状态

PPT 中的递归例子：

void PrintList(List L) {
    if (L != NULL) {
        PrintElement(L->Element);
        PrintList(L->Next);
    }
}

这是 tail recursion，但 PPT 说它是 a bad use of recursion。

原因：

• 如果链表有 1 million elements，递归深度可能达到 $N$。
• 每一层递归都占用系统栈空间。
• 输入足够大时可能 stack overflow。

时间复杂度：

空间复杂度：

如果改成迭代：

while (L != NULL) {
    PrintElement(L->Element);
    L = L->Next;
}

时间复杂度仍是：

但额外空间变成：

PPT 的结论：

• Recursion can always be completely removed.
• Non-recursive programs are generally faster than equivalent recursive programs.
• However, recursive programs are generally simpler and easier to understand.

22. Queue ADT#

4.1 定义#

课程 PPT 的定义：

• A queue is a First-In-First-Out (FIFO) list.
• It is an ordered list in which insertions take place at one end and deletions take place at the opposite end.

也就是：

first in, first out

入队发生在队尾，出队发生在队首。

4.2 对象与操作#

核心操作：

int IsEmpty(Queue Q);
Queue CreateQueue(void);
void DisposeQueue(Queue Q);
void MakeEmpty(Queue Q);
void Enqueue(ElementType X, Queue Q);
ElementType Front(Queue Q);
void Dequeue(Queue Q);

常见扩展：

ElementType FrontAndDequeue(Queue Q);
int IsFull(Queue Q);

4.3 操作复杂度#

只要实现中直接维护 Front 和 Rear，队列基本操作都是常数时间。

这里 $C$ 是数组容量，$N$ 是当前元素个数。

23. Queue 的实现#

5.1 Linked List Implementation#

PPT 只说 linked list implementation is trivial。

典型做法是维护两个指针：

typedef struct QueueNode *PtrToNode;

struct QueueNode {
    ElementType Element;
    PtrToNode Next;
};

struct QueueRecord {
    PtrToNode Front;
    PtrToNode Rear;
};

入队：

Rear->Next = NewNode;
Rear = NewNode;

出队：

OldFront = Front;
Front = Front->Next;
free(OldFront);

空队列需要特殊处理，因为第一个元素入队时 Front 和 Rear 都要指向它；最后一个元素出队后 Rear 也要置空。

复杂度：

• Enqueue：$O(1)$。
• Front：$O(1)$。
• Dequeue：$O(1)$。

5.2 Array Implementation#

课程 PPT 的结构：

struct QueueRecord {
    int Capacity;          /* max size of queue */
    int Front;             /* the front pointer */
    int Rear;              /* the rear pointer */
    int Size;              /* optional: current size of queue */
    ElementType *Array;    /* array for queue elements */
};

如果只是普通数组，每次 Dequeue 后都把后面所有元素前移，会导致：

这不是课程想要的队列实现。

正确想法是：

• 不移动元素。
• 只移动 Front 和 Rear 指针。
• 数组末尾用完后回到数组开头，即 circular queue。

5.3 Circular Queue#

循环队列把数组下标看成一个环：

static int Succ(int Value, Queue Q) {
    if (++Value == Q->Capacity) {
        Value = 0;
    }
    return Value;
}

一种常见约定：

• Front 指向队首元素。
• Rear 指向下一个可写位置。
• \(Front == Rear\) 表示空。
• \((Rear + 1) % Capacity == Front\) 表示满。

入队：

void Enqueue(ElementType X, Queue Q) {
    if (IsFull(Q)) {
        Error("Full queue");
    } else {
        Q->Array[Q->Rear] = X;
        Q->Rear = (Q->Rear + 1) % Q->Capacity;
    }
}

出队：

void Dequeue(Queue Q) {
    if (IsEmpty(Q)) {
        Error("Empty queue");
    } else {
        Q->Front = (Q->Front + 1) % Q->Capacity;
    }
}

读取队首：

ElementType Front(Queue Q) {
    if (IsEmpty(Q)) {
        Error("Empty queue");
    }
    return Q->Array[Q->Front];
}

复杂度：

• Enqueue：$O(1)$。
• Dequeue：$O(1)$。
• Front：$O(1)$。
• 空间：$O(C)$。

5.4 为什么有空位却说队满#

PPT 的问题：

Why is the queue announced full while there is still a free space left?

原因：

• 如果只用 Front 和 Rear 两个指针，并且规定 \(Front == Rear\) 表示 empty；
• 那么满队列时也可能出现 \(Front == Rear\)；
• 为了区分 empty 和 full，循环队列常故意浪费一个空位。

因此：

empty: Front == Rear
full:  (Rear + 1) % Capacity == Front

这时数组容量为 Capacity，最多只能放：

个元素。

PPT 提到：Adding a Size field can avoid wasting one empty space.

如果维护 Size：

empty: Size == 0
full:  Size == Capacity

这样可以使用所有数组位置，但每次 Enqueue 和 Dequeue 都要同步更新 Size。

复杂度仍然是：

5.5 队列实现易错点#

24. Queue 的典型应用#

6.1 Job Scheduling#

PPT 示例是 operating system 中的 job scheduling。

任务按到达顺序进入队列：

Enqueue Job 1
Enqueue Job 2
Enqueue Job 3
Dequeue Job 1
Enqueue Job 4
...

含义：

• 新任务从队尾进入。
• 最早等待的任务从队首被处理。

每个任务入队一次、出队一次：

队列操作本身：

6.2 Level-order Traversal#

树的层序遍历需要队列。

算法：

void LevelOrder(Tree T) {
    Queue Q = CreateQueue();
    if (T != NULL) {
        Enqueue(T, Q);
    }

    while (!IsEmpty(Q)) {
        Tree Cur = Front(Q);
        Dequeue(Q);
        visit(Cur);

        if (Cur->Left != NULL) {
            Enqueue(Cur->Left, Q);
        }
        if (Cur->Right != NULL) {
            Enqueue(Cur->Right, Q);
        }
    }
}

复杂度：

每个结点入队一次、出队一次。

空间复杂度：

其中 $W$ 是树的最大宽度，最坏可以是 $O(N)$。

本仓库里可以参考：

• w4_binary_tree/best_zigzag.c
• midtermreview/binary_tree.c
• w6_binary_heap/complete binary search tree.c

这些代码都用数组模拟队列来做层序处理。

6.3 BFS#

图的广度优先搜索也使用队列。

基本模板：

void BFS(Vertex S) {
    Mark[S] = true;
    Enqueue(S, Q);

    while (!IsEmpty(Q)) {
        Vertex V = Front(Q);
        Dequeue(Q);

        for (each neighbor W of V) {
            if (!Mark[W]) {
                Mark[W] = true;
                Enqueue(W, Q);
            }
        }
    }
}

邻接表实现下：

空间复杂度：

队列保证按距离从近到远扩展，所以 BFS 可以求无权图的最短路径层数。

6.4 Bonus Problem: LRU-K#

PPT 最后一页提到 Bonus Problem 1：LRU-K。

本仓库中的参考代码：

• bonus/bonus1.c

它维护两个队列：

• history queue：访问次数还没有达到阈值 $K$ 的页面。
• cache queue：访问次数达到阈值 $K$ 后进入缓存的页面。

代码中还使用 hash_map[value] 直接定位队列结点，使删除指定页面不需要线性扫描。

核心操作：

所以对 $M$ 次访问，若哈希定位均摊 $O(1)$，总复杂度近似：

空间复杂度：

其中 $N$ 是队列容量，$U$ 是页面 ID 范围或哈希表大小。

25. 栈与队列对比#

共同点：

• 都是受限的线性表。
• 如果直接维护关键位置指针，基本操作都是 $O(1)$。
• 都常用数组或链表实现。

区别：

• 栈关心“最近的对象”。
• 队列关心“最早的对象”。

26. 总复杂度速查#

27. 考试抓手#

1. 复杂度题先写输入规模，再看循环次数、递归式和是否重复扫描。
2. ADT 题先写对象和操作，再比较不同表示法的复杂度。
3. List 题重点看数组移动、链表指针顺序、dummy head node、previous 的代价。
4. Stack 题重点看“最近未匹配”：括号、运算符、递归调用。
5. Queue 题重点看“最早等待”：循环队列、层序遍历、BFS。