《数据结构》第三章-栈、队列和数组

《数据结构》第三章-栈、队列和数组知识梳理，一张图带你完全了解相关内容，通过思维导图帮你提高效率，赶紧来试一试吧~

栈、队列和数组

• 栈
  • 基本概念
    • 定义
      • 栈是只允许在一端进行插入或删除操作的线性表（后进先出）
      • 栈顶：线性表允许进行插入删除的那一端
      • 栈底：不允许进行插入和删除的一端
      • 空栈：不含任何元素的空表
      • n个不同元素进栈，出栈元素不同排列的个数为：
    • 基本操作
      • Initstack (&S): 初始化一个空栈s
      • StackEmpty (S): 判断一个栈是否为空，若栈s为空则返回true，否则返回false
      • Push (&S, x): 进栈，若栈s未满，则将x加入使之成为新栈顶
      • Pop (&S, &x): 出栈，若栈s非空，则弹出栈顶元素，并用x返回
      • GetTop (s,&x): 读栈顶元素，若栈s非空，则用x返回栈顶元素
      • Destroystack (&S): 销毁栈，并释放栈s占用的存储空间(“&”表示引用调用)
  • 栈的顺序存储结构（顺序栈）
    • 顺序栈的实现
      • 利用一组地址连续的存储单位存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置
    • 顺序栈的基本操作
      • 
      • 初始化
      • 判栈空
      • 进栈
      • 出栈
      • 读栈顶元素
    • 共享栈
      • 利用栈底位置相对不变的特性，让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向空间的中间延伸
      • 判空
        • top0==-1
        • top1==MaxSize-1
      • 判满
        • top1-top0==1
  • 栈的链式存储结构（链栈）
    • 链栈没有头结点，Lhead指向栈顶元素
• 队列
  • 基本概念
    • 定义
      • 队列是只允许在表的一端进行插入，而在表的另一端进行删除的线性表（先进先出）
      • 入队：向队尾插入元素
      • 出队：在队头删除元素
    • 基本操作
      • InitQueue (&Q): 初始化队列，构造一个空队列Q
      • QueueEmpty (Q): 判队列空，若队列Q为空返回true，否则返回false
      • EnQueue (&Q,x): 入队，若队列Q未满，将x加入，使之成为新的队尾
      • DeQueue ( &Q,&x):出队，若队列Q非空，删除队头元素，并用x返回
      • GetHead (Q,&x):读队头元素，若队列Q非空，则将队头元素赋值给x
  • 队列的顺序存储结构
    • 队列的顺序存储
      • 存在“上溢出”现象
    • 循环队列
      • • 为了区分是队空还是队满的情况（两种情况都是Q.front=Q.rear），可采用三种方法： 牺牲一个单元格来区分队空还是队满，此时以“(Q.rear+1)%MaxSize == Q.front”作为队满条件 类型中增设表示元素个数的数据成员 类型增设tag数据成员，以区分队满还是队空 图中采用第一种方法
        • 初始时: Q. front=Q. rear=0。
        • 队首指针进1: Q. front=(Q. front+1)%MaxSize。
        • 队尾指针进1: Q. rear= (Q. rear+1)%MaxSize。
        • 队列长度（元素个数）: (Q. rear+MaxSize-Q. front)%MaxSize。
        • 出队入队时:指针都按顺时针方向进1 (如图3.7所示)
  • 队列的链式存储结构
    • 队列的链式存储
      • 链队列是一个同时带有队头指针和队尾指针的单链表
    • 基本操作
      • 初始化
      • 判队空
      • 入队
      • 出队
  • 双端队列
    • 
    • 在两端都可以进行入队和出队操作的队列
      • 前端进的元素排列在队列中后端进的元素的前面
      • 无论是前端还是后端出队，先出的元素排列在后出元素的前面
    • 输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列
      • tips：以首元素为界，看两边的元素是否有序（即插入顺序的正序或逆序），即可判断是否是合适的出队顺序
    • 输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列
      • tips：在双端删除元素类似于出栈（后进先出），在单端删除类似于出队（先进先出）
