③栈、队列和数组

24自用408数据结构，栈(Stack)是一种操作受限的线性表，只允许在一端进行插入或删除操作的线性表。

第三章

• 栈(Stack)
  • 基本概念
    • 一种操作受限的线性表，只允许在一端进行插入或删除操作的线性表
    • 注意
      • 后进先出LIFO
      • n个不同元素，出栈元素不同排列组合个数为
        • 
    • 基本操作
      • InitStack(&s)
      • StackEmpty(s)
      • Push(&s,x
      • Pop(&s，&x
      • GetTop(S，&x)
      • DestroyStack(&S)
  • 栈的顺序存储结构
    • 顺序栈实现
      • 栈顶指针：初始为S.top＝-1（有可能为0，意为指向栈顶元素的下一个存储单元，出栈入栈等操作都会发生变化注意)
        • S.top＝-1
      • 进栈操作：栈不满时，栈顶指针先加1，再送值至栈顶元素
        • S.data[++S.top]＝x
      • 出栈操作：栈非空时，先取栈顶元素，再将栈顶指针减1
        • x＝S.data[S.top--]
        • 读栈和出栈注意区别
          • 读栈顶元素，栈顶元素不改变
      • 栈空条件：S.top＝＝-1；栈满条件：S.top＝＝MaxSize-1：栈长：栈顶指针加1
        • S.top＝＝-1
      • 栈的空间不足时，会发生上溢
    • 共享栈
      • 两个顺序栈共享一个一维数组空间
      • 判空：top左＝-1时，左栈空；top右＝MaxSize，右栈空
      • 判满：两个指针相邻，top右-top左＝1
      • 进栈：左号栈top左先加1，再赋值；右栈top右先减1，再赋值
      • 出栈与进栈相反
  • 栈的链式存储结构
    • 便于多个栈共享存储空间和提高效率
    • 不会发生上溢
    • 采用单链表实现，并规定所有操作都是在单链表的表头进行的
• 队列(Queue)
  • 基本概念
    • 一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除
    • 注意
      • 先进先出FIFO
      • 不可以随意读取栈或队列中间的某个数据
    • 基本操作
  • 队列的顺序存储结构
    • 队列的顺序存储
      • 队头指针，队尾指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置(这个指针指向不是固定，得认真审题，看指针指向含义)
        • Q.front＝＝Q.rear＝＝0
      • 进队操作：队不满时，先送值到队尾元素，再将队尾指针加1
      • 出队操作：队不空时，先取队头元素值，再将队头指针加1
      • 队空条件：Q.front＝＝Q.rear＝＝0
      • 如果用Q.rear＝＝MaxSize作为队满条件，会出现“假上溢”
    • 循环队列
      • 将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环
      • 基本操作
        • 队首指针进1：Q.front＝(Q.front+1)％Maxsize
        • 队尾指针进1：Q.rear＝(Q.rear+1)%MaxSize
        • 队列中元素个数：(Q.rear-Q.front+MaxSize)%MaxSize
      • 判满
        • 1| 牺牲一个单元来区分队空和队满，且在以“队头指针在队尾指针的下一位置作为队满的标志
          • 队满条件：(Q.rear+1)%MaxSize＝Q.front
          • 队空条件：Q.front＝＝Q.rear
          • 队列中元素个数：(Q.rear-Q.front+MaxSize)%MaxSize
        • 2| 类型中增设表示元素个数的数据成员
          • 队空：Q.size＝＝0
          • 队满：Q.size＝＝MaxSize
          • 这两种情况都有Q.front＝＝Q.rear
        • 3| 类型中增设tag数据成员
          • 队空：tag＝0时，因删除导致Q.front＝Q.rear
          • 队满：tag＝1时，因插入导致Q.front＝＝Q.rear
  • 队列的链式存储结构
    • 实际上是一个同时带有队头指针和队尾指针的单链表
    • 不带头结点的链式队列在操作上往往比较麻烦，通常使用带头结点的单链
    • 优点
      • 单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题
      • 若程序中需要使用多个队列时，与多个栈的情形一样，最好使用链式队列，这样就不会出现分配不合理和“溢出”问题”
  • 双端队列
    • 允许两端都可以进行入队和出队操作的队列
    • 为升级版栈，只要栈能实现的，双端队列都能实现
    • 类型
      • 输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列
      • 输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列
• 栈和队列应用
  • 栈的应用
    • 括号匹配
    • 表达式求值
      • 中缀表达式转后缀表达式
        • 手算
          • 1| 按照左优先原则，找到优先级最高的运算符
          • 2| 按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数
          • 3| 重复②直到所有运算符都被处理
          • 4| 左优先原则：只要左边的运算符能着计算，就优先算左边的
        • 机算
          • 1| 遇到操作数
            • 直接加入后缀表达式
          • 2| 遇到界限符
            • ①遇到左括号直接入栈； ②遇到右括号，依次弹出栈内运算符并加入后缀表达式，直到，弹出左括号为止。注意，界限符不加入后缀表达式。
          • 3| 遇到运算符
            • 依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式。 若遇到左括号或栈空，则停止。最后再把当前运算符入栈
      • 中缀表达式转前缀表达式
        • 手算
          • 1| 按照右优先原则，找到优先级最高的运算符
          • 2| 按照[运算符 左操作数 右操作数] 的方式组合成一个新的操作数
          • 3| 重复②直到所有运算符都被处理
          • 4| 右优先原则：只要右边的运算符能着计算，就优先算左边的
      • 后缀表达式的计算
        • 手算
          • 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
        • 机算
          • 1| 从左往右扫描下一个元素，直到处理完所有元素
          • 2| 若扫描到操作数则压入栈，并返回①；否则执行③
          • 3| 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①
      • 中缀表达式的计算
        • 机算
          • 1| 初始化两个栈，操作数栈和运算符栈
          • 2| 若扫描到操作数，压入操作数
          • 3| 遇到界限符或运算符，则按照中缀转后缀相同的逻辑压入运算符栈(期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈
    • 递归
      • 两个条件
      • 太多层递归可能会导致栈溢出
  • 队列的应用
    • 队列在层次遍历中的应用
      • 层序遍历树
    • 队列在计算机系统中的应用
      • 解决主机与外部设备之间速度不匹配的问题
      • 解决多用户引起的资源竞争问题
      • 图的广度优先遍历
• 数组
  • 数组的定义
    • 相同类型元素构成的有限序列，线性表的推广
  • 数组的存储结构
    • 数组元素ai的地址：LOC(ai)＝LOC(a0)+i×L（0≤i≤n)
    • 多维数组(二维数组为例)
      • 按行优先
        • 数据元素aij的地址：LOC(aij)＝LOC(a0)+[i×(列数)+j]×L]
      • 按列优先
        • 数据元素aij的地址：LOC(aij)＝LOC(a0)+[j×(行数)+i]×L]
  • 特殊矩阵
    • 对称矩阵
      • 关于主对角线对称的矩阵
      • 计算方法
        • 按行优先
          • 1| 先找出每一行的元素个数(第1行到第i行l
          • 2| 将每一行个数累加求和即可得到表达式
          • 3| 上下三角区的元素将表达式中i和j互换即可
        • 按列优先
          • 步骤与按行相同，将行改成列即可
    • 三角矩阵
      • 下三角矩阵
        • 上三角区的所有元素均为同一常量
        • 存储完下三角区和主对角线元素之后，紧接着存储对角线上方的常量一次即可
        • 存储常量的下标k为n(n+1)/2(数组以0开头)
      • 上三角矩阵
        • 下三角区的所有元素均为同一常量
        • 存储完上三角区和主对角线元素之后，紧接着存储对角线下方的常量一次即可
    • 三对角矩阵
      • 又称带状矩阵，以对角线为中心的三条对角线的区域，其他区域的元素都为0
      • 在一维数组存放的下标为k＝2i+j-3
      • 已知k，i＝(k+1)/3+1 向下取整即可 j＝k-2i+3
    • 计算元素下标之间的对应关系的方法一致 在审题时，一定要注意数组的下标是从0开始还是从1开始 还有矩阵的下标是从1开始还是从0开始
  • 稀疏矩阵
    • 矩阵中非零元素的个数t，相对矩阵元素的个数来说非常少，即s＞＞t的矩阵称为稀疏矩阵
    • 存储方式
      • 三元组
        • 将非零元素及其相应的行和列构成一个三元组(行标，列标，值)
    • 注意：稀疏矩阵压缩存储后便失去了随机存取的特性
    • 稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储