栈和队列-数据结构第3章

后缀表达式求值：从左往右扫描，每遇到一个运算符，就将<左操作数 右操作数 运算符>变为<左操作数 运算符 右操作数>的形式。

第三章 栈和队列 数据结构 王道考研系列

• 栈(Stack)
  • 定义
    • 一种操作受限的线性表，只能在栈顶插入、删除
    • 特性：先进后出（Last in first out,LIFO）
    • 术语：栈顶、栈底、空栈
  • 基本操作
    • 创、销
    • 增、删（元素进栈、出栈，只能在栈顶操作）
    • 查(获得栈顶元素，但不删除）
    • 判空
  • 栈的顺序存储结构
    • 顺序栈
      • 顺序存储,用静态数组方式实现，并需要记录栈顶指针
      • 基本操作
        • 创（初始化）
        • 增（进栈）
        • 删（出栈）
        • 查（获取栈顶元素）
        • 判空、判满
        • 都是O(1)时间复杂度
      • 两种实现
        • 初始化时 top = -1
          • 入栈
          • 出栈
          • 获得栈顶元素
            • x=S.data[s.top] ;
          • 栈空/栈满条件是?
            • 栈空条件
              • S.top == -1;
            • 栈满条件
              • S.top == MaxSize-1;
            • 栈长
              • S.top + 1
        • 初始化时 top = 0
          • 入栈
          • 出栈
          • 获得栈顶元素
            • x=S.data[S.top-1];
          • 栈空/栈满条件是?
            • 栈空条件
              • S.top == 0;
            • 栈满条件
              • S.top == MaxSize;
    • 共享栈
      • 两个栈共享同一片内存空间，两个栈从两边往中间增长
      • 初始化
        • 0号栈 栈顶指针初始化时 top1 = -1;
        • 1号栈 栈顶指针初始化时 top1 = MaxSize;
      • 栈满条件
        • top0 + 1 == top1;
  • 栈的链式存储结构
    • 用链式存储方式实现的栈
    • 两中实现方式
      • 带头结点
      • 不带头结点
    • 基本操作
      • 创（初始化）
      • 增（进栈）
      • 删（出栈）
      • 查（获取栈顶元素）
      • 判空、判满
• 队列（Queue）
  • 队列的基本概念
    • 定义
      • 一种操作受限的线性表，只能在队尾插入、在队头删除
      • 特性：先进先出（first into first out,FIFO）
      • 术语
        • 队头、队尾、空队列、队头元素、队尾元素
    • 基本操作
      • 创、销
      • 增、删（入队、出队，只能在规定的一端进行）
      • 查（获得队头元素，但不删除）
      • 判空
  • 队列的顺序存储结构
    • 用顺序存储实现队列
    • 基本操作
      • 创（初始化）
      • 增（进队）
      • 删（出队）
      • 查（获取队头元素）
      • 判空、判满（进行增/删/查操作前的必要判断）
    • 循环队列
    • 循环队列的操作
  • 队列的链式存储结构
    • 用链式存储实现队列
      • 带头结点
      • 不带头结点
    • 基本操作
      • 创（初始化）
      • 增（进队）
        • 注意一个元素入队
      • 删（出队）
        • 注意最后一个元素出队
      • 查（获取队头元素）
      • 判空、判满（进行增/删/查操作前的必要判断）
  • 双端队列
    • 双端队列
      • 允许从两端插入、两端删除的队列
    • 输入受限的双端队列
      • 允许从两端删除、从另一端插入的队列
    • 输出受限的双端队列
      • 允许从两端插入、从另一端删除的队列
    • 考点：对输出序列合法性的判断
• 栈和队列的应用
  • 栈在括号匹配中的应用
    • 用栈实现括号匹配：
      • 依次扫描所有字符
      • 遇到左括号入栈
      • 遇到右括号则弹出栈顶元素检查是否匹配。
    • 匹配失败情况：
      • ①左括号单身
      • ②右括号单身
      • ③左右括号不匹配
  • 栈在表达式求值中的应用
    • 概念
      • 运算符、操作数、界限符（DIY概念：左操作数/右操作数）
    • 三种算数表达式
      • 中缀表达式
        • 运算符在操作树中间
      • 后缀表达式（逆波兰式）
        • 运算符在操作数后面
      • 前缀表达式（波兰式）
        • 运算符在操作数前面
    • 后缀表达式相关考点
      • 中缀表达式转后缀表达式
        • ①按“左优先”原则确定运算符的运算次序
        • ②根据①中确定的次序，依次将各个运算符和与之相邻的两个操作数按<左操作数 右操作数 运算符>的规则合体
      • 后缀表达式求值
        • 从左往右扫描，每遇到一个运算符，就将<左操作数 右操作数 运算符>变为<左操作数 运算符 右操作数>的形式
      • 计算
        • 从左往右扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈（注意：先弹出的元素是“右操作数”）
    • 前缀表达式相关考点
      • 中缀表达式转前缀表达式
        • ①按“右优先”原则确定运算符的运算次序
        • ②根据①中确定的次序，依次将各个运算符和与之相邻的两个操作数按<运算符 右操作数 左操作数>的规则合体
      • 前缀表达式求值（用栈实现）
        • 从右往左扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈（注意：先弹出的元素是“左操作数”）
  • 栈在递归中的应用
    • 函数调用的特点：
      • 最后被调用的函数最先执行结束（LIFO）
    • 函数调用时，需要用一个“函数调用栈” 存储：
    • 递归调用时，函数调用栈可称为“递归工作栈”
      • 缺点：效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算
  • 队列在遍历中的应用
    • 树的层次遍历
    • 图的广度优先遍历
  • 队列在计算机系统中的应用
    • 多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service,先来先服务）是一种常用策略
• 矩阵的压缩存储
  • 数组的存储结构
    • 一维数组
    • 二维数组
  • 特殊矩阵
    • 对称矩阵
      • 特点：对方阵中的任意一个元素，有aᵢ,ⱼ=aⱼ,ᵢ
      • 压缩：只存储主对角线+下三角区（或主对角线+上三角区）
    • 三角矩阵
      • 特点：上三角区全为常量（下三角矩阵）；或下三角区全为常量（上三角矩阵）
      • 压缩：按行优先/列优先规则依次存储非常区域，并在最后一个位置存放常量c
    • 三对角矩阵（带状矩阵）
      • 特点：当|i-j|>1时，有aᵢ,ⱼ=0(1<=i,j<=n)
      • 压缩：按行优先/列优先规则依次存储带状区域
    • 稀疏矩阵
      • 非零元素个数远小于零元素个数
      • 压缩：只存储非零元素
        • 顺序存储：顺序存储三元组<行，列，值>
        • 链式存储：十字链表法
  • 常见考题
    • 矩阵的压缩存储需要多长的数组
    • 由矩阵行列号<i,j>推出对应的数组下标号k
      • 数列求和
    • 由k推出<i,j>
      • 如何处理不等式中的“刚好大于等于/小于等于”
      • 向上取整/向下取整
    • 易错点
      • 存储上三角？下三角？
      • 行优先？列优先
      • 矩阵元素的下标从0？1？开始
      • 数组下标从0？1？开始
• 队列的顺序实现
  • 实现思想
    • 用静态数组存放数据元素，设置队头 /队尾指针(front/rear)
    • 循环队列：用模运算（取余）将存储空间在逻辑上变为“环状”
    • 模运算
  • 重要考点
    • 如何 初始化、入队、出队
    • 如何 判空、判满
    • 如何 计算队列的队列
  • 分析思路
    • 确定front、rear指针的指向
      • ①rear指向队尾元素后一个位置
      • ②rear指向队尾元素
    • 确定判空、判满的方法
      • a.牺牲一个存储单元
      • b.增加size变量记录队列长度
      • c.增加tag = 0/1用于标记最近的一次操作是 出队/入队
      • ...