栈和队列

栈和队列的共同点是只允许在端点处插入和删除元素。(一)栈:限定仅在表尾进行插入和删除操作的线性表。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新

栈和队列

• 栈
  • 栈（Stack）
    • 只允许在一端进行插入或删除操作的线性表
  • 栈顶（Top）：线性表允许进行插入和删除的那一端。
  • 栈底（Bottom）：固定的，不允许进行插入和删除的另一端
  • 特点
    • 栈是受限的线性表，所以自然具有线性关系。
    • 栈中元素后进去的必然先出来，即后进先出LIFO（Last In First Out）
  • 输入n个元素得到的出栈序列种数
• 顺序栈
  • 栈是线性表的特例，那栈的顺序存储也是线性表顺序存储的简化。栈的顺序存储结构也叫作顺序栈。
  • 结构
  • 操作
    • 初始化时top=-1
      • 判空
        • S.top==-1
      • 判满
        • S.top==maxsize-1
      • 进栈：
      • 出栈：
      • 读取栈顶元素：
    • 初始化时top=0
      • 判空
        • S.top==0
      • 判满
        • S.top==maxsize
      • 入栈
        • S.data[S.top++]=x
      • 出栈
        • x=S.data[--S.top]
      • 读取栈顶元素
        • x=S.data[S.top-1]
    • 补充
      • 除初始化操作外，其他基本操作的初始条件都要求栈已存在
• 共享栈
  • 顺序栈的存储空间大小需要事先开辟好，很多时候对每个栈各自单独开辟存储空间的利用率不如将各个栈的存储空间共享
  • 示意图
    • 将两栈的栈底分别设在内存空间的两端
  • 共享栈的结构
  • 共享栈的操作
    • 初始化
      • 0号栈栈顶指针初始时top0=-1；1号栈栈顶指针初始时 top1=MaxSize；
    • 进栈
    • 栈满：top1+1=top2
      • 两栈顶指针值相减的绝对值为1
• 链式栈
  • 栈是线性表的特例，线性表的存储结构还有链式存储结构，所以也可以用链表的方式来实现栈。栈的链式存储结构也叫作链栈。
  • 特点
    • 链栈一般不存在栈满的情况
    • 多个栈共存时最好用链式存储结构
  • 结构
  • 操作
    • 进栈
    • 出栈
    • 空栈的判定条件通常定为top==NULL；
