Skip to content

Latest commit

 

History

History
319 lines (221 loc) · 9.04 KB

README.md

File metadata and controls

319 lines (221 loc) · 9.04 KB

栈和队列

三要素：

  1. 逻辑结构
  2. 数据的运算
  3. 存储结构（物理结构）

栈和队列都是操作受限的线性表。

1. 栈

1.1. 定义

栈是只允许在一端进行插入或删除操作的线性表。

  • 栈顶：允许插入和删除的一端。
  • 栈底：不允许插入和删除的一端。
  • 空栈
  • 栈顶元素
  • 栈底元素

进栈顺序：

$$ a_1->a_2->a_3->a_4->a_5 $$

出栈顺序：

$$ a_5->a_4->a_3->a_2->a_1 $$

后进先出，Last In First OUT（LIFO）

1.2. 基本操作

  • InitStack(&S)：初始化栈。构造一个空栈 $S$，分配内存空间。
  • DestroyStack(&S)：销毁栈。销毁并释放栈 $S$ 所占用的内存空间。
  • Push(&S, x)：进栈。若栈 $S$ 未满，则将 $x$ 加入使之成为新栈顶。
  • Pop(&S, &x)：出栈，若栈 $S$ 非空，则弹出栈顶元素，并用 $x$ 返回。
  • GetTop(S, &x)：读栈顶元素。若栈 $S$ 非空，则用 $x$ 返回栈顶元素。
  • StackEmpty(S)：判断一个栈 $S$ 是否为空。若 $S$ 为空，则返回 true，否则返回 false。

$n$ 个不同的元素进栈，出栈元素的不同排列的个数为：

$$ \frac{1}{n+1} C^{n}_{2n} $$

上述公式称为 卡特兰（Catalan）数。可采用数学归纳法证明（不要求掌握）。

$$ \frac{1}{5+1} C^{5}_{10} =\frac{10 \times 9 \times 8 \times 7 \times 6}{6 \times 5 \times 4 \times 3 \times 2 \times 1} =42 $$

1.3. 顺序栈

顺序存储，用静态数据实现，并需要记录栈顶指针。

基本操作

两种实现

  • 初始化时 top=-1
  • 初始化时 top=0

共享栈

  • 两个栈共享同一片内存空间，两个栈从两边往中间增长。
  • 初始化：S.top0 = -1;，S.top1 = MaxSize;。
  • 栈满条件：S.top0 + 1 == S.top1;

1.4. 链栈

与单链表类似，只实现头插法、头结点出栈。

  • 带头结点的链栈
  • 不带头结点的链栈

2. 队列

2.1. 定义

队列是只允许在一端进行插入，在另一端删除操作的线性表。

  • 队头：允许删除的一端。
  • 队尾：允许插入的一端。
  • 空队列
  • 队头元素
  • 队尾元素

入队顺序：

$$ a_1->a_2->a_3->a_4->a_5 $$

出队顺序：

$$ a_1->a_2->a_3->a_4->a_5 $$

先进先出，First In First OUT（FIFO）

2.2. 基本操作

  • InitQueue(&Q)：初始化队列。构造一个空队列 $Q$，分配内存空间。
  • DestroyQueue(&Q)：销毁队列。销毁并释放队列 $Q$ 所占用的内存空间。
  • EnQueue(&Q, x)：入队。若队列 $Q$ 未满，则将 $x$ 加入使之成为新的队尾元素。
  • DeQueue(&Q, &x)：出队，若队列 $Q$ 非空，则弹出队头元素，并用 $x$ 返回。
  • GetHead(Q, &x)：读队头元素。若队列 $Q$ 非空，则用 $x$ 返回队头元素。
  • QueueEmpty(Q)：判断一个队列 $Q$ 是否为空。若 $Q$ 为空，则返回 true，否则返回 false。

2.3. 队列的顺序实现

实现思想：

  • 用静态数组存放数据元素，设置队头/队尾指针。
  • 循环队列：用模运算（取余）将存储空间在逻辑上变为环状。
  • Q.rear = (Q.rear + 1) % MaxSize;。

重要考点：

  • 如何初始化、入队、出队。
  • 如何判空、判满。
  • 如何计算队列的长度。

分析思路：

  • 确定 front，rear 指针的指向。
    • rear 指向队尾元素的后一个位置。
    • rear 指向队尾元素。
  • 确定判空、判满的方法。
    • 牺牲一个存储单元。
    • 增加 size 变量记录队列长度。
    • 增加 tag 变量用于标记最近一次操作是入队还是出队操作。
    • ...

2.4. 队列的链式实现

实现方式：

  • 带头结点
  • 不带头结点

基本操作：

  • 初始化队列
  • 入队
  • 出队
  • 获取队头元素
  • 判空
  • 判满？不存在的

