栈
定义
- 栈是限定仅在表尾（栈顶top）进行插入和删除操作的线性表
Java中stack就是继承了vector
public E push(E item)//入栈
public synchronized E pop()//出栈
public synchronized E peek()//查看栈顶元素
public boolean empty()//判断是否为空
public synchronized int search(Object o)//查找最靠近栈顶的元素o位置
所以我们看C++里的stack吧
//栈的定义
typedef int SElemType;
typedef struct{
SElemType data[MAXSIZE];
int top;
}sqstack;
//入栈
Status push(sqstack *S, SElemType e){
if(S->top==MAXSIZE){
return ERROR;//满了
}
S->top++;
S->data[S->top]=e;
return SUCCESS;
}
//出栈
Status pop(sqstack *S, SElemType e){
if(s->top==-1){
return ERROR;//栈空
}
*e=s->data[s->top];
s->top--;
return SUCCESS;
}
//时间复杂度均为O(1)
两个栈共享空间
使用一个数组，数组的两个端点可以分别做两个栈的栈底。只需要两个值分别记录栈顶的位置即刻，如果两个值相差一即为两个栈都满了。
栈的链式存储结构
把栈顶放在单链表的头部
栈的应用—-递归
递归过程退回的顺序是它前行的逆序。在退回过程中，可能要执行某些动作，包括要恢复在前行过程中存储起来的某些数据。这种存储某些数据，并在后面以存储的逆序恢复这些数据，以提供之后使用的需求。就类似于栈。
在前行阶段，每次函数递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值以及返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。（由系统代劳管理）
栈的应用—-四则表达式
后缀表达式：所有的符号都是在要运算的数字后面出现。 9+（3-1）*3+10/2的后缀表达式是9 3 1 - 3 * + 10 2 / + 后缀表达式的计算方式就是从左到右🏪，如果遇到数字就入栈，遇到运算符号，就将栈顶的两个元素提取出来进行运算，得到一个新的数字后，将其压入栈中。当表达式遍历完后，将栈中最后的数字提出来就是答案。
中缀表达式转换为后缀表达式
我们平时用的数学表达式叫做中缀表达式。 方法：从左到右遍历中缀表达式中每个字符，遇到数字就输出，即成为后缀表达式的一部分，如果遇到的是符号，则判断其与栈顶元素的符号的优先级，如果低于或等于栈顶元素，就栈中元素依次出栈，直到栈顶元素优先级比新元素低，如果是右括号，则栈顶元素依次出栈直至遇到左括号。
队列
- 只允许在一端进行插入操作，而在另一端进行删除操作端线性表
在Java中队列Queue是一个接口
boolean add(E e);//添加元素
boolean offer(E e);//使用容量限制队列时优于add
E remove();//移除头部元素并返回，如果为空则抛出异常
E poll();//移除头部元素并返回，如果为空则返回null
E element();//只返回头部元素，为空异常
E peek();//返回头部元素，为空null
看C++中的Queue
empty()
Test whether container is empty (public member function )
size()
Return size (public member function )
front()
Access next element (public member function )
back()
Access last element (public member function )
push()
Insert element (public member function )
emplace()
Construct and insert element (public member function )
pop()
Remove next element (public member function )
swap()
Swap contents (public member function )两个队列进行交换
循环队列
队列的头尾相接的顺序存储结构称为循环队列。 一个数组，两个指针，一个指向头front，一个指向尾巴后面rear，尾指针到末端后，返回至数组最前端。队列满时为：(rear+1)%QueueMaxSize==front. 计算队列大小：(rear-front+QueueMaxSize)%QueueMaxSize ** **
串
- 串是由零个或多个字符组成的有限序列，有名叫字符串。
字符串能比较大小”aaa”<”aaaaa” private final byte[] value;
朴素算法模式匹配
两个循环嵌套 低效
KMP模式匹配算法
Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。
下面先直接给出KMP的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗花明☺）：
- 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
- 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
- 如果j != -1，且当前字符匹配失败（即S[i]!=P[j]），则令i不变，j=next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。
- 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。
很快，你也会意识到next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。
转换成代码表示，则是：
int KmpSearch(char* s, char* p)
{
int i = 0;
int j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen)
{
//①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if (j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
//②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen)
return i - j;
else
return -1;
}
