数据结构栈和队列

数据结构栈和队列，逻辑结构为线性结构，两种数据类型都可以用顺序存储结构或链式存储结构来实现，一起来看。

3.栈和队列

• 栈
  • 逻辑结构：线性结构
  • 存储结构
    • 顺序存储：顺序栈
      • 存储类型的描述
    • 链式存储：链栈
      • 存储类型的描述
  • 栈的基本操作
    • 顺序栈
      • 初始化
      • 判栈空
      • 进栈
        • 先判栈满，再赋值，后top+1
      • 出栈
        • 先判栈空，在赋值，后top-1
      • 读栈顶元素
    • 链栈
  • 应用
    • 栈在括号匹配当中的应用
    • 栈在表达式求值中的应用
      • 1.掌握中缀表达式如何转化为按后缀表达式
        • 注意：中缀转后缀是遵循“左优先”原则，只要左边的运算符能计算就优先算左边的，在栈中先弹出的是右操作数
        • 手算方法
          • 操作数
            • 直接写
          • 运算符
            • 非括号
              • 若栈顶运算符的优先级高于或等于自己
                • 优先级：+ - > * /
                • 则不断弹出
              • 若栈顶运算符的优先级小于自己
                • 则直接压入栈中
            • 括号
              • 左括号
                • 直接压入栈中（左括号只有在遇到右括号才全部弹出，但是在遇到右括号之前，仍然具有优先级的性质）
              • 右括号
                • 不断将栈顶元素弹出，知道左括号（右括号不会进栈！！）
        • 机算方法
      • 2.掌握中缀表达式如何转化为按前缀表达式
        • 注意：中缀转前缀是遵循“右优先”原则，只要右边的运算符能计算就优先算左边的，在栈中先弹出的是左操作数
      • 3.理解在计算后缀表达式时栈是如何工作的
        • 操作数
          • 直接压入栈
        • 运算符
          • 弹出两个操作数，注意运算顺序
    • 栈在递归当中的应用
  • LIFO
• 队列
  • 逻辑结构：线性结构
  • 存储结构
    • 顺序存储
      • 存储类型的描述
      • 顺序队列
      • 循环队列
        • 可以解决顺序队列假溢出的问题
        • 三种方式处理队满或队空
          • 留出一个空位
          • tag位标记插入还是删除
          • 增加元素个数统计
        • 入队出队特点
          • 头尾指针永远都是在+1
            • 增加元素，尾指针（rear）+1
            • 减少元素，头指针（front）+1
    • 链式存储（链式队列）
      • 存储类型的描述
      • 同时带有队头指针和队尾指针的结点，可分为带头结点的链队和不带头节点的链队
      • 在新的结点入队后，要把新结点的next指针赋值为null
    • 双端队列
      • 考点主要是输出序列的判断，只要看清输入输出端的限制条件，耐心分析应该问题不大
  • 队列的基本操作
    • 循环队列的基本操作
      • 初始化
      • 判队空
      • 入队
        • 先判队满，再赋值，最后Q.rear = (Q.rear + 1)%MaxSize;
      • 出队
        • 先判队空，再赋值，最后Q.front = (Q.front + 1)%MaxSize;
    • 链式队列的基本操作
      • 初始化
      • 判队空
      • 入队
        • 赋值完毕后，需要将新结点指针指向空，在进行结点指针赋值（对尾指针指向新结点）
      • 出队
        • 带头结点
          • 先判空，再分配一个结点使其指向要出队的元素，再通过指针赋值逻辑上删除结点（⚠️注意如果队列中只有一个元素，则还需要再判断p是否等于Q.rear，如果等于，则赋值Q.rear = Q.front是往后的判空操作能顺利进行），最后free(p)物理上删除结点。
        • 不带头结点
      • • 注意头指针的位置是位于头结点的，以及特殊情况下front和rear的处理
  • 应用
    • 队列在层序遍历中的应用
      • 图的广度优先遍历类似于树的层序遍历，需要用到队列
      • 理解层序遍历的过程
    • 队列在计算系统中的应用
      • 1.解决主机与外部设备之间的速度不匹配问题
      • 2.解决由多用户引起的资源竞争问题
      • 3.缓冲区用队列实现
  • FIFO
• 特殊矩阵的压缩存储
  • 对称矩阵
    • 性质：上三角区中的所有元素和下三角区的所有元素相同（⚠️上三角区和下三角区都不包含主对角线上的元素）
    • 存储：对于n阶对称矩阵，建立长度为n(n+1)/2的一维数组，找到数组下标k和矩阵元素下标（i、j）的关系
  • 三角矩阵
    • 性质：上三角矩阵的下三角区是相同的变量，下三角矩阵的上三角区是相同的变量
    • 存储：对于n阶对称矩阵，建立长度为n(n+1)/2+1的一维数组，找到数组下标k和矩阵元素下标（i、j）的关系
  • 三对角矩阵（带状矩阵）
    • 性质：对于任一元素ai,j，当|i-j|>1时，有ai,j=0
    • 存储：对于n阶对称矩阵，建立长度为3n-2的一维数组，找到数组下标k和矩阵元素下标（i、j）的关系
  • 稀疏矩阵
    • 性质：矩阵中非零元素个数为t，相对于矩阵的个数s来说非常少，即s>>t的矩阵称为稀疏矩阵
    • 存储：将非零元素及其对应的行和列构成一个三元组（行标、列标、值），三元组既可以采用数组存储，也可以采用十字链表法存储
    • 失去了随机存取的特性
  • 注意点
    • 注意这些结构的下表和数组下标的区别，数组（C语言）是从0开始
    • 稀疏矩阵的存储方法
      • 三元组
      • 十字链表
• Remark
  • 队列与链表
    • 链表的头指针和尾指针是固定地指链头和链尾
    • 队列的头和尾可以选择是链头和链尾，也可以相反的选择，所以队列的头可能位于链表
    • 还有一个要注意的点是，队列的头是输出的一端，即减少的一端，反映在链式存储上就是失去结点
    • 标识字符只能以英文字母或者下划线开头，而不能是数字开头
    • 非递归方式不一定非要用栈实现，例如斐波那契额就可用循环实现
    • 进制转换和迷宫求解都是用栈实现
  • 顺序表示
    • 要注意题目给的到底是多少个元素，比如A[0...N]和A[0...N-1]分别是n+1和n个元素，小心坑
  • 归根结底
    • 基础的概念要清楚掌握
    • 读题时要完全读懂再进行下一步
• 逻辑结构为线性结构，两种数据类型都可以用顺序存储结构或链式存储结构来实现