栈的基本概念

栈的定义：

  • 栈（Stack）是只允许在一端进行插入或删除操作的线性表
  • 逻辑结构：与普通线性表相同
  • 数据的运算：插入、删除操作有区别
  • 栈顶：允许插入和删除的一端，对应元素被称为栈顶元素
  • 栈底：不允许插入和删除的一端，对应元素被称为栈底元素
  • 特点：后进先出Last In First Out（LIFO）

栈的基本操作：

  • 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个不同元素进栈，出栈元素不同排列的个数为image-20220627140503701
  • 上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明

栈的顺序存储结构

顺序栈的定义和初始化：

image-20220627140718709

进栈操作：

image-20220627141553163

出栈操作：

image-20220627141642971

读取栈顶元素：

image-20220627141856313

注意：也可以让栈顶指针top先指向0，每次进栈S.top++，出栈--S.top

共享栈：

  • 使用静态数组要求提前规定好栈的大小，容易造成内存资源的浪费因此共享栈应运而生
  • 两个栈共享同一片空间，0、1号栈朝着同一方向进栈
  • 栈满的条件：top0 + 1 == top1

image-20220627142538149

image-20220627142525712

栈的链式存储结构

栈的链式存储实质：

  • 进栈：头插法建立单链表，也就是对头结点的后插操作
  • 出栈：单链表的删除操作，对头结点的“后删”操作
  • 推荐使用不带头结点的链栈
  • 创销增删查的操作参考链表

链栈的定义：

image-20220627150312131

队列的基本概念

队列的定义：

  • 栈（Stack）是只允许在一端进行插入或删除操作的操作受限的线性表
  • 队列（Queue）是只允许在一端进行插入，在另一端删除的线性表
  • 队头：允许删除的一端，对应的元素被称为队头元素
  • 队尾：允许插入的一端，对应的元素被称为队尾元素
  • 队列的特点：先进先出First In First Out（FIFO）

队列的基本操作：

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

队列的顺序存储结构

队列的定义和初始化：

image-20220627153045734

入队操作：

image-20220627153645337

  • 通过取余操作，只要队列不满，就可以一直利用之前已经出队了的空间，逻辑上实现了循环队列的操作
  • 于是，队列已满的条件：队尾指针的再下一个位置是队头，即(Q.rear+1)%MaxSize==Q.front
  • 代价：牺牲了一个存储单元，因为如果rear和front相同，与判空的条件相同了

出队操作：

image-20220627171724686

实际上获取队头元素的值就是出队操作去掉队头指针后移的代码

判断队列已满/已空：

方案1：

  • 使用前面讲的牺牲一个存储空间的方式来解决
  • 初始化时rear=front=0
  • 队列元素个数：(rear+MaxSize-front)%MaxSize
  • 队列已满的条件：队尾指针的再下一个位置是队头，即(Q.rear+1)%MaxSize==Q.front
  • 队空条件：Q.rear==Q.front

方案2：

  • 不牺牲一个存储空间，在结构体中多建立一个变量size
  • 初始化时rear=front=0；size = 0;
  • 队列元素个数= size
  • 插入成功size++；删除成功size--;
  • 此时队满条件：size==MaxSize
  • 队空条件：size == 0;

方案3：

  • 不牺牲一个存储空间，在结构体中多建立一个变量tag
  • 初始化时rear=front=0；tag = 0;
  • 因为只有删除操作，才可能导致队空，只有插入操作，才可能导致队满因此
  • 每次删除操作成功时，都令tag=0；
  • 每次插入操作成功时，都令tag=1；
  • 队满条件：front==rear && tag == 1
  • 队空条件：front==rear && tag == 0
  • 队列元素个数：(rear+MaxSize-front)%MaxSize

队列的链式存储结构

初始化（带头结点）：

image-20220627174630688

初始化（不带头结点）：

image-20220627174715478

入队（带头结点）：

image-20220627180628318

入队（不带头结点）：

image-20220627180722979

出队（带头结点）：

image-20220627180803329

出队（不带头结点）：

image-20220627180859275

队列满的条件：

  • 顺序存储：预分配的空间耗尽时队满
  • 链式存储：一般不会队满，除非内存不足
  • 因此一般不用考虑队满

双端队列

定义：

  • 双端队列：只允许从两端插入、两端删除的线性表
  • 输入受限的双端队列：只允许从一端插入、两端删除的线性表
  • 输出受限的双端队列：只允许从两端插入、一端删除的线性表
  • 不管是怎么样的双端队列实际都是栈和队列的变种

考点：

  • 判断输出序列合法性
  • 在栈中合法的输出序列，在双端队列中必定合法

栈在括号匹配中的应用

括号匹配问题：

image-20220627201914734

  • 若有括号无法被匹配则出现编译错误
  • 遇到左括号就入栈
  • 遇到右括号，就“消耗”一个左括号

代码实现：

image-20220627202358904

栈在表达式求值中的应用

算数表达式：

  • 由三个部分组成：操作数、运算符、界限符
  • 我们平时写的算术表达式都是中缀表达式
  • 如何可以不用界限符也能无歧义地表达运算顺序
  • Reverse Polish notation（逆波兰表达式=后缀表达式）
  • Polish notation（波兰表达式=前缀表达式）

中缀、后缀、前缀表达式：

image-20220627203834383

中缀转后缀的方法（手算）：

  • 确定中缀表达式中各个运算符的运算顺序
  • 选择下一个运算符，按照「左操作数右操作数运算符」的方式组合成一个新的操作数
  • 如果还有运算符没被处理，就继续第二步
  • 注意：运算顺序不唯一，因此对应的后缀表达式也不唯一
  • “左优先”原则：只要左边的运算符能先计算，就优先算左边的，保证手算和机算是一致的

