栈与队列¶

线性表¶

数组实现
链表实现
- 哨兵链表，双向循环链表
补充，稀疏矩阵（sparse matrix）是大部分元素均为 0 的矩阵
- 多维数组实现，空间浪费严重
- 多重链表（multilist）实现，也称十字链表（orthogonal linked list）
补充，链表的游标实现（no pointer）
- 使用全局结构体数组来实现链表，维护其中一个分区 freelist 来实现 malloc 和 free

栈和队列基础¶

栈（stack）是 last-in-first-out (LIFO) 的

struct Stack {
    int capacity;
    int topOfStack;
    ElementType *array;
}

栈的基本操作：
- 入栈（push），将元素压入栈顶
- 出栈（pop），将栈顶元素出栈
- 查看栈顶元素（top）
栈的实现：
- 数组实现
  - 自下而上，数组下标为栈顶
  - 注意栈满时的处理
- 链表实现
  - 自上而下，头节点为栈顶
  - 注意malloc和free(create a recycle bin)

队列（queue）是 first-in-first-out (FIFO) 的

struct Queue {
    int capacity;
    int front, rear;
    ElementType *array;
}

队列的基本操作：
- 入队（enqueue），在队尾插入元素
- 出队（dequeue），在队首弹出元素
队列实现
- 数组实现
  - 注意队满和队空时的处理
- 链表实现
循环队列
- 通过取模运算实现循环
- 注意队满和队空时的处理

中缀、后缀与前缀¶

后缀（postfix）表达式，所有操作符置于操作数的后面
- 后缀表达式不再考虑运算符的优先级，也不需要括号
后缀表达式求值，\(\Omicron(N)\)，维护一个操作数栈
1. 读到操作数，入栈
2. 读到操作符，将栈顶前两个操作数依次出栈，进行运算，并把运算结果入栈
3. 表达式读完后，将栈顶元素出栈，即为表达式的值
中缀表达式转后缀表达式，维护一个操作符栈
1. 读到操作数，直接输出
2. 读到操作符，将其与栈顶操作符比较优先级
  - pre(top) >= pre(tmp)，栈顶操作符出栈，并重复步骤 b.
  - pre(top) < pre(tmp) 或者栈为空，操作符直接入栈
  - 注意，读到左括号直接入栈，读到右括号将栈中元素依次出栈直至左括号，丢弃这对括号
  - 注意，上述针对左结合操作符，对于右结合操作符（如 \(\text{\textasciicircum}\)），优先级相等时直接入栈
3. 表达式读完后，将栈中元素全部依次出栈
前缀（prefix）表达式，所有操作符置于操作数的前面
- 前缀表达式不再考虑运算符的优先级，也不需要括号
前缀表达式求值，和后缀求值基本一致，唯一区别是前缀自右向左扫描表达式
中缀表达式转前缀表达式，和中缀转后缀基本一致，区别如下：
- 自右向左扫描表达式
- 左括号和右括号相反
- 左结合操作符和右结合操作符相反，体现在优先级相等时的处理
表达式树（expression tree）是一种二叉树，叶子节点均为操作数，其余节点均为操作符
中缀表达式建树，维护两个栈，optr 栈存储操作符，expt 栈存储表达式树根节点
1. 读到操作数，生成一个只有根节点的表达式树，入栈 expt
2. 读到操作符，将其与 optr 栈顶操作符比较优先级
  - pre(top) >= pre(tmp)，栈顶操作符出栈，将 expt 栈顶前两棵树出栈，生成以该操作符为根节点、以这两棵树为左右子树的表达式树，入栈 expt；重复步骤 b.
  - pre(top) < pre(tmp) 或者栈为空，操作符直接入栈
  - 注意，读到左括号直接入栈，读到右括号将栈中元素依次出栈直至左括号，丢弃这对括号
  - 注意，上述针对左结合操作符，对于右结合操作符（如 \(\text{\textasciicircum}\)），优先级相等时直接入栈
3. 表达式读完后，将 expt 栈顶元素出栈，即为表达式树

最后更新: 2024年10月2日 14:45:20
创建日期: 2024年3月9日 08:53:42