栈
栈的定义
栈（stack）是一种线性数据结构，它就像一个上图所示的放入乒乓球的圆筒容器，栈中的元素只能先入后出（First In Last Out，简称FILO）。最早进入的元素存放的位置叫作栈底 （bottom），最后进入的元素存放的位置叫作栈顶 （top）。
通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，拿下图来说，栈顶元素为元素4；同理，栈底元素指的是位于栈最底部的元素，下图中的栈底元素为元素1。
在顺序栈中用数组data[0..MaxSize-1]存放栈中元素，其中一端作为栈顶，另一端作为栈顶。我们的通常做法是讲data[0]作为栈底，data[MaxSize-1]做为栈顶。对顺序栈SqStack的声明是：
typedef struct{
ElmeType data[MaxSize]; //存放栈中的数据元素
int top; //栈顶指针，栈顶元素在data数组中的下标
}SqStack;判断栈空的条件：s->top == -1;
判断栈满的条件：s->top == MaxSize - 1;
元素e的进栈操作：先将栈顶指针top增1，然后将元素e放在栈顶指针处；
出栈栈顶元素：先将栈顶指针top处的元素取出放在e中，然后将栈顶指针减1。
栈的基本操作
- 初始化栈 InitStack(&s)
- 销毁栈 DestoryStack(&s)
- 判断是否为空栈 StackEmpty(s)
- 取栈顶元素 GetTop(s,&e)
入栈操作
入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。
//进栈操作的实现 以顺序栈为例
bool Push(SqStack *&s, ElemType e)
{
if (s->top == MaxSize - 1) //栈已满
return flase;
s->top++; //栈顶指针加一
s->data[s->top] = e; //将元素e放在栈顶指针处
return true;
}一个序列从1到n依次入栈, 那么可能的出栈序列一共有多少种? 注意: 在任意一个时刻,只要栈不为空, 就可能有元素出栈, 不是说元素全部入栈之后再出栈
这种条件下对应的出栈情况求和公式h(n)=C(2n,n)/(n+1)
出栈操作
出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。
//出栈操作的实现 以顺序栈为例
bool Pop(SqStack *&s, ElemType &e)
{
if (s->top == -1) //栈已空
return flase;
e = s->data[s->top]; //取栈顶元素赋给e
s->top--; //栈顶指针减一
return true;
}例题
(顺序栈)判断一个字符串是否为对称串
bool symmetry(ElemType str[])
{
int i;
ElemType e;
SqStack *st; //创建一个顺序栈st
InitStack(st); //初始化栈st
for (i = 0; str[i] != '\0'; i++) //将str串中的每一个字符依次压入st栈
{
Push(st, str[i]);
}
for (i = 0; str[i] != '\0', i++)
{
Pop(st, e); //将栈顶元素存到e中，并出栈
if (str[i] ！ = e) //如果e不等于str[i]证明不是str对称串
{
DestoryStack(st); //销毁栈st
return false; //返回false
}
}
DestoryStack(st); //销毁栈st
return true; //返回true
}(链栈)判断表达式中的左右括号是否配对
bool Match(char exp[], int n)
{
int i = 0;
char e;
bool match = true; //初始化match为true
LinkStNode *st;
InitStack(st); //初始化链栈st
while (i < n && match)
{
if (exp[i] == '(') //如果exp[i]为左括号
Push(st, exp[i]); //将exp[i]入栈st
else if (exp[i] == ')') //如果exp[i]为右括号
{
if (GetTop(st, e) == true) //判断链栈st是否有栈顶元素，若有取出将栈顶元素的值存在e中
{
if (e != '(') //如果e不是为左括号
match = false; //match置为false
else
Pop(st, e); //将e对应的栈顶元素出栈 match是true
}
else
match = false; //若栈顶没有元素，直接将match置为false
}
i++; // i++，回到while循环
}
if (!StackEmpty(st)) //while循环完成，如果st不是空栈，说明还有左括号留在栈中，没有右括号与它匹配
match = false; //将match置为false
DestoryStack(st); //销毁栈st
return match; //函数返回最终的match值
}队列
队列的定义
队列（queue）是一种线性数据结构，它的特征和行驶车辆的单行隧道很相似。不同于栈的先入后出，队列中的元素只能先入先出 （First In First Out，简称FIFO ）。队列的出口端叫作队头 （front），队列的入口端叫作队尾 （rear）。对于顺序队列SqQuence的声明是：
typedef struct{
ElmeType data[MaxSize]; //存放队列中的数据元素
int front,rear; //队头和队尾指针
}SqQuence;判断队空的条件：q->front == q->rear;
判断队满的条件：q->rear == MaxSize - 1;
元素e的进队操作：先将rear增1，然后将元素e放在data数组的rear位置；
出队操作：先将front增1，然后取出data数组中front位置的元素。
队列的基本操作
- 初始化队列 InitQueue(&q)
- 销毁队列 DestoryQueue(&q)
- 判断是否为空队列 QueueEmpty(q)
入队操作
入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。
//入队操作 顺序队
bool enQueue(SqQueue *&q, ElemType e)
{
if (q->rear == Maxsize - 1) //队已满
return flase;
q->rear++; //队尾增一
q->data[q->rear] = e; //队尾位置插入元素e
return true;
}出队操作
出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。
//出队操作 顺序队
bool deQueue(SqQueue *&q, ElemType &e)
{
if (q->front == q->rear) //队已空
return flase;
q->front++; //队头增一
e = q->data[q->front]; //取队头位置元素
return true;
}环形队列
数组形式的循环(环形)队列
假设一个队列经过反复的入队和出队操作，还剩下2个元素，在“物理”上分布于数组的末尾位置。这时又有一个新元素将要入队。
在数组不做扩容的前提下，如何让新元素入队并确定新的队尾位置呢？我们可以利用已出队元素留下的空间，让队尾指针重新指回数组的首位。
这样一来，整个队列的元素就“循环”起来了。在物理存储上，队尾的位置也可以在队头之前。当再有元素入队时，将其放入数组的首位，队尾指针继续后移即可。
一直到（队尾下标+1）%数组长度 = 队头下标 时，代表此队列真的已经满了。需要注意的是，队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1。
环形队列基本概念
判断队空的条件：q->front == q->rear;
判断队满的条件:（q->rear+1)%MaxSize == q->front;
元素e的进队和出队操作：分别将队尾rear和队头front循环进1。
front = (front + 1)%MaxSize
rear = (rear + 1)%MaxSize
设一个环形队列中数组的下标是0~N-1，队头指针为f(指向队头元素的前一个位置)、队尾指针为r(指向队尾元素)，则其元素个数为(r-f+N)%N。
环形队列进队和出队的代码实现
//环形队列 进队列
bool enQueue(SqQueue *&q, ElemType e)
{
if ((q->rear + 1) % MaxSize == q->front) //队满上溢出
return false;
q->rear = (q->rear + 1) % MaxSize; //队尾指针rear加一
q->data[q->rear] = e; //元素e插入到到队尾
return true;
}
//环形队列 出队列
bool deQueue(SqQueue *&q, ElemType &e)
{
if (q->front == q->rear) //队空下溢出
return false;
q->front = (q->front + 1) % MaxSize; //队首指针rear加一
e = q->data[q->front]; //取出该位置元素赋值给e
return true;
}串
基础知识
串是由0个或多个字符组成的有限序列
串也具有线性存储结构和链式存储结构，前者称为顺序串，后者称为链串。
在顺序串上实现串的基本运算的算法
生成串、串的复制、判断串是否相等、串的连接、求子串、子串的插入、子串的删除、子串的替换、输入串
设S为一个长度为n的字符串，每个字符串各不相同，则有：
S子串个数为n(n+1)/2+1 (含有S本身和空串)
S的非空子串个数为n(n+1)/2
S的互异非空子串个数为n(n+1)/2-1
空串和空格串的区别？
空串不含有任何字符，长度为0，空串是任意串的子串。空格串仅含有空格字符，其长度是串中空格字符的个数。例如：
- 空串：存储 0 个字符的串，例如 S = ""（双引号紧挨着）；
- 空格串：只包含空格字符的串，例如 S = " "（双引号包含3个空格）
求串s中出现的第一个最长连续字符子串的下标和长度
//函数传入了一个串s，得到第一个最长连续相同字符构成的子串
void LongestString(SqString s, int &index, int &maxlen)
{
int length, i = 1, start; //length保存子串的长度
index = 0; //index表示最终找到的子串在s中开始的位置
maxlen = 1; //maxlen保存其长度
while (i < s.length) //当i小于s的长度
{
start = i - 1; //用start表示临时子串开始的位置，下标要减一
length = 1; //先将子串长度置为1
while (i < s.length && s.data[i] == s.data[i - 1]) //当i小于s的长度且当前位置的值等于前一个位置的值
{
i++; //表示前后的字符重复 i自增1
length++; //长度加一
}
if (maxlen < length) //上面的while结束后，判断如果length大于maxlen
{
maxlen = length; //将maxlen更新
index = start; //将子串开始的下标更新
}
i++; //i自增1，回到最外层while循环
}
}串的模式匹配
串的模式匹配算法，通俗地理解，是一种用来判断两个串之间是否具有"主串与子串"关系的算法。若两串匹配，子串在主串中的位置，指的是子串首个字符在主串中的位置。
BF算法（暴力算法）
BF算法的平均时间复杂度是O(m*n)，BF 算法的实现过程很"无脑"，不包含任何技巧，在对数据量大的串进行模式匹配时，算法的效率很低，所以要对其进行改进。
代码实现
//传入主串s和子串t，若匹配成功返回子串t在主串s中的位置，若不匹配，返回-1
int BF(SqString s, SqString t)
{
int i = 0, j = 0; //i用于记录主串s当前下标的位置 j用于记录子串t当前下标的位置
while (i < s.length && j < t.length) //遍历子串和主串
{
if (s.data[i] == t.data[j]) //如果子串和主串的对应的字符相同
{
i++; //主串下标后移一位
j++; //子串下标后移一位
}
else //若发现对应字符不相同
{
i = i - j + 1; //主串的当前位置i前进一位
j = 0; //子串的当前位置j回到初始位置
}
}
if (j >= t.length) //匹配成功
return (i - t.lenth); //返回子串在主串中的位置
else //匹配失败
return (-1); //返回-1
}KMP算法
KMP算法是改进的串的模式匹配算法，KMP算法的平均时间复杂度为O(m+n)，KMP算法还可以继续改进。
代码实现
//返回子串t的next数组
void Get_Next(SqString t, int next[])
{
int j, k;
j = 0; //用j扫描t
k = -1; //用k记录t[j]之前与t开头相同的字符个数
next[0] = -1; //设置next[0]的值为-1
while (j < t.length-1 ) //求t所有位置的next值
{
if (k == -1 || t.data[j] == t.data[k]) //t.data[j]表示后缀的单个字符，t.data[k]表示前缀的单个字符
{
j++; //j后移一位
k++; //k后移一位
next[j] = k; //并设置next[j]的值为k
}
else
k = next[k]; //若字符值不相同且k!=-1，将k值回溯
}
}
//返回子串t在主串s中的位置，若不匹配，返回-1
int KMPIndex(SqString s, SqString t)
{
int i = 0; //i用于记录主串s当前下标的位置
int j = 0; //j用于记录子串t当前下标的位置
int next[MAXSIZE]; //初始化一个next数组
Get_Next(t, next); //调用函数Get_Next得到子串t的next数组
while (i < s.length && j < t.length) //i和j都没有越界时继续循环
{
if (j == -1 || s.data[i] == t.data[j]) //当j=-1或s.data[i]与t.data[j]相匹配时，将子串和主串当前下标位置同时后移一位
{
i++;
j++;
}
else //否则就将j回溯
{
j = next[j];
}
}
if (j >= t.length) //如果最后j的值大于等于模式串的值则匹配成功，返回子串位置
return (i - t.length);
else //否则匹配失败 返回-1
return (-1);
}改进的KMP算法
改进的KMP只不过是把next[ ]数组改进成nextval[ ]数组，在代码中多了一个判断：如果后移一位后的t.data[j] = t.data[k]就设置nextval[j]的值为nextval[k]，其余情况下与普通的next[ ]数组的求法一致，对应的KMP算法是一样的思路，改进后的KMP算法的平均时间复杂度还是O(m+n)。
下面是求子串nextval数组的代码
//返回子串t的nextval数组
void Get_Nextval(SqString t, int nextval[])
{
int j, k;
j = 0; //用j扫描t
k = -1; //用k记录t[j]之前与t开头相同的字符个数
nextval[0] = -1; //设置nextval[0]的值为-1
while (j < t.length) //求t所有位置的nextval值
{
if (k == -1 || t.data[j] == t.data[k]) //t.data[j]表示后缀的单个字符，t.data[k]表示前缀的单个字符
{
j++; //j后移一位
k++; //k后移一位
if (t.data[j] != t.data[k]) //判断后移一位的字符是否相同，若不相同设置nextval[j]的值为k
{
nextval[j] = k;
}
else
nextval[j] = nextval[k]; //若相同设置nextval[j]的值为nextval[k]
}
else
k = nextval[k]; //若字符值不相同且k!=-1，将k值回溯
}
}
Comments NOTHING