目录
一、栈（Stack）基本概念
1.栈的定义
2.栈的基本操作
(1)初始化栈（InitStack）
InitStack(&S)：初始化栈S，构造一个空栈，并为其分配相应的内存空间。
(2)创建和销毁栈
CreateStack(&S)：创建栈S（通常包含在初始化过程中）。
DestroyStack(&S)：销毁栈S，释放栈S所占用的内存空间。
(3)向栈顶添加元素（Push）
Push(&S, x)：若栈S未满，则将元素x加入栈顶，成为新的栈顶元素。
(4)从栈顶移除元素（Pop）
Pop(&S, &x)：若栈S非空，则弹出栈顶元素，并使用变量x返回该元素的值。
(5)获取栈顶元素（GetTop）
GetTop(S, &x)：若栈S非空，则使用变量x返回栈顶元素的值，但不删除该元素。
(6)其他常用操作
StackEmpty(S)：判断栈S是否为空。若S为空，则返回true，否则返回false。
3.常考题型
给出一个进栈顺序，问有哪些合法的出栈顺序？
例如：进栈顺序为a->b->c->d->e，考试的时候一般会出选择题，问选项中哪种出栈顺序不可能出现？
这里我们给出一个不可能出现的顺序：c->a->b->d->e。（因为c如果第一个出栈，那么栈内元素从栈顶到栈底一定是b、a，b一定会先于a出栈）
那么一共存在多少种不同的出栈顺序呢？可以采用数学归纳法得到一个公式（不要求掌握，作为知识扩展）：
4.总结
二、栈的实现
1.顺序存储方式实现-顺序栈
顺序栈的考察是栈结构的重点，需要关注栈的先进后出特性以及一些重要操作，并学会使用栈解决实际问题
👇🏻👇🏻👇🏻一些顺序栈相关C++代码实现可以参考下面文章👇🏻👇🏻👇🏻
栈相关代码-CSDN博客文章浏览阅读48次。【代码】栈相关代码。
https://blog.csdn.net/hehe_soft_engineer/article/details/134235803
(1)顺序栈定义
使用静态数组定义顺序栈，注意题目中栈顶指针的指向，有的题会将栈顶指针指向栈顶元素，有的会指向距离栈顶最近的空元素位置。
(2)顺序栈常用操作
栈顶元素的指向直接关系到进栈、出栈的代码实现，这个选择题一定要看清楚，这个在下面的④读取栈顶元素时有体现。
①初始化
注意初始化情况时，一般top栈顶指针指向-1
②进栈操作
③出栈操作
注意：只是在逻辑上删除了这个数据
④读取栈顶元素
注意审题：栈顶指向的是栈顶元素还是空位置！！！！
(3)共享栈
两个栈共享一块内存空间，两个栈顶指针的增加方向是相对的，注意栈满时的条件。
(4)总结
2.栈的链式存储
链式存储本质上就是单链表加了操作限制
(1)链栈定义（跟链表一样）
(2)链栈的常用操作
①进栈
②出栈
③查栈内元素
从链头开始遍历，寻找目标元素。
(3)总结
3.栈相关易错习题总结
(1)选择题
问题：
解答：
注意这里的元素是指data！！！
问题：
解答：
注意与C语言的命名规则相结合，并且还要输入顺序，判断合法的输出结构
问题：
解答：
(2)简答题
问题：
解答：
三、栈的应用
1.括号匹配问题
注意下面的流程图，好好理解：
代码也需要掌握，因为在复试的时候很有可能出符号匹配相关的题目
2.表达式求值问题
这块知识点非常重要，也很抽象、容易忘，跟着王道的视频课好好学习并理解，多做几个练习，下面是对主要过程进行总结，如果知识点有点遗忘或看不懂，一定要及时回顾一下视频课！！
中缀表达式转后缀和前缀表达式可以对比着来记忆；
前缀表达式和后缀表达式的计算也可以对比记忆，效果更好。
(1)表达式相关术语
(2)后缀表达式计算
（手算和机算都要掌握，这块容易出题）
(3)前缀表达式的计算
着重注意一下机算过程，手算的时候也可以按照这个过程来求值
(4)总结
3.前、中、后缀表达式之间的转换
(1)中缀表达式转后缀表达式
注意左优先原则
(2)中缀表达式转前缀表达式
中缀转后缀和中缀转前缀对比：
4.中缀表达式相关知识点再整理
说明：这块内容和前面有重叠，但是是对中缀表达式相关知识点的汇总和拓展，其中中缀表达式求值问题是使用了中缀转后缀+后缀表达式求值两个算法结合实现的
(1)中缀表达式转后缀表达式的计算过程(用栈来实现)
(2)中缀表达式的计算(用栈来实现)
5.栈在递归中的作用
四、队列Queue
队列的顺序实现是队列结构考察的重点，需要关注队列先进先出的特性以及一些重要操作，并学会使用队列解决实际问题
👇🏻👇🏻👇🏻一些队列相关C++代码实现可以参考下面文章👇🏻👇🏻👇🏻队列相关代码-CSDN博客文章浏览阅读52次。【代码】队列相关代码。
1.队列的定义
2.队列的常见操作
(1)初始化队列(InitQueue(&Q))：构造一个空队列Q。
(2)销毁队列 (DestroyQueue(&Q))：销毁并释放队列Q所占用的内存空间。
(3)入队(EnQueue(&Q, x))：若队列Q未满，将元素x加入队列，使之成为新的队尾元素。
(4)出队(DeQueue(&Q, &x))：若队列Q非空，删除队头元素，并用变量x返回其值。
(5)读队头元素(GetHead(Q, &x))：若队列Q非空，则将队头元素的值赋给变量x。该操作不删除队头元素。
(6)判断队列空(QueueEmpty(Q))：判断队列Q是否为空。若队列Q为空，返回true；否则返回false。
队列的使用场景中，大多只访问队头元素，而其他元素则按照先入先出的原则进行管理和处理。队列的这些基本操作确保了数据结构的正确性和有效性，是实现各种队列相关算法和应用的基础。
3.队列的顺序实现
(1)代码定义顺序实现
(2)初始化
//初始化队列
void InitQueue(SeqQueue &Q){
Q.rear=0;
Q.front=0;
//Q.rear==Q.front时队列为空
}
(3)入队列操作
//入队操作
bool EnQueue(SeqQueue &Q,int elem){
if((Q.rear+1)%MaxSize==Q.front){//判断队列满
return false;
}else{
Q.data[Q.rear]=elem;
Q.rear=(Q.rear+1)%MaxSize;
return true;
}
}
(4)循环队列（很常考！！！重点重点重点！！！）
这部分最重要的就是掌握判断什么时候队列满和队列空，这块真题里面经常考察，需要对题目里面定义的队列满、空的条件理解清楚。
下面对常见的循环队列情况进行总结：
①循环队列的入队操作：
②循环队列的出队操作
③判断循环队列是否已满或者已空
当题目中说：队尾指针指向队尾元素时的情况：
(5)总结
4.队列的链式实现
(1)代码定义
//链式队列的定义
typedef struct{
LNode *front,*rear;//队头指针和队尾指针
}LinkQueue;
//初始化链式队列
void InitLinkQueue(LinkQueue &Q){
LNode *p=(LNode *)malloc(sizeof(LNode));
Q.front=p;
Q.rear=p;
}
(2)初始化
初始化：定义头指针和尾指针
(3)入队操作
队尾指针rear后插，并更新队尾指针
(4)出队操作
队头指针处删除结点，并可能更新头结点指针
(5)队列满的判断
队列的链式实现不会出现队列满的情况，除非内存不足。
(6)总结
5.双端队列
(1)栈、队列、双端队列结构对比
(2)双端队列类型
(3)双端队列的输出合法性（重点题型，易考题！！）
①栈的输出合法序列
绿色标注的是合法输出序列：
②输入受限的双端队列
绿色标注的是合法输出序列：
③输出受限的双端队列
绿色标注的是合法输出序列：
(4)总结
6.队列相关易错习题总结
(1)选择题
问题：重要，多看几遍，一定牢牢记住
解答：
问题：重要，多看几遍，一定牢牢记住
解答：
问题：
解答：
问题：
解答：
注意D选项和C选项的区别，严谨
问题：
解答：
这里，头指针并不一定在链尾，可能在链内，所以寻找尾指针可能需要O(n)复杂度
问题：
解答：
(2)简答题
问题：
解答：
五、队列的应用
其中 1.树的层序遍历 和 2.图的广度优先遍历 在后续的树、图章节详细介绍。
1.树的层序遍历
2.图的广度优先遍历
3.队列在操作系统中的应用
4.习题总结
(1)简答题
问题：注意算法思想
解答：
六、矩阵的压缩存储
矩阵作为线性代数中的一个核心概念，广泛应用于各个领域，但其存储方式并非总是最优的。因此，对于大型矩阵或者具有特殊结构的矩阵，压缩存储成为了提高效率的关键。
矩阵的压缩存储主要关注于如何在不损失信息的前提下，尽可能地减少存储空间的使用。这种存储方式通常针对具有特殊结构或性质的矩阵。
对于稀疏矩阵元素的存储同样是矩阵存储的重要议题：
稀疏矩阵是一种元素大部分为零的矩阵。对于这类矩阵，存储非零元素的位置和值往往比存储所有元素更为高效。
1.数组的存储结构
(1)一维数组
(2)二维数组
※注意行优先和列优先存储逻辑上和物理上的对应关系
行优先存储：
列优先存储：
2.特殊矩阵的存储（不要背公式）
这部分不要背公式，要自己多去推导一下，这块需要灵活应对。考试的时候一般来说不会考具体公式，会问你第几行第几列的元素存在数组中什么位置，或者反过来问。
(1)对称矩阵
行优先存储：
列优先存储：
(2)三角矩阵
下三角矩阵：
上三角矩阵：
(3)三对角矩阵
(4)稀疏矩阵
①顺序存储
②十字链表法
（注意结点中各部分的含义，理解记忆，很重要！！2024年考试真题刚考过）
(5)总结
(6)常见问题
3.易错题总结
(1)选择题
问题：
解答：
问题：
解答：
看准B数组下标是从哪里开始的
七、本章归纳总结
八、参考
📚课件来源：王道考研
📚课本及题目：《2024数据结构考研复习指导-王道论坛》
欢迎大家交流学习，如有错误请批评指正！
下一章：字符串
