一、栈
![image-20210726204709944](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726204710.png)
栈的定义
![image-20210726204740231](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726204740.png)
![image-20210726204751208](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726204751.png)
![image-20210726204800939](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726204800.png)
栈的基本操作
![image-20210726204812066](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726204812.png)
出栈顺序
![image-20210726204902687](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726204902.png)
总结
![image-20210726204916821](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726204916.png)
二、顺序栈
![image-20210726204937548](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726204937.png)
顺序栈的定义
![image-20210726205014664](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205014.png)
基本操作
初始化操作
![image-20210726205041303](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205041.png)
进栈操作
![image-20210726205118594](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205118.png)
出栈操作
![image-20200624152110685](https://cdn.jsdelivr.net/gh/KimYangOfCat/MyPicStorage/2021-CSPostgraduate-408/20200810010246.jpg)
读取栈顶元素
![image-20200624152208184](https://cdn.jsdelivr.net/gh/KimYangOfCat/MyPicStorage/2021-CSPostgraduate-408/20200810010251.jpg)
另一种基本操作的实现方式
![image-20210726205210505](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205210.png)
![image-20210726205256057](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205256.png)
共享栈
![image-20210726205357959](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205358.png)
总结
![image-20210726205435561](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205435.png)
三、链栈
![image-20210726205457511](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205457.png)
复习单链表
![image-20210726205518576](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205518.png)
![image-20200624153252888](https://cdn.jsdelivr.net/gh/KimYangOfCat/MyPicStorage/2021-CSPostgraduate-408/20200810010340.jpg)
链栈的定义
![image-20210726205556417](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205556.png)
总结
![image-20210726205606460](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205606.png)
四、队列
![image-20210726205643080](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205643.png)
队列的定义
![image-20210726205656372](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205656.png)
![image-20210726205707313](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205707.png)
![image-20210726205716597](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205716.png)
队列的基本操作
![image-20210726205730255](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205730.png)
总结
![image-20210726205740361](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205740.png)
五、顺序队列
![image-20210726205800388](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205800.png)
顺序队列的定义
![image-20210726205828662](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205828.png)
顺序队列的初始化
![image-20210726205936490](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726205936.png)
入队操作
![image-20210726210000265](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210000.png)
![image-20210726210010587](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210010.png)
循环队列
![image-20210726210034990](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210035.png)
![image-20210726210046933](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210047.png)
出队
![image-20210726210126251](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210126.png)
判空/判满
方案一:牺牲一个存储空间
![image-20210726210151059](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210151.png)
方案二:利用size变量记录队列长度
![image-20210726210211159](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210211.png)
方案三:利用tag记录最后一次操作
![image-20210726210223004](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210223.png)
其它实现方式
![image-20210726210307014](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210307.png)
![image-20210726210328765](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210328.png)
![image-20210726210353025](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210353.png)
总结
![image-20210726210420928](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210420.png)
六、链队列
![image-20210726210449654](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210449.png)
链队列的定义
![image-20210726210500752](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210500.png)
链队列的基本操作
链队列的初始化
带头结点
![image-20210726210631445](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210631.png)
不带头结点
![image-20210726210647339](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210647.png)
入队
带头节点
![image-20210726210701573](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210701.png)
不带头节点
![image-20210726210711098](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210711.png)
出队
带有头节点
![image-20210726210725504](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210725.png)
不带头节点
![image-20210726210736800](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210736.png)
判满
![image-20210726210758825](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210758.png)
总结
![image-20210726210828317](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210828.png)
七、双端队列
![image-20210726210852720](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210852.png)
双端队列的定义
![image-20210726210903964](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726210904.png)
考点
对于栈的输出序列的合法性
![image-20210726211211957](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211212.png)
绿色为合法,红色为非法
对于输入受限的双端队列的输出序列的合法性
![image-20210726211247998](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211248.png)
绿色为合法,红色为非法,带下划线是在栈中不合法,但在输入受限的双端队列中合法的。
对于输出受限的双端队列
![image-20210726211310281](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211310.png)
绿色为合法,红色为非法,带下划线是在栈中不合法,但在输出受限的双端队列中合法
这种输出受限的双端队列,看序号较大的元素输出的位置,这意味着,在它输出之前,比它小的元素的相对位置是确定的,接下来就是考虑有什么插入的方法能实现这种相对位置关系!
总结
![image-20210726211326371](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211326.png)
八、栈的应用
括号匹配问题
![image-20210726211346767](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211346.png)
实际过程
![image-20210726211355389](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211355.png)
正好匹配
![image-20210726211417509](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211417.png)
左右不匹配
![image-20210726211427595](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211427.png)
右括号单身
![image-20210726211437034](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211437.png)
左括号单身
![image-20210726211447361](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211447.png)
整个流程
![image-20210726211516771](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211516.png)
算法实现
![image-20210726211553287](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211553.png)
总结
![image-20210726211604921](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211604.png)
表达式求值
![image-20210726211622556](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211622.png)
算数表达式是什么?
由三个部分组成(操作数,运算符,界限符)
![image-20210726211634409](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211634.png)
前/后缀表达式的诞生
![image-20210726211644195](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211644.png)
中/后/前缀表达式的区别
![image-20210726211654826](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211654.png)
中转后的过程:
![image-20210726211703851](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211703.png)
上图中,后缀表达式的算术符的先后次序对应中缀表达式的生效的先后次序,但是这是一定的吗?
![image-20210726211716650](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211716.png)
![image-20210726211814054](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211814.png)
左优先原则,可保证运算顺序唯一性,以确定机算算法输出结果的唯一性!!
![image-20210726211824944](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211824.png)
![image-20210726211929334](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211929.png)
![image-20210726211942205](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211942.png)
机算算法实现
![image-20210726211958326](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726211958.png)
![image-20210726212059658](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212059.png)
中转前的过程
![image-20210726212125015](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212125.png)
中转后和中转前的区别:
![image-20210726212140264](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212140.png)
中转前的机算过程:
![image-20210726212202368](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212202.png)
总结
![image-20210726212314936](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212315.png)
"左优先"/“右优先”原则和左/右操作数不是专业说法,仅供理解!
表达式求值——具体代码实现
![image-20210726212335434](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212335.png)
中转后机算
手算过程:
![image-20210726212356303](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212356.png)
机算过程:
![image-20210726212423771](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212423.png)
中缀表达式的计算
![image-20210726212506614](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212506.png)
![image-20210726212608258](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212608.png)
CPU只能执行单个的加减乘除运算,上边这么搞的意义就是为了将高级程序语言编译成简单的机器码,让CPU去执行!
总结
![image-20210726212630916](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212630.png)
栈在递归中的应用
递归的过程就是函数调用的过程
![image-20210726212828055](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212828.png)
![image-20210726212846550](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212846.png)
适合用“递归”算法解决的问题
![image-20210726212856325](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212856.png)
求阶乘:
![image-20210726212926663](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212926.png)
使用递归时,需要注意调用栈溢出!
![image-20210726212940735](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212940.png)
可以自定义栈将递归算法改造成非递归算法!
求斐波那契数列
![image-20210726212954526](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726212954.png)
总结
![image-20210726213001818](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726213001.png)
九、队列的应用
树的层次遍历
提示:不知道树这种数据结构的同学,可以考虑先跳过本文内容,等了解树之后,再来康康~
![image-20210726213113786](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726213113.png)
详细实现内容在树的章节实现!
图的广度优先遍历
遍历是指找出所有元素节点
![image-20210726213124384](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726213124.png)
队列在操作系统中的应用
CPU资源分配问题
![image-20210726213132774](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726213132.png)
打印数据缓冲区
![image-20210726213144535](https://raw.githubusercontent.com/wushuai2000/PicGo/main/img/20210726213144.png)