HL🌱数字花园

第三章栈、队列和数组

2024年9月22日11分钟阅读

第三章栈、队列和数组

3.1 栈

定义

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

特点：先进后出，后进先出

栈顶、栈底、空栈

基本操作

InitStack (&S)：初始化栈。构造一个空栈 S，分配内存空间。

DestroyStack (&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。

Push (&S, x)：进栈，若栈 S 未满，则将 x 加入使之成为新栈顶。

Pop (&S,&x)：出栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回。

GetTop (S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素

栈的顺序存储结构

实现

  1. 栈顶指针: S.top 栈顶元素: S.data[S.top]

  2. 进栈: 指针先加 1, 再送值到栈顶元素

  3. 出栈: 先取栈顶元素值, 再将栈顶指针减 1

共享栈

  1. 定义: 将两个栈的栈底设置在共享空间的两端, 两个栈顶向中间延伸

  2. 判空: top 0=-1 top 1=MaxSize

  3. 判满: top 1-top 0=1

  4. 进栈: top 0 先加 1 再赋值, top 1 先减 1 再赋值, 出栈相反

栈的链式存储结构

优点: 便于多个栈共享储存空间, 提高其效率, 不会栈满上溢

特点：所有操作在表头进行, 通常没有头结点, 将头指针作为栈顶指针, 便于结点插入 / 删除

3.2 队列

定义

队列（Queue）是只允许 在一端进行插入（入队），在另一端删除（出队） 的线性表

队头、队尾、空队列

特点：先进先出

队列的基本操作

InitQueue (&Q)：初始化队列，构造一个空队列 Q。

DestroyQueue (&Q)：销毁队列。销毁并释放队列 Q 所占用的内存空间。

EnQueue (&Q, x)：入队，若队列 Q 未满，将 x 加入，使之成为新的队尾。

DeQueue (&Q,&x)：出队，若队列 Q 非空，删除队头元素，并用 x 返回。

GetHead (Q,&x)：读队头元素，若队列 Q 非空，则将队头元素赋值给 x

队列的顺序存储结构

实现

  1. 两个指针: front 指示队头元素, rear 指向队尾元素下一个位置

  2. 初始状态 (队空): Q.front Q.rear0

  3. 进队: 先送值到队尾元素, 再将队尾指针加 1

  4. 出队: 先取队头元素值, 再将队头指针加 1

  5. 存在假溢出

队列的链式存储结构

适合数据元素变动较大的情形, 不存在队满溢出, 多个队列不存在存储分配不合

双端队列

只允许从两端插入、两端删除的线性表

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

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

3.3 栈和队列的应用

3.3.1 栈在括号匹配中的应用

最后出现的左括号最先被匹配

  1. 设置一个空栈, 顺序读入括号

  2. 若为 ) , 与栈顶 ( 配对出栈或者不合法

  3. 若为 ( , 作为新的更急迫的期待压入栈中

  4. 算法结束, 栈为空, 否则括号序列不匹

3.3.2 栈在表达式求值中的应用

中缀转后缀

中缀转后缀的手算方法

① 确定中缀表达式中各个运算符的运算顺序

② 选择下一个运算符，按照 「左操作数右操作数运算符」 的方式组合成一个新的操作数

③ 如果还有运算符没被处理，就继续 ②

“左优先” 原则：只要左边的运算符能先计算，就优先算左边的可保证运算顺序唯一

后缀表达式的手算方法： 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数

中缀转后缀的机算方法

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。

从左到右处理各个元素，直到末尾。可能遇到三种情况：

① 遇到操作数。直接加入后缀表达式。

② 遇到界限符。遇到 “(” 直接入栈；遇到 “)” 则依次弹出栈内运算符并加入后缀表达式，直到弹出 “(” 为止。注意：“(”不加入后缀表达式。

③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 “(” 或栈空则停止。之后再把当前运算符入栈

后缀表达式计算（算法实现）

用栈实现后缀表达式的计算：

①从左往右扫描下一个元素，直到处理完所有元素

②若扫描到操作数则压入栈，并回到①；否则执行③

③若扫描到运算符，则弹出两个栈顶元素（先出栈的为右操作数），执行相应运算，运算结果压回栈顶，回到①

中缀表达式计算（栈实现） 中缀转后缀 + 后缀表达式求值

  1. 初始化两个栈，操作数栈和运算符栈
  2. 若扫描到操作数，压入操作数栈
  3. 若扫描到运算符或界限符，则按照 “中缀转后缀” 相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

中缀转前缀

中缀转前缀的手算方法：

① 确定中缀表达式中各个运算符的运算顺序

② 选择下一个运算符，按照 「运算符左操作数右操作数」 的方式组合成一个新的操作数

③ 如果还有运算符没被处理，就继续 ②

“右优先” 原则：只要右边的运算符能先计算，就优先算右边的

前缀表达式计算（算法实现）

用栈实现前缀表达式的计算：

①从右往左扫描下一个元素，直到处理完所有元素

②若扫描到操作数则压入栈，并回到①；否则执行③

③若扫描到运算符，则弹出两个栈顶元素（先弹出的为左操作数），执行相应运算，运算结果压回栈顶，回到①

3.3.3 栈在递归中的应用

函数调用的特点：最后被调用的函数最先执行结束（LIFO）

函数调用时，需要用一个栈存储： ① 调用返回地址 ② 实参 ③ 局部变量

递归 ：可以把原始问题转换为属性相同，但规模较小的问题

两个条件 1. 递归表达式 (递归体) 2. 边界条件 (递归出口)

递归调用时，函数调用栈可称为 “递归工作栈” 每进入一层递归，就将递归调用所需信息压入栈顶每退出一层递归，就从栈顶弹出相应信

缺点：效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算

3.3.4 队列的应用

在层次遍历中的应用

  1. 树的遍历
  2. 图的广度优先遍历

在计算机系统中的应用

  1. FCFS 先来先服务

  2. 解决主机与外部设备之间速度不匹配的问题

  3. 解决由多用户引起的资源竞争问题

3.4 数组和特殊矩阵

3.4.1 数组

数组 ：由 n（n>=1）个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素

数组是线性表的推广

数组地址计算

  1. 一维数组

  1. 二维数组–行优先

  1. 二维数组–列优先

3.4.2 特殊矩阵的压缩存储

压缩存储: 多个值相同的元素只分配一个空间, 0 不分配空间

对称矩阵的压缩存储

若 n 阶方阵中任意一个元素 ai, j 都有 ai, j = aj, i 则该矩阵为对称矩阵

三角矩阵的压缩存储

下三角矩阵：除了主对角线和下三角区，其余的元素都相同

上三角矩阵：除了主对角线和上三角区，其余的元素都相同

三对角矩阵的压缩存储

稀疏矩阵的压缩存储

压缩存储策略：

  1. 顺序存储——三元组 <行，列，值>
  2. 链式存储——十字链表法

关系图谱

反向链接