數(shù)據(jù)結(jié)構(gòu)之棧，隊列，串介紹

棧和隊列不再過多描述，了解入棧出棧規(guī)則，入隊出隊規(guī)則，棧的遞歸應(yīng)用即可，面試肯定不會考這種概念，太簡單。

LeetCode36棧的應(yīng)用

比如說有相當多的四則運算，前綴，中綴，后綴的題目都與棧有關(guān)。

主要想講一下串這種數(shù)據(jù)結(jié)構(gòu)。串百分之九十九指的都是字符串，對于一個字符串S="Googlegoodgoor"，來講想要找到一個為“goor”的子串，最常用的方法暴力搜索，一位一位的對照，直至找到相應(yīng)的子串，當然這種算法太過于復(fù)雜，對于一個復(fù)雜的字符串，除非你的正則表達式，用的非常的好，能夠快速定位到需要的東西，否則你需要設(shè)計相當多的代碼，來實現(xiàn)這個功能。下面介紹一種算法，KMP模式匹配算法，能夠大大減少重復(fù)遍歷的情況，這個算法很重要，2020年在面試騰訊C++崗位，讓我手寫過KMP算法。

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

設(shè)模式串為S="abcdaabcab",子串為T="abcab",傳統(tǒng)暴力解決方法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很好的解決了這種重復(fù)遍歷的情況，用一個Next數(shù)組來保存這些有用的信息。

Next數(shù)組，最長前綴默認Next[0]=-1，什么是最長前綴，對于子串a(chǎn)bcab，有相等前綴后綴子串a(chǎn)b。

匹配方法：當我們第一次匹配的時候，S位置在S[3],T位置在T[3]不相等，我們借助next數(shù)組next[3]為0所以子串要退回到T[0]位置，與S[3]相比依然不相等，這時候就需要S移動到S[4]的位置，S[4]=T[0]，但S[5]不等于T[1]，即子串退回到next[1]的T[0]位置，即從后面開始可以匹配到子串。

LeetCode第28題