知识要点：

栈的定义、结构特点及其存储方式(顺序存储与链接存储)和基本操作的实现算法；

队列的结构、特点及其存储方式(顺序存储与链接存储)和基本操作的实现算法。

递归的基本概念和实现原理以及用递归的思想描述问题和书写算法的方法；

用栈实现递归问题的非递归解法。

栈的定义：只允许一段进行插入或者删除操作的线性表；该端称为栈顶（top），相反另一端不允许被操作的称为栈底（base）

栈内元素的个数称为栈的大小，不含任何元素的栈称为空栈；

栈的特性：先进后出型（Last In First Out）

栈的存储结构（顺序存取）利用一组连续的内存空间存取(预先开辟内存MaxSize)

1、顺序栈初始化：S.top=-1；S.base=0；

2、入栈操作：S.data[++S.top] （栈不满栈顶指针加一，数据入栈）；

3、出栈操作：S.data[S.top]，S.top-- （栈非空，取栈顶元素，栈顶指针减一）；

4、栈空条件：S.top=-1；栈满条件：S.top-S.base=MaxSize-1；（即S.top=MaxSize-1）

5、对于栈的操作：初始化、栈判空、入栈、出栈、取栈顶元素时间复杂度都为O(1)；

栈的存储结构（链式存取）利用指针标明数据元素之间的的逻辑关系(不用预先开辟内存)

1、链栈初始化：S=NULL；//默认为空栈

2、入栈操作：开辟一个新结点p

p->next=S；S=p；//修改栈顶指针

3、出栈操作：取栈顶元素；保存当前栈顶指针p=S；栈顶指针后移S=S->next；清除原栈顶指针free§；

3、栈空条件：S=NULL；栈满条件：一般不会出现栈满情况；

4、对于栈的操作：初始化、栈判空、入栈、出栈、取栈顶元素时间复杂度都为O(1)；

补充（共享栈）：两端都为栈底，两端的栈底指针分别为S.top1和S.top2；

初始化S.top1=-1以及S.top2=MaxSize+1

入栈操作：先++S.top1或–S.top2，之后进行入栈操作；

出栈操作：先取出数据，之后S.top1–或S.top2++；

栈满操作：S.top2-S.top1=1；（此共享栈相当于一个数组两个栈结构）

n个不同元素入栈得到的出栈序列的个数为：C(n ,2n)/(n+1)；前者为组合数

栈的应用：递归调用、括号匹配、表达式求值（前缀表达式、中缀表达式、后缀表达式）

队列的定义：允许在表的两端进行操作的线性表，一端进行入队(插入)，另一端进行出队(删除)；允许插入的一端称为队尾

允许删除的一端称为队头；

队列内元素个数的数量称为队列长度，不含任何元素的队列称之为空队列；

队列的特性：先进先出型（First In First Out）

队列的存储结构（顺序存取）循环队列防止出现假溢出现象；预先开辟内存MaxSize

1、循环队列的初始化：Q.front=Q.rear=0；

2、入队操作：Q.rear=(Q.rear+1)%MaxSize；

3、出队操作：Q.front=(Q.front+1)%MaxSize；

4、队空条件：Q.front=Q.rear；队满条件：(Q.rear+1)%MaxSize=Q.front；

5、队列的初始化、队判空、入队、出队、求队长（Q.rear-Q.front+MaxSize）%MaxSize时间复杂度都为O(1)；

队列的存处结构（链式存取）

1、链式队列的初始化：Q.front=Q.rear=new QNode；

Q.front->next=NULL；//默认队列为空

2、入队操作：新建一结点p（队首指针通常放在链队的头部）

p->next=NULL，Q.rear->next=p；  //入队    Q.rear=p；//修改队尾指针

3、出队操作：取出队头元素p=Q.front->next，e=p->data；队头指针后移Q.front=p->next；清除队头元素free§

如果被删除的是最后一个元素（即删除此元素队列为空）则：Q.rear=Q.front；//修改队尾指针

4、队空条件：Q.front=Q.rear；

5、队列的初始化、队判空、入队、出队、求队长时间复杂度都为O(1)；

补充（双端队列）：两端均可以进行插入或者删除操作的队列；

队列的应用：树的层次遍历以及图的广度遍历、计算机内缓冲区的设置；
————————————————
版权声明：本文为CSDN博主「梦想之深邃」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/m0_37848958/article/details/82834075