一、栈
1 基本概念
- 栈：是限定仅在表尾进行插入和删除操作的线性表。后进先出LIFO
- 栈顶(top)：允许插入和删除的一端
- 核底(bottom)：另一端
- 栈的引入简化了程序设计，使关注范围缩小，聚焦于要解决的问题核心。
2 栈的顺序存储结构 - 顺序栈
1）存储结构
栈是线性表的特例，栈的顺序存储是线性表顺序存储的简化。
- 栈底：数组0端
- top 变量：指示栈顶元素在数组中的位置，空栈-1
2）基本操作
- 进栈push：栈顶指针加一，新插元素赋值栈顶空间
- 出栈pop：栈顶指针减一，返回原栈顶
3）两栈共享空间
一个数组来存储两个具有相同数据类型的栈，数组两端为栈底，向中间靠拢。
通常都是当两个栈的空间需求有相反关系时，才使用这样的数据结构。
3 栈的链式存储结构 - 链栈
1）存储结构
- 栈顶：单链表的头部，替代头结点
2）基本操作
- 进栈push：当前栈顶元素赋值给新结点后继，新结点赋值给栈顶指针
- 出栈pop：栈顶指针下移，释放原栈顶结点
3）顺序栈与链栈对比
- 如元素变化不可预料，最好是用链栈；
- 如元素变化在可控范围内，使用顺序栈。
4 栈的应用
1）递归
编译器使用栈实现递归
2）四则运算表达式求值
- 中缀表达式：标准四则运算表达式，所有的运算符号都在两数字的中间
9 + (3 - 1) * 3 + 10/2
- 逆波兰表示：一种不需要括号的后缀表达法，所有的符号都是在要运算数字的后面出现
9 3 1-3 * + 10 2 / +
1. 将中缀表达式转化为后缀表达式(栈用来进出运算的符号)。
- 从左到右遍历中缀表达式的每一数字和符号，若是数字就输出，即成为后缀表达式的一部分
- 若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈
- 一直到最终输出后缀表达式为止。
2. 将后缀表达式进行运算得出结果(栈用来进出运算的数字)。
- 从左到右遍历表达式的每个数字和符号，遇到是数字就进栈；
- 遇到是符号，就将处于栈顶两个数字出拢，进行运算，运算结果进栈
- 一直到最终获得结果。
二、队列
1 基本概念
- 队列：是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。先进先出FIFO
- 队尾：允许插入的一端
- 队头：允许删除的一端称
2 队列的顺序存储结构 - 循环队列
1）存储结构
- 循环队列：队列的头尾相接的顺序存储结构
- front 指针：头指针
- rear 指针：尾指针。若队列不空，指向队尾的下一个位置
- 标志变量 flag：标记队列是否满了
2）基本操作
- 入队EnQueue：判满，新元素给尾指针位置，尾指针后移
- 出队DeQueue：判空，返回对头元素，头指针后移
3 队列的链式存储结构 - 链队列
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。
- front 指针：头指针。指向头结点。
- rear 指针：尾指针。指向终端结点。
2）基本操作
- 入队EnQueue：新结点赋值给原对尾结点后继，新结点设为队尾结点，尾指针指向新结点
- 出队DeQueue：头结点的后继结点出队，头结点的后继改为其后面的结点。若链表除头结点外只剩一个元素时， 则需将尾指针指向头结点
3）循环队列与链队列对比
- 在可以确定队列长度最大值的情况下，建议用循环队列
- 如果无法预估队列的长度时，则用链队列
4 队列的应用
键盘输入显示器输出
排队