数据结构之栈，队列，串介绍

栈和队列不再过多描述，了解入栈出栈规则，入队出队规则，栈的递归应用即可，面试肯定不会考这种概念，太简单。

LeetCode36栈的应用

比如说有相当多的四则运算，前缀，中缀，后缀的题目都与栈有关。

主要想讲一下串这种数据结构。串百分之九十九指的都是字符串，对于一个字符串S="Googlegoodgoor"，来讲想要找到一个为“goor”的子串，最常用的方法暴力搜索，一位一位的对照，直至找到相应的子串，当然这种算法太过于复杂，对于一个复杂的字符串，除非你的正则表达式，用的非常的好，能够快速定位到需要的东西，否则你需要设计相当多的代码，来实现这个功能。下面介绍一种算法，KMP模式匹配算法，能够大大减少重复遍历的情况，这个算法很重要，2020年在面试腾讯C++岗位，让我手写过KMP算法。

讲一下大致流程，原理可以自己分析。

设模式串为S="abcdaabcab",子串为T="abcab",传统暴力解决方法S[0],T[0]比较，在比较S[1],T[1],当S[3],T[3]不相等的时候，S退回到S[0],T退回到T[0],当我们匹配到S[3],T[3]不等的时候S有必要退回S[2]重新比较么，显然第一次比较的所有动作全部白费，KMP很好的解决了这种重复遍历的情况，用一个Next数组来保存这些有用的信息。

Next数组，最长前缀默认Next[0]=-1，什么是最长前缀，对于子串abcab，有相等前缀后缀子串ab。

匹配方法：当我们第一次匹配的时候，S位置在S[3],T位置在T[3]不相等，我们借助next数组next[3]为0所以子串要退回到T[0]位置，与S[3]相比依然不相等，这时候就需要S移动到S[4]的位置，S[4]=T[0]，但S[5]不等于T[1]，即子串退回到next[1]的T[0]位置，即从后面开始可以匹配到子串。

LeetCode第28题