目录
一、栈（Stack）基本概念
1.栈的定义
2.栈的基本操作
3.常考题型
4.总结
二、栈的实现
1.顺序存储方式实现-顺序栈
(1)顺序栈定义
(2)顺序栈常用操作
①初始化
②进栈操作
③出栈操作
④读取栈顶元素
(3)共享栈
(4)总结
2.栈的链式存储
(1)链栈定义（跟链表一样）
(2)链栈的常用操作
①进栈
②出栈
③查栈内元素
(3)总结
3.栈相关易错习题总结
(1)选择题
(2)简答题
三、栈的应用
1.括号匹配问题
2.表达式求值问题
(1)表达式相关术语
(2)后缀表达式计算
(3)前缀表达式的计算
(4)总结
3.前、中、后缀表达式之间的转换
(1)中缀表达式转后缀表达式
(2)中缀表达式转前缀表达式
4.中缀表达式相关知识点再整理
(1)中缀表达式转后缀表达式的计算过程(用栈来实现)
(2)中缀表达式的计算(用栈来实现)
5.栈在递归中的作用
四、队列Queue
1.队列的定义
2.队列的常见操作
3.队列的顺序实现
(1)代码定义顺序实现
(2)初始化
(3)入队列操作
(4)循环队列（很常考！！！重点重点重点！！！）
①循环队列的入队操作：
②循环队列的出队操作
③判断循环队列是否已满或者已空
(5)总结
4.队列的链式实现
(1)代码定义
(2)初始化
(3)入队操作
(4)出队操作
(5)队列满的判断
(6)总结
5.双端队列
(1)栈、队列、双端队列结构对比
(2)双端队列类型
(3)双端队列的输出合法性（重点题型，易考题！！）
①栈的输出合法序列
②输入受限的双端队列
③输出受限的双端队列
(4)总结
6.队列相关易错习题总结
(1)选择题
(2)简答题
五、队列的应用
1.树的层序遍历
2.图的广度优先遍历
3.队列在操作系统中的应用
4.习题总结
(1)简答题
六、矩阵的压缩存储
1.数组的存储结构
(1)一维数组
(2)二维数组
2.特殊矩阵的存储（不要背公式）
(1)对称矩阵
(2)三角矩阵
(3)三对角矩阵
(4)稀疏矩阵
(5)总结
(6)常见问题
3.易错题总结
(1)选择题
七、本章归纳总结
八、参考
一、栈（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数据结构考研复习指导-王道论坛》
欢迎大家交流学习，如有错误请批评指正！
下一章：字符串