获取队列长度，时间复杂度 $O(n)$。

如果频繁使用队列长度，可以设置一个变量 length。

3. 双端队列

3.1. 定义

双端队列：只允许从两端插入、两端删除的线性表。

输入受限的双端队列：只允许从一端插入、两端删除的线性表。

输出首先的双端队列：只允许从两端插入、一端删除的线性表。

3.2. 问题

若数据元素输入序列为：1，2，3，4，则哪些输出序列是合法的？哪些是非法的？

$$ A^{4}_{4}=4!=24 $$

3.2.1. 对栈合法的序列

1,x,x,x 2,x,x,x 3,x,x,x 4,x,x,x
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,1 3,4,1,2 4,3,1,2
1,5,3,2 2,4,3,3 3,4,2,1 4,3,2,1

卡特兰数：

$$ \frac{1}{n+1} C^{n}{2n} =\frac{1}{4+1} C^{5}{8} =14 $$

3.2.2. 对输入受限的双端队列合法的序列

1,x,x,x 2,x,x,x 3,x,x,x 4,x,x,x
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,1 3,4,1,2 4,3,1,2
1,5,3,2 2,4,3,3 3,4,2,1 4,3,2,1

3.2.3. 对输出受限的双端队列合法的序列

1,x,x,x 2,x,x,x 3,x,x,x 4,x,x,x
1,2,3,4 2,1,3,4 3,1,2,4 4,1,2,3
1,2,4,3 2,1,4,3 3,1,4,2 4,1,3,2
1,3,2,4 2,3,1,4 3,2,1,4 4,2,1,3
1,3,4,2 2,3,4,1 3,2,4,1 4,2,3,1
1,4,2,3 2,4,1,1 3,4,1,2 4,3,1,2
1,5,3,2 2,4,3,3 3,4,2,1 4,3,2,1

4. 栈的应用

4.1. 括号匹配

实现思路：

  1. 依次扫描所有字符。
  2. 遇到左括号入栈。
  3. 遇到右括号则弹出栈顶元素，检查是否匹配。

匹配失败的情况：

  • 左括号单身：所有括号都检查完了，但是栈非空。
  • 右括号单身：扫描到右括号，但是此时栈空。
  • 左右括号不匹配：栈顶左括号，与当前的右括号不匹配。

4.2. 表达式求值

三种算数表达式：

  • 中缀表达式
  • 后缀表达式
  • 前缀表达式

后缀表达式相关考点：

  • 中缀表达式转后缀表达式
  • 后缀表达式求值

前缀表达式相关考点：

  • 中缀表达式转前缀表达式
  • 前缀表达式求值

$$ 中缀表达式求值 = 中缀转后缀 + 后缀表达式求值 $$

4.3. 递归

实现递归表达式：

  • 递归表达式（递归体）
  • 边界条件（递归出口）

递归缺点：

  • 太多层递归可能会导致栈溢出。
  • 可能包含很多重复计算。

5. 队列的应用

  • 树的层次遍历
  • 图的广度优先遍历
  • 多个进程争抢着使用优先的系统资源时，FCFS（First Come First Service，先来先服务）是一种常用策略。

6. 矩阵的压缩存储

数组的存储结构：

特殊矩阵：

  • 对称矩阵
    • 特点：对方阵中的任意一个元素，有 $a_{i,j}=a_{j,i}$。
    • 压缩：只存主对角线+下三角区（或主对角线+上三角区）。
  • 三角矩阵
    • 特点：上三角区全为常量（下三角矩阵）；或下三角区全为常量（上三角矩阵）。
    • 压缩：按行优先/列优先规则依次存储非常量区域，并在最后一个位置存放常量 $c$。
  • 三对角矩阵
    • 特点：当 $|i-j|>1$ 时，$a_{i,j}=0$ （$1 \leq i, j \leq n$）。
    • 压缩：按行优先/列优先规则依次存储带状区域。
  • 稀疏矩阵
    • 特点：非零元素个数远少于零元素个数。
    • 压缩：只存储非零元素
      • 顺序存储：顺序存储三元组 <行，列，值>。
      • 链式存储：十字链表法。

常见考题：

  • 矩阵的压缩存储需要多长的数组。
  • 由矩阵行列号 $&lt;i,j&gt;$ 推出对应的数组下标号 $k$。
  • 由 $k$ 推出 $&lt;i,j&gt;$
    • 如何处理不等式中的“刚好大于等于/小于等于”。
    • “向上取整/向下取整”。
  • 易错点：
    • 存储上三角？下三角？
    • 行优先？列优先？
    • 矩阵元素的下标从 0？1？开始
    • 数组下标从 0？1？开始