栈Stack

只允许在一端进行插入或删除操作的线性表
由栈顶、栈底、空栈组成
栈是一个单进单出的瓶子，有一个栈顶指针，指向栈顶，用于引导进栈出栈。

表达式处理

在数学上我们通常会用算数表达式来表示几个数或几个基本运算单位之间的运算关系，例如：
（1+2）;2-1;1*2；1/1;
而在数据结构中，我们为了电脑能够更好的读取数据，符合电脑的一些运算习惯，我们有三种表达式：前缀表达式 中缀表达式 后缀表达式
我们先定义三个部分，操作数—基本算数单元（1），运算符—基本运算符号（+），界限符—限定运算关系（{}）
中缀表达式就是平时的算数表达式 a+b-c
前缀表达式将符号位放在操作数之前 ab+c-/abc-+
后缀表达式将符号位放在操作数之后 -+abc
中转前后 注：运算顺序一定优先注意，根据符左右和左右符来判断是否处理了

队列queue

允许一边进一边出
有两个指针，一个是指向队头，一个是指向队尾。
根据指向风格不同，计算队列是否已满的方法也不同。
一般会故意留空区别空满
队列一般为循环队列，以达到最大使用效率
常用于

串string

有零个或多个字符组成的有限序列。一般用数组存放
串长：

define MAXLEN 255 定长

或是
堆分配

顺序储存和链式储存两种
顺序存储-随机存取
链式存储-增删改查
ps 每个结点存储多个字符，提高存储效率

基本操作

求子串 substring(&Sub,S,pos,len)

比较操作 strCompare(S,T)

定位操作 index(S,T)

模式匹配

模式串不一定在主串中找到
子串一定会找到

朴素模式匹配算法

所有长度为m的子串依次与模式串对比，直到有一个完全匹配的子串出现

例如 Index(S,T)
//设置两个扫描指针 一个主串指针 一个模式串指针
//失败回归第一个位置 i=i-j+2;j=1;
//若j>T.length 则匹配成功 返回当前子串第一个字符的位置--i-T.length
//最坏o(mn)

KMP算法

对于回溯的优化——对自身进行分析后适配
——主串的指针i不用移动（回溯）
预处理模式串——next数组-让模式串的指针回溯到相应的位置，避免重复对比
最坏o(m+n)

next数组
和自己对比，失败就向右移动m，匹配自己内部和开始部分的相同点
j[i]=i-m

优化——移动后字符相同接着移动