数据结构_3栈和队列

参考王道计算机考研《数据结构》课程，自主进行知识点归纳总结，必备复习资料分享，方便大家备考时翻阅查看，提高复习效率，希望对大家备考有所帮助。

栈和队列

• 队列
  • 定义
    • 一种操作受限的线性表，只能在队尾插入，在队头删除
    • 特性
      • 先进先出(FIFO)
    • 术语
      • 队头、队尾、空队列、队头元素、队尾元素
        • 
  • 基本操作
    • 创销
    • 增删(入队、出队只能在规定的一端进行)
    • 查（获得队头元素，但不删除）
    • 判空
  • 顺序实现
    • 实现思想
      • 用静态数组存放数据元素，设置队头/队尾（front/rear）指针
      • 循环队列
        • 用模运算(取余)将存储空间在逻辑上变为“环状”
        • Q.rear = (Q.rear+1) % MaxSize
    • 重要考点
      • 如何初始化，入队，出队
      • 如何判空，判满
      • 如何计算队列的长度
    • 分析思路
      • 确定rear、front指针的指向
        • rear指向队尾元素后一个位置
        • rear指向队尾元素
          • 初始化rear
            • 初始化：rear = -1 优点：插入元素不用判断是否在数组头部插入元素（使其他模块的代码更具通用性） 
      • 确定判空/判满的方法
        • 牺牲一个存储单元
        • 增加size变量
          • 记录当前队列长度
        • 增加tag=0/1
          • 标记最近的一次操作是出队/入队
  • 链式实现（单链表的阉割）
    • 用链式存储实现队列
      • 带头结点
      • 不带头结点
    • 基本操作
      • 创（初始化）
      • 增（入队）
        • 注意第一个元素入队
      • 删（出队）
        • 注意最后一个元素出队
      • 查（获取队头元素）
      • 判空
      • 判满？（不需要）
        • 一般不会队满，除非内存不足
  • 双端队列（选择题）
    • 允许从两端插入、两端删除的队列
    • 输入受限的双端队列
      • 允许从两端删除、一端插入的队列
    • 输出受限的双端队列
      • 允许从两端插入、一端删除的队列
    • 考点
      • 对输出序列合法性的判别
        • 在栈中合法的输出序列，在双端队列中必定合法（栈是双端队列的特例） 如何判别双端队列输出序列是否合法？ 观察输出序列中在输入序列中靠后的元素 对应该元素在输入序列前面的元素应该已在队列中排好 根据输出序列判断该元素前面的元素排列情况是否合法
• 栈与队列的应用
  • 栈的应用
    • 括号匹配问题
    • 表达式求值问题
      • 起源
        • 可以不用界限符(括号)也能无歧义地表达运算顺序
      • 概念
        • 运算符、操作数、界限符(括号)
      • 三种表达式
        • 一个中缀表达式可以对应多个后缀、前缀表达式
        • 中缀表达式
          • 运算符在操作数中间
        • 后缀表达式（逆波兰式）
          • 运算符在操作数后面
        • 前缀表达式（波兰式）
          • 运算符在操作数前面
      • 后缀表达式考点（常考）
        • 中缀转后缀
          • 1. 按"左优先"原则确定运算符的运算次序
            • 目的：一个中缀表达式只对应一个后缀表达式（确保算法的“确定性”） "左优先"：只要左边的运算符能先计算，就优先算左边(优先输出左边的运算符)的 
          • 2. 根据①中确定的次序，依次将各个运算符和与之相邻的两个操作数 按<左操作数 右操作数 运算符>的规则合体
        • 后缀转中缀
          • 从左往右扫描，每遇到一个运算符，就将 <左操作数 右操作数 运算符>变为(左操作数 运算符 右操作数)
            • 切记加括号（以免改变优先级）
        • 计算
          • 从左往右扫描后缀表达式
          • 遇到操作数入栈 遇到运算符则弹出两个栈顶元素运算后将运算结果压回栈顶
          • 表达式合法的结果
            • 最后(表达式处理完成)栈中只会留下一个元素，就是最终结果
          • 注意
            • 先弹出的元素是"右操作数"
      • 前缀表达式
        • 中缀转前缀
          • 1. 按"右优先"原则确定运算符的运算次序
            • 目的：一个中缀表达式只对应一个前缀表达式（确保算法的“确定性”） "右优先"：只要右边的运算符能先计算，就优先算右边(优先输出右边的运算符)的
          • 2. 根据①中确定的次序，依次将各个运算符和与之相邻的两个操作数 按<运算符 左操作数 右操作数>的规则合体
        • 计算
          • 从右往左扫描前缀表达式
          • 遇到操作数入栈 遇到运算符则弹出两个栈顶元素运算后将结果入栈
          • 注意
            • 先弹出的元素是"左操作数"
  • 队列的应用
• 栈（stack）
  • 概述
    • 术语
      • 栈顶
      • 栈底
      • 空栈
    • 定义
      • 一种操作受限的线性表，只能在栈顶插入、删除
      • 特性
        • 后进先出（LIFO）
    • 基本操作
      • 创、销
      • 增、删(元素进栈、出栈只能在栈顶操作)
      • 查（获得栈顶元素，但不删除）
      • 判空
  • 顺序栈
    • 顺序存储
      • 用静态数组实现，并需要记录栈顶指针
    • 基本操作
      • 创、增、删、查（均O(1)）
        • 王道ppt3.1.1 p5 删：top = -1 逻辑上删除栈，但实际上栈还存在，当函数运行结束后系统自动回收内存（声明栈时分配内存（非malloc）——静态数组） 查：栈的使用场景中大多只访问栈顶元素
    • 两种实现
      • 初始化时（top=-1）
        • 指向插入位置
        • 入栈
          • S.data[++S.top] = x
            • 先移动指针+1，再压入元素
        • 出栈
          • S.data[S.top--] = x
            • 先弹出元素，再移动指针-1
        • 获得栈顶元素
          • x = S.data[S.top]
        • 栈空/栈满条件
          • 栈空条件：top = -1 栈满条件：top = MaxSize - 1
      • 初始化时（top=0）
        • 指向插入位置的下一个位置
        • 入栈
          • S.data[S.top++] = x
        • 出栈
          • S.data[--S.top] = x
        • 获得栈顶元素
          • x = S.data[S.top-1]
        • 栈空/栈满条件
          • 栈空条件：top = 0 栈满条件：top = MaxSize
    • 共享栈
      • 定义
        • 两个栈共享同一片内存空间，两个栈从两边往中间增长
      • 初始化
        • 0号栈
          • 栈顶指针初始是top0 = -1
        • 1号栈
          • 栈顶指针初始是top1 = MasSize
      • 栈满条件
        • top0 + 1 == top2（两个栈栈顶指针挨在一起）
  • 链栈
    • 链式存储
      • 用链式存储方式实现的栈
    • 两种实现
      • 带头结点
      • 不带头结点(推荐)？
    • 重要基本操作
      • 创
      • 增
      • 删
      • 查
      • 判空、判满