一、栈

image-20210726204709944

栈的定义

image-20210726204740231
image-20210726204751208
image-20210726204800939

栈的基本操作

image-20210726204812066

出栈顺序

image-20210726204902687

总结

image-20210726204916821

二、顺序栈

image-20210726204937548

顺序栈的定义

image-20210726205014664

基本操作

初始化操作

image-20210726205041303

进栈操作

image-20210726205118594

出栈操作

image-20200624152110685

读取栈顶元素

image-20200624152208184

另一种基本操作的实现方式

image-20210726205210505
image-20210726205256057

共享栈

image-20210726205357959

总结

image-20210726205435561

三、链栈

image-20210726205457511

复习单链表

image-20210726205518576
image-20200624153252888

链栈的定义

image-20210726205556417

总结

image-20210726205606460

四、队列

image-20210726205643080

队列的定义

image-20210726205656372
image-20210726205707313
image-20210726205716597

队列的基本操作

image-20210726205730255

总结

image-20210726205740361

五、顺序队列

image-20210726205800388

顺序队列的定义

image-20210726205828662

顺序队列的初始化

image-20210726205936490

入队操作

image-20210726210000265
image-20210726210010587

循环队列

image-20210726210034990
image-20210726210046933

出队

image-20210726210126251

判空/判满

方案一：牺牲一个存储空间

image-20210726210151059

方案二：利用size变量记录队列长度

image-20210726210211159

方案三：利用tag记录最后一次操作

image-20210726210223004

其它实现方式

image-20210726210307014
image-20210726210328765
image-20210726210353025

总结

image-20210726210420928

六、链队列

image-20210726210449654

链队列的定义

image-20210726210500752

链队列的基本操作

链队列的初始化

带头结点

image-20210726210631445

不带头结点

image-20210726210647339

入队

带头节点

image-20210726210701573

不带头节点

image-20210726210711098

出队

带有头节点

image-20210726210725504

不带头节点

image-20210726210736800

判满

image-20210726210758825

总结

image-20210726210828317

七、双端队列

image-20210726210852720

双端队列的定义

image-20210726210903964

考点

对于栈的输出序列的合法性

image-20210726211211957

绿色为合法，红色为非法

对于输入受限的双端队列的输出序列的合法性

image-20210726211247998

绿色为合法，红色为非法，带下划线是在栈中不合法，但在输入受限的双端队列中合法的。

对于输出受限的双端队列

image-20210726211310281

绿色为合法，红色为非法，带下划线是在栈中不合法，但在输出受限的双端队列中合法

这种输出受限的双端队列，看序号较大的元素输出的位置，这意味着，在它输出之前，比它小的元素的相对位置是确定的，接下来就是考虑有什么插入的方法能实现这种相对位置关系！

总结

image-20210726211326371

八、栈的应用

括号匹配问题

image-20210726211346767

实际过程

image-20210726211355389

正好匹配

image-20210726211417509

左右不匹配

image-20210726211427595

右括号单身

image-20210726211437034

左括号单身

image-20210726211447361

整个流程

image-20210726211516771

算法实现

image-20210726211553287

总结

image-20210726211604921

表达式求值

image-20210726211622556

算数表达式是什么？

由三个部分组成（操作数，运算符，界限符）

image-20210726211634409

前/后缀表达式的诞生

image-20210726211644195

中/后/前缀表达式的区别

image-20210726211654826

中转后的过程：

image-20210726211703851

上图中，后缀表达式的算术符的先后次序对应中缀表达式的生效的先后次序，但是这是一定的吗？

image-20210726211716650
image-20210726211814054

左优先原则，可保证运算顺序唯一性，以确定机算算法输出结果的唯一性！!

image-20210726211824944
image-20210726211929334
image-20210726211942205

机算算法实现

image-20210726211958326
image-20210726212059658

中转前的过程

image-20210726212125015

中转后和中转前的区别：

image-20210726212140264

中转前的机算过程：

image-20210726212202368

总结

image-20210726212314936

"左优先"/“右优先”原则和左/右操作数不是专业说法，仅供理解！

表达式求值——具体代码实现

image-20210726212335434

中转后机算

手算过程：

image-20210726212356303

机算过程：

image-20210726212423771

中缀表达式的计算

image-20210726212506614
image-20210726212608258

CPU只能执行单个的加减乘除运算，上边这么搞的意义就是为了将高级程序语言编译成简单的机器码，让CPU去执行！

总结

image-20210726212630916

栈在递归中的应用

递归的过程就是函数调用的过程

image-20210726212828055
image-20210726212846550

适合用“递归”算法解决的问题

image-20210726212856325

求阶乘：

image-20210726212926663

使用递归时，需要注意调用栈溢出！

image-20210726212940735

可以自定义栈将递归算法改造成非递归算法！

求斐波那契数列

image-20210726212954526

总结

image-20210726213001818

九、队列的应用

树的层次遍历

提示：不知道树这种数据结构的同学，可以考虑先跳过本文内容，等了解树之后，再来康康～

image-20210726213113786

详细实现内容在树的章节实现！

图的广度优先遍历

遍历是指找出所有元素节点

image-20210726213124384

队列在操作系统中的应用

CPU资源分配问题

image-20210726213132774

打印数据缓冲区

image-20210726213144535