• 栈和队列的应用
  • 栈
    • 栈在括号匹配中的应用
      • 初始设置一个空栈，顺序读入括号。
      • 若是右括号，则或者使置于栈顶的最急迫期待得以消解，或者是不合法的情况（括号序列不匹配，退出程序)。
      • 若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性降了一级。算法结束时，栈为空，否则括号序列不匹配。
    • 栈在表达式求值中的应用
      • 中缀表达式→后缀表达式
        • 用栈存放暂时还不确定运算次序的操作符，icp表示当前扫描到的运算符ch的优先级，该运算符进栈后的优先级为isp
        • 转换过程
          • 1||| 在表达式开头和末尾添加“#”
          • 2||| 从左向右开始扫描中缀表达式
            • 若为数字，加入后缀表达式
            • 若为运算符
              • 若为‘（’，入栈
              • 若为‘）’，则依次把栈中的运算符加入后缀表达式，直到出现‘（’，从栈中删除‘（’
              • 若为除括号外的其他运算符，当其优先级高于除'（'外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或遇到了一个左括号为止。
                • PS：只有优先级更高的符号才能压入栈顶
          • 3||| 当扫描的中缀表达式结束时，栈中的所有运算符依次出栈并加入后缀表达式
      • 后缀表达式
        • 求值过程
          • 1||| 顺序扫描表达式的每一项，然后根据它的类型做如下相应操作
            • 若该项是操作数，则将其压入栈中
            • 若该项是操作符<op>,则连续从栈中退出两个操作数Y和X，形成运算指令X<op>Y，并将计算结果重新压入栈中
          • 2||| 当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果
    • 栈在递归中的应用
      • 递归：在一个函数、过程或数据结构的定义中又应用了它自身
        • 递归体：递归表达式
        • 递归出口：边界条件
        • 本质：将原始问题转换为属性相同但规模较小的问题
  • 队列
    • 队列在层次遍历中的应用
      • 过程
        • 1||| 根结点入队。
        • 2||| 若队空（所有结点都已处理完毕)，则结束遍历；否则重复③操作。
        • 3||| 队列中第一个结点出队,并访问之。若其有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回②。
    • 队列在计算机系统中的应用
      • 解决主机与外部设备之间速度不匹配的问题
        • 设置打印缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则以此从该缓冲区中取出数据
      • 解决由多用户引起的资源竞争问题
• 数组和特殊矩阵
  • 数组
    • 定义：由n个相同类型的数据元素构成的有限序列，是线性表的推广
    • 存储结构
      • 一维数组
      • 多维数组
        • 行优先
        • 列优先
  • 特殊矩阵的压缩存储
    • 定义
      • 压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间
      • 特殊矩阵：指具有许多相同矩阵元素或零元素，并使其分布有一定规律性的矩阵，
    • 分类
      • 对称矩阵
        • 将对称矩阵A[1...n][1...n]存放在一维数组B[(n(n+1)/2]中，只存放下三角部分（含对角线）的元素
      • 三角矩阵
        • 下三角矩阵（上三角区的所有元素均为同一常量）
          • 类似对称矩阵，存储完下三角区和主对角线上的元素后，再存储一次上三角区的常量，将矩阵A[1...n][1...n]压缩到一维数组B[(n(n+1)/2+1]
        • 上三角矩阵
          • 类似于下三角矩阵
      • 三对角矩阵（带状矩阵）
        • 定义：对于任意元素aij，当|i-j|>1时，有aij=0
        • aij对应存放下标为k=2i+j-3
      • 稀疏矩阵
        • 定义：矩阵中的非零元素的个数t，相对于矩阵元素的个数s来说非常少，即s>>t
        • 存储三元组（行标、列标、值）（可以用数组或是十字链表法存储）
          • 矩阵可以作为图的存储结构