• 栈的应用
  • 1、括号匹配：假设有两种括号，一种圆的()，一种方的[]，嵌套的顺序是任意的。
    • 算法思想
      • 若是左括号，入栈；若是右括号，出栈一个左括号判断是否与之匹配；检验到字符串尾，还要检查栈是否为空。只有栈空，整个字符串才是括号匹配的
    • 代码
  • 2、表达式求值：
    • 基本概念
      • 运算符
      • 操作数
      • 界限符
        • 反映了计算的先后顺序
    • 三种表达式
      • 中缀表达式
        • 运算符在操作数中间
      • 后缀表达式(逆波兰式)
        • 运算符在操作数后面
      • 前缀表达式(波兰式)
        • 运算符在操作数前面
      • 可以不用界限符也能无歧义地表达运算顺序
      • 总结
        • 一个中缀表达式可以对应多个后缀、前缀表达式
    • 表达式求值算法思想
      • 后缀表达式
        • 从左往右扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈
        • 先弹出的元素是“右操作数”
      • 前缀表达式
        • 从右往左扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈
        • 先弹出的元素是“左操作数”
      • 用栈实现中缀表达式的计算
        • 初始化两个栈，操作数栈和运算符栈
        • 若扫描到操作数，压入操作数栈
        • 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）
    • 表达式互相转换
      • 中缀表达式转后缀表达式
        • 算法思路
          • 1.按“左优先”原则确定运算符的运算次序
            • 一个中缀表达式只对应一个后缀表达式（确保算法的“确定性”）
          • 2.根据1.中确定的次序，依次将各个运算符和与之相邻的两个操作数按<左操作数 右操作数 运算符>的规则合体
        • 例子
      • 后缀表达式转中缀表达式
        • 算法思路
          • 从左往右扫描，每遇到一个运算符，就将<左操作数 右操作数 运算符>变为（左操作数 运算符 右操作数）的形式
      • 中缀表达式转前缀表达式
        • 算法思路
          • 1.按“右优先”原则确定运算符的运算次序
            • 一个中缀表达式只对应一个后缀表达式（确保算法的“确定性”）
          • 2.根据1.中确定的次序，依次将各个运算符和与之相邻的两个操作数按<运算符 左操作数 右操作数 >的规则合体
        • 例子
      • 前缀表达式转中缀表达式
        • 算法思路
          • 从右往左扫描，每遇到一个运算符，就将<运算符 左操作数 右操作数 >变为（左操作数 运算符 右操作数）的形式
  • 3、递归：
    • 要理解递归，你要先理解递归，直到你能理解递归。如果在一个函数、过程或数据结构的定义中又应用了它自身，那么这个函数、过程或数据结构称为是递归定义的，简称递归。递归最重要的是递归式和递归边界。
    • 栈与函数调用
      • 函数调用的特点：最后被调用的函数最先执行结束（LIFO）
      • 栈是实现过程和函数等子程序所必需的结构
      • 函数调用时，需要用一个“函数调用栈” 存储：
        • 调用返回地址
        • 实参
        • 局部变量
      • 递归调用时，函数调用栈可称为“递归工作栈”
        • 每进入一层递归，就将递归调用所需信息压入栈顶
        • 每退出一层递归，就从栈顶弹出相应信息
    • 分析
      • 消除递归不一定需要使用栈，例如尾递归
      • 任何一个递归都可以转换为非递归
      • 优点：程序结构简单清晰易读，易证明其正确性缺点：执行过程中占内存较多，运行效率低，不易优化
      • 适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题
    • 例子
      • 1.阶乘
        • 时间复杂度：O(NlogN)
      • 2.斐波那契数列
        • 时间复杂度 O(2^n)
      • 3.汉尼塔n个圆盘总的移动次数是(2^n)-1
• 队列
  • 队列(Queue)
    • 是只允许在一端进行插入，而在另一端进行删除的线性表
  • 队头（Front）：允许删除的一端，又称为队首。
  • 队尾（Rear）： 允许插入的一端。
  • 特点
    • 队列是受限的线性表，所以自然具有线性关系。
    • 先进入队列的元素必然先离开队列，即先进先出（First In First Out）简称FIFO
  • 队列的应用
    • 图的广度优先搜索
    • 二叉树的层次遍历
    • 进程调度算法--FCFS
• 顺序队列
  • 用数组来实现队列，可以将队首放在数组下标为0的位置。
  • 结构
  • 缺点
    • 会出现假溢出现象
• 循环队列
  • 用模运算（取余）将存储空间在逻辑上变为“环状”。这样首尾相连的顺序存储的队列就叫循环队列
  • 入队：rear=(rear+1)%MaxSize
  • 出队：front=(front+1)%MaxSize
  • 队列长度：（rear+Maxsize-front）%Maxsize
  • 循环队列的操作
    • 判断队列是否为空
    • 入队
    • 出队
    • 取队头元素
  • 确定front、rear指针的指向
    • rear指向队尾元素后一个位置
    • rear指向队尾元素
  • 那如何分辨队列是空还是满呢？
    • 1.设置标志位flag，当flag=0且rear等于front时为队列空，当flag=1且rear等于front时为队列满
    • 2.我们把front=rear仅作为队空的判定条件。当队列满的时候，令数组中仍然保留一个空余单元。我们认为这种情况就是队列满了。
    • 3.增加size变量记录队列长度
• 链式队列
  • 队列的链式存储结构，其实就是线性表的单链表，只不过需要加点限制，只能表尾插入元素，表头删除元素。
  • 结构
    • • 带尾指针的单向循环链表更适合表示队列
      • 一般不会队满，除非内存不足
    • 为了方便操作，我们分别设置队头指针和队尾指针，队头指针指向头结点，队尾指针指向尾结点。
  • 链式队列的操作
    • 1.入队
      • 我们知道队列只能从队尾插入元素，队头删除元素。于是入队就是在队尾指针进行插入结点操作。链队的插入操作和单链表的插入操作是一致的
    • 2.出队
      • 出队就是头结点的后继结点出队，然后将头结点的后继改为它后面的结点
• 双端队列