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

LeetCode36棧的應(yīng)用

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

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

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

設(shè)模式串為S="abcdaabcab",子串為T="abcab",傳統(tǒng)暴力解決方法S[0],T[0]比較，在比較S[1],T[1],當(dāng)S[3],T[3]不相等的時(shí)候，S退回到S[0],T退回到T[0],當(dāng)我們匹配到S[3],T[3]不等的時(shí)候S有必要退回S[2]重新比較么，顯然第一次比較的所有動(dòng)作全部白費(fèi)，KMP很好的解決了這種重復(fù)遍歷的情況，用一個(gè)Next數(shù)組來(lái)保存這些有用的信息。

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

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

LeetCode第28題