数据结构第三、四章：栈、队列、KMP
栈：
考察点并不多，主要是这样一些：
1.顺序栈指针起始位置和操作的关系、共享栈指针起始和操作的关系，以及判满
2.链栈的具体操作实现问题以及相应带头结点、不带头结点等
其他就是一些比较零散的知识点，书上基本划了重点，这里也就不加以赘述
习题补充：
4、5、6：主要补充下顺序栈、共享栈可能需要注意数组开始或者结束位置的问题
具体其实就是数组的写法和理解上面可能需要注意一下
平时可能多以注意指针的位置为主，对数组的起始和结束位置注意并不够
10：链栈的操作不够熟悉，做的时候依旧会有些生，主要是没清楚数据结构
是一个头插、头删的单链表，这个定义在其实就能清楚很多，保留
至于有没有头结点需要看题目的给定，还是比较容易产生惯性思维导致出错的
出入栈序列问题：
只需要把握某个出栈，另外几个还在栈里面的思路就可以解决
核心思想其实是模拟栈的运行，统考的考察点也均是反套路的基于栈运行的原理去考察
平时做题的时候应该以模拟栈运行的思路去做，而不是套公式，要能模拟栈的运行
23：C语言标识符，即使是当时特意注意，也同样是会忘记的，这类只能靠不断去回忆
31：目前统考里面暂时还没有出现以出序情况凑入序的题目，具体还没有研究过
队列：
主要考点是这样一些：
1.顺序队列（主要是循环队列）的指针和操作问题
其中涉及考法一般以给定指针和约定方法求判空、判满或者给定初始反推指针情况为主
只需要熟练掌握这四种情况以及各自的逆推，判空即为初始，判满也并不难
2.链队的带头结点、不带头结点的操作实现（以及适用的链表类型
3.双端队列的输出序列判断（主要是对应方法的提取速度上面还需要加强
复习上面以上面列出的主要内容为主，其他就以书上的一些重点和细节复习为主
细节补充：
如果有谁说用队列、栈来实现随机存取给他一巴掌
数组的各类型表示里面，如果没有给出具体的说明就默认是以零开始的，否则按说明
习题补充：
5、6、7：依旧是一些需要注意的点
数组的开端和结束端是什么，以及队尾队首指针是什么
其实更容易忽略的就是判满条件，一般约定是以牺牲一个存储单元，但不排除出题
这个也是个潜在的考点方向，需要注意的
所以思维惯性上面，还是需要划关键词，尽可能不要出错
8、9、10、21、22：循环队列的判空、判满问题，还是考察正逆推为主，熟练就能不错
6：比较弱的其实就是这类计算中间间隔几个，一直都是比较弱的地方
包括后面的矩阵运算，比较容易出错，只能是一步步慢慢算，既然容易错就只能这样
17：至于队头和队尾到底设置在哪，这个是真的看题目的，和指针的位置基本没关系的
有时候就像这种逆天题目会出来链尾设置队头的情况，具体情况分析
19：可以用于个人的正逆推，比较适合去练手提高熟练程度，主要是知识匹配速度
因为这两个比较类似，所以提取上面就容易弱一些，还是要多练
23：其实当初的理解多半还是有些缺陷，这道题的考察其实也是以模拟运行过程为主
不过也确实可以视作就是栈的输出，只要符合栈就一定成立
18：多队列问题，相比于多栈问题会容易一些，只需要找最长子序列有几个就行
多栈问题目前还没有研究过，但预计处理方式应该是模拟运行为主
12：还是很有意思的，画蛇添足类的题目，有时候在时间复杂度一样的情况下看冗余度
哪个明显是不需要、不必要的操作，那么就可以直接排除，本质是看常数项的大小
栈、队列的应用：
出题一般都会比较灵活，需要具体问题具体分析，只能看临场状态和理解
但基本的知识点还是要清楚：
1.栈的中缀转前缀、转后缀，后缀、前缀转中缀以及计算（统考多次单独考察
2.栈最大深度的计算
个人认为容易结合树、递归考察，只需要清楚一件事
栈最大深度就是这棵递归树的最大深度，因为栈一定是遍历到叶结点开始回归向上的
至于建递归树的过程我的建议是自底向上而不要采用自顶向下
3.队列对树的层次遍历（广搜）
其他就是一些细节性的补充，看书上个人补充的笔记和重点划分即可
建议额外补充清楚整本数据结构里面哪些用了栈，哪些用了队列，方便一次性回忆
也尽可能要向其他学科拓展，因为统考就是这样考察的
习题补充：
6：递归函数的调用次数计算，就是数出整棵递归树的结点数，数量小可以自顶向下
只要不要漏掉第一次主调用也算一次就行了
关于栈的应用，计组里面也有相应的处理中断的内容，所以考察应该会比较泛化
12：目前栈、队列的应用上面统考考察只有两个，但统考肯定会考察新的内容
所以务必要自己额外补充栈、队列的应用和在不同数据结构中的应用，否则必然死透
16：多队列问题，目前基本已经算是最简单的问题了，一个问题可以变为其反问题
矩阵：该节掌握较差，建议额外补充习题，并且多加练习
附录：栈、队列的应用和统计
二叉树的遍历是基于递归的，也可以是基于栈的，所以必然用了栈（先序、中序、后序
线索二叉树的构建也可以说是基于栈的，按线索二叉树访问也需要用到递归栈
但就遍历本身而言，线索二叉树的向后遍历只有后序需要栈，向前遍历只有先序需要栈
这当然是建立在“非递归”栈情况上的
树的层序遍历需要用到队列
图的广度优先搜索(BFS)需要用到队列，深度优先搜索需要用到递归工作栈
AOV网的拓扑排序基于栈，关键路径的求解利用栈（逆拓扑排序，也可以基于队列实现
折半查找的递归也可以理解为利用栈，二叉排序树的构建用递归也可以利用栈
排序章暂时还未复习，后序会总结进来
KMP：（配合天勤、PPT、统考真题、综合题模拟算法运行
不建议按照王道书上给定的方法学习，因为统考考察的是KMP算法运行的模拟
单纯求出Next数组、Nextval几乎没有任何用处，基本可以直接舍弃，以算法模拟为核
Next数组是用于实际意义上算法执行的代码，不适合用于算法的模拟运行
具体稍微提一点：KMP算法中主串指针是只会向前移动不会向后返回的
只改变字串的指针位置而已，所以比较次数上面最多不会超过主串的长度，注意下
至于具体的训练方法，由于题量比较有限，所以建议结合PPT、统考真题、综合2、天勤
一并完成训练，算法的思想如果理解了其实这个算法可以说是非常简单的
就是实现比较复杂而已
学科综合应用：（基本无需勘误）
栈：
数据结构中的应用
- 括号匹配：用于检查表达式中的括号是否正确匹配
- 表达式求值：用于中缀表达式转换为后缀表达式和后缀表达式求值
- 深度优先搜索（DFS）：使用栈实现图和树的深度优先遍历
- 函数调用：用于实现递归函数调用时保存和恢复函数状态
- 撤销操作：在文本编辑器中实现撤销（Undo）功能
计算机组成原理中的应用
- 函数调用栈：管理函数调用和返回，包括参数传递和局部变量存储
- 中断处理：保存和恢复处理中断时的CPU状态
- 寄存器栈：一些处理器使用栈式寄存器组织方式来简化指令集设计
- 逆波兰表示法计算：用于栈机器中的表达式计算
- 存储器管理：实现嵌套子程序和递归调用的栈帧管理
计算机网络中的应用
- 协议栈：如TCP/IP协议栈，分层实现网络通信功能
- 路由器栈：用于存储路由表和转发信息
- 数据包封装和解封装：数据通过各层协议进行封装和解封装处理
- 网络地址转换（NAT）：记录内外部地址映射关系
- 缓冲区管理：网络传输中使用栈管理数据包的缓冲区
操作系统中的应用
- 进程的上下文切换：保存和恢复进程的CPU状态
- 递归调用管理：管理递归函数的调用栈帧
- 内核模式和用户模式切换：管理特权级别切换的状态保存
- 任务调度：管理多任务操作系统中的任务切换
- 系统调用处理：管理用户进程和内核之间的系统调用接口
队列：
数据结构中的应用
- 广度优先搜索（BFS）：使用队列实现图和树的广度优先遍历
- 缓冲区管理：在生产者-消费者问题中用于实现缓冲区管理
- 打印队列：管理待打印任务的顺序
- 任务调度：用于操作系统的任务调度，如在多级反馈队列调度算法中
- 事件驱动编程：用于存储和处理事件的队列
计算机组成原理中的应用
- 指令流水线：在指令流水线中，指令通过各阶段的队列传递
- 硬件缓冲区：在硬件中实现数据的缓冲，如在内存控制器中
- 输入输出（I/O）队列：管理I/O请求的顺序
- CPU任务队列：管理CPU等待执行的任务队列
- 数据流处理：在数据流处理器中，用队列管理数据传输
计算机网络中的应用
- 路由队列：在路由器中管理数据包的转发顺序
- 数据包缓冲：用于管理网络数据包的缓存，如在交换机和路由器中
- 消息队列：用于分布式系统中的消息传递
- 网络请求队列：在服务器中管理客户端请求的处理顺序
- 流量整形：用于管理网络流量的整形和控制
操作系统中的应用
- 进程调度：管理待执行进程的队列，如在轮转调度算法中
- I/O请求管理：在操作系统中管理I/O请求的队列
- 打印队列：管理打印作业的执行顺序
- 多级队列调度：在多级队列调度算法中，用队列管理不同优先级的任务
- 网络数据处理：在操作系统内核中，管理网络数据包的接收和发送队列
栈的应用场景（主要是交叉学科的知识汇总）：
函数调用和递归、表达式求值、括号匹配、深度优先搜索、迷宫求解
撤销操作：
许多应用程序（如文本编辑器）使用栈来实现撤销（Undo）操作。每次用户执行一个操作时，该操作被推入栈中。当用户执行撤销时，从栈中弹出最近的操作。
页面访问历史：
在浏览器中，栈可用于存储用户的页面访问历史。每当用户访问新页面时，该页面的地址被推入栈中。后退按钮则从栈中弹出地址。
进制转换：
栈可以用于将十进制数转换为其他进制数（如二进制、八进制等）
队列应用场景（了解即可）：
任务调度：
操作系统使用队列来管理等待执行的任务，如进程或线程。当系统资源（如CPU）可用时，它会从队列中取出下一个等待的任务来执行。
在多线程编程中，任务队列用于在多个线程之间分配工作。生产者线程将任务添加到队列中，消费者线程从队列中取出任务并执行。
打印任务管理：
在打印环境中，多个打印任务可能被发送到同一台打印机。打印机使用队列来管理这些任务，确保它们按照接收的顺序被打印。
网络通信：
在网络通信中，数据包通常按照它们到达的顺序被处理。队列用于在接收和发送数据包时保持这种顺序。
在路由器和交换机中，队列用于缓冲数据包，以便在拥塞时进行管理。
事件处理：
在图形用户界面（GUI）中，用户输入事件（如鼠标点击或键盘输入）被添加到事件队列中。GUI框架按照事件发生的顺序从队列中取出事件并处理它们。
在Web应用程序中，用户请求（如HTTP请求）被添加到请求队列中，以便服务器按照请求到达的顺序处理它们。
数据缓冲：
在数据产生和消费速度不匹配的情况下，队列用作缓冲区来平衡两者。例如，在生产者-消费者问题中，生产者将数据添加到队列中，消费者从队列中取出数据。
动画和模拟：
在计算机图形和模拟中，队列用于管理需要按顺序执行的动画帧或模拟步骤。
并发控制：
在多线程或多进程环境中，队列可用于同步对共享资源的访问。通过将要访问资源的请求添加到队列中，可以确保它们按照预定的顺序被处理，从而避免竞争条件和死锁。
消息传递：
在分布式系统中，消息队列用于在不同组件或系统之间传递消息。这些消息可以是数据、命令或事件。通过使用队列，系统可以异步地通信，从而提高可扩展性和可靠性。
批处理：
在批处理环境中，队列用于存储待处理的作业或任务。这些作业可以按照特定的顺序或优先级进行处理，以实现资源的高效利用和任务的优化执行。
补充：
C语言的标识符一般应遵循如下的命名规则：
命名规则：标识符必须以字母（az、AZ）或下划线开头，后面可跟任意个（可为0）字符，这些字符可以是字母、下划线和数字，其他字符不允许出现在标识符中
大小写区分：标识符区分大小写
长度限制：C89规定标识符长度不超过31个字符，C99规定不超过63个字符
关键字限制：C语言中的关键字有特殊意义，不能作为标识符
命名建议：自定义标识符最好取具有一定意义的字符串，便于记忆和理解
文件系统，用的逻辑结构一般是树