image-20220627203754570

中缀表达式转后缀表达式（机算，用栈实现）：

  • 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
  • 从左到右处理各个元素，直到末尾。可能遇到三种情况：
    • 遇到操作数。直接加入后缀表达式。
    • 遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意：“(”不加入后缀表达式。
    • 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。
  • 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式的计算（手算）：

  • 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
  • 注意：两个操作数的左右顺序
  • 特点：最后出现的操作数先被运算，LIFO（后进先出），可以使用栈来完成这个步骤
  • “左优先”原则：只要左边的运算符能先计算，就优先算左边的

后缀表达式的计算（机算，用栈实现）：

  • 从左往右扫描下一个元素，直到处理完所有元素
  • 若扫描到操作数则压入栈，并回到第一步；否则执行第三步
  • 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步
  • 注意：先出栈的是“右操作数”
  • 若表达式合法，则最后栈中只会留下一个元素，就是最终结果
  • 后缀表达式适用于基于栈的编程语言（stack-orientedprogramming language），如：Forth、PostScript

中缀表达式转前缀表达式（手算）：

  • 确定中缀表达式中各个运算符的运算顺序
  • 选择下一个运算符，按照「运算符左操作数右操作数」的方式组合成一个新的操作数
  • 如果还有运算符没被处理，就继续第二步
  • “右优先”原则：只要右边的运算符能先计算，就优先算右边的

中缀表达式的计算（机算，用栈实现）：

  • 中缀表达式的计算=中缀转后缀+后缀表达式求值，两个算法的结合
  • 用栈实现中缀表达式的计算：
    • 初始化两个栈，操作数栈和运算符栈
    • 若扫描到操作数，压入操作数栈
    • 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

栈在递归中的应用

函数调用的特点：

  • 最后被调用的函数最先执行结束（LIFO）
  • 函数调用时，需要用一个栈（函数调用栈）存储，里面包含以下信息：
    • 调用返回地址
    • 实参
    • 局部变量
  • 适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题

栈在递归中的应用：

  • 计算正整数的阶乘n!
  • 求斐波那契数列
  • ......

栈在递归中过程：

  • 递归调用时，函数调用栈可称为“递归工作栈”
  • 每进入一层递归，就将递归调用所需信息压入栈顶
  • 每退出一层递归，就从栈顶弹出相应信息
  • 缺点：
    • 太多层递归可能会导致栈溢出
    • 可能包含很多重复计算

队列的应用

  • 树的层次遍历
  • 图的广度优先遍历
  • 操作系统中的应用
    • 多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service，先来先服务）是一种常用策略。可以用队列实现
    • CPU资源的分配
    • 打印数据缓冲区

特殊矩阵的压缩储存

一维数组的存储结构：

  • 起始地址：LOC
  • 各数组元素大小相同，且物理上连续存放。
  • 数组元素a[i]的存放地址= LOC + i * sizeof(ElemType)

二维数组的存储结构：

  • 分为行优先和列优先，本质就是把二维的逻辑视角转换为内存中的一维储存
  • M行N列的二维数组b[M][N]中，若按行优先存储，则b[i][j]的存储地址= LOC + (i*N + j) * sizeof(ElemType)
  • M行N列的二维数组b[M][N]中，若按列优先存储，则b[i][j]的存储地址= LOC + ( j*M+ i ) * sizeof(ElemType)
  • 二维数组也有随机存储的特性

普通矩阵的存储：

  • 可用二维数组存储
  • 注意：描述矩阵元素时，行、列号通常从1开始；而描述数组时通常下标从0开始
  • 某些特殊矩阵可以压缩存储空间（比如对称矩阵）

对称矩阵的压缩存储：

  • 若n阶方阵中任意一个元素ai,j都有ai,j = aj,i则该矩阵为对称矩阵
  • 普通存储：n*n二维数组
  • 压缩存储策略：只存储主对角线+下三角区（或主对角线+上三角区），按行优先原则将各元素存入一维数组中
  • 数组大小应为多少：(1+n)*n/2
  • 站在程序员的角度，对称矩阵压缩存储后怎样才能方便使用：可以实现一个“映射”函数矩阵下标->一维数组下标
  • 按行优先的原则，ai,j是第几个元素：image-20220628001748003

三角矩阵的压缩存储：

  • 下三角矩阵：除了主对角线和下三角区，其余的元素都相同
  • 上三角矩阵：除了主对角线和上三角区，其余的元素都相同
  • 压缩存储策略：按行优先原则将橙色区元素存入一维数组中，并在最后一个位置存储常量c
  • 下三角矩阵，按行优先的原则，ai,j是第几个元素：image-20220628002543214
  • 上三角矩阵，按行优先的原则，ai,j是第几个元素：image-20220628002619268

三对角矩阵的压缩存储：

  • 三对角矩阵，又称带状矩阵：当|i - j|>1时，有ai,j = 0 （1≤ i, j ≤n）
  • 压缩存储策略：按行优先（或列优先）原则，只存储带状部分
  • 按行优先的原则，ai,j是第几个元素：image-20220628002928870
  • image-20220628003003647

稀疏矩阵的压缩存储：

  • 稀疏矩阵：非零元素远远少于矩阵元素的个数
  • 压缩存储策略1：顺序存储——三元组<i（行），j（列），v（值）>，失去了数组随机存储的特性
  • 压缩存储策略2：链式存储，十字链表法
    • image-20220628003342737

笔记完整PDF

百度网盘提取码：l3ja

赏