栈是限定仅在表尾进行插入和删除操作的线性表。
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

• 栈的定义

  • 栈的定义
    • 栈（stack）是限定仅在表尾进行插入和删除操作的线性表。
    • 我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表，简称LIFO结构。
    • 栈的插入操作，叫作进栈，也称压栈、入栈。
    • 栈的删除操作，叫作出栈，也有的叫做弹栈。
  • 进栈出栈变化形式
    3个元素，就有5种可能的出栈次序，如果元素数量多，其实出栈的变化将会更多的。

• 栈的抽象数据类型

图片.png

• 栈的顺序存储结构及实现

  • 栈的顺序存储结构
    • 在栈存在一个元素时，栈长度top等于0，因此通常把空栈的判定条件定位top等于-1。
  • 栈的顺序存储结构——进栈操作

图片.png

• 栈的顺序存储结构——出栈操作

图片.png

• 两栈共享空间

数组有两个断点，两个栈有两个栈底，分别占用两个断点，一个是top-1为空，一个是top为n为空
若栈2是空栈，栈1的top1等于n-1时，就是栈1满了，若栈1为空栈时，top2等于0时，为栈2满了，所以他们的关系top1+1=top2就是满栈。

• 栈的数据插入

图片.png

图片.png

• 栈的删除

图片.png

• 栈的链式存储结构及实现

  • 栈的链式存储结构
    栈的链式存储结构，简称为链栈。

图片.png

• 栈的链式存储结构——进栈操作

图片.png

图片.png

图片.png

• 栈的链式存储结构——出栈操作

图片.png

图片.png

• 栈的应用——递归

  • 斐波那契数列实现

    
    
    图片.png
  • 递归定义
    我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。
    迭代使用循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存，迭代则不需要反复调用函数和占用额外的内存。
    递归很适合栈。

• 栈的应用——四则运算表达式求值

  • 后缀（逆波兰）表示法定义
    一种不需要括号的后缀表达法，我们也把它称为逆波兰
    所有的符号都是在要运算数字后面出现。
  • 后缀表达式计算结果
    从左到右遍历表达式的每个数字和符号遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
  • 中缀表达式转后缀表达式
    从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号则栈顶元素一次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

• 队列的定义

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出的线性表，简称FIFO，允许插入的一端成为队尾，允许删除的一端称为队头。

• 循环队列

  • 队列顺序存储的不足
    有很多不足，溢出和出列问题最明显，如果出列后，其他元素都往前移动一位，那么就麻烦，如果直接出列让头往后移动，那么添加的时候会溢出，然而前面却没填满，这种叫假溢出

• 循环队列定义
• 所以解决溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。
• 那么问题又来了，空队列的时候front=rear，现在队列满时，也是front等于rear，那么如何判断此时的队列是空还是满呢？
• 我们通常是保留一个元素空间

• 设最大尺寸位QueueSize，那么队列满的条件是
  (rear+1)%QueueSize == front
  用取余的方式是为了，让首位相连，最后一个前进一位最后结果是0.
• 计算队列的长度的公式是(rear-front+QueueSize)%QueueSize

• 队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它之只能尾进头出。我们把它建成为链队列。

• 我们将队头指针指向队列的头结点，而队尾指针指向终端结点。

  
  

• 空队列时，front和rear都指向头结点

• 队列的链式存储结构——入队操作

• 队列的链式存储结构——出队操作

图片.png

• 在可以确定队列长度最大值的情况下，建议用循环队列，如果无法预估队列的长度时，则用链队列。