数据结构(3)栈、队列、数组

1 栈

1.1 栈的定义

后进先出【LIFO】

1.2 基本操作

元素进栈出栈 只能在栈顶进行！！！

经常考的题：

穿插的进行进栈和出栈 可能有多个选项

1.3 顺序栈

1.3.1 初始化

下标是从0开始的

1.3.2 进栈

更简单的写法：

1.3.3 出栈

1.3.4 读栈顶元素

有时候栈顶的top指针是指向下一个个的

1.4 共享栈

回收资源这个事情我不用管，系统会自己回收！

1.5 链栈

只能在链头进行操作【带不带头结点 都要会写！！！】

一定要自己写一遍！！！

2 队列

2.1 定义

排队在食堂打饭

先进入的元素先出【FIFO】

2.2 基本操作

2.3 顺序队列

2.3.1 初始化

2.3.2 入队

这里要注意队列满的时候的条件，当rear等于10的时候不能说明已经满了：因为前面的元素可能已经出队了那么我们应该把rear指针指向前面【这时候就用到取模运算！！！】

加入取模运算之后，队列逻辑上就变成了一个循环队列的感觉：

2.4 循环队列

队列已满的条件：必须要牺牲一个存储单元，不能把那个也填上。因为在初始化的时候，front=rear时，判断队列是空的；因此为了加以区分，只能这样了！

2.4.1 入队

这样就可以填上了队列是否已满

2.4.2 出队

2.4.3 判满和判空

【1】牺牲一个存储单元用于判满

有了前后指针可以计算出队列中的元素个数！！！：

就是：(rear+Maxsize-front)%Maxsize[记住！！]

【2】定义size 用于记录对列中有几个元素

【3】设置tag 0表示删除 1表示插入

只有删除会导致队列为空 只有插入会导致队列为满！！！

因此可通过front=rear和tag的值进行综合判断 对列是满还是空！

2.4.4 其他的题

【1】队尾指针指向队尾元素

这样的话可以在初始化的时候有所改动！！！

判空：

判满：

牺牲一个存储单元、增加一个辅助变量!

2.5 队列的链式实现

带头结点和不带头节点

2.5.1 初始化

2.5.2 入队【在表尾进行】

不带头结点的时候要对第一个元素进行特殊处理：

2.5.3 出队

对最后一个节点出队的时候，要修改的不止头指针还有尾指针哦

当最后一个结点出队的时候操作不太一样！

2.5.4 队列满的条件

一般不会满，但是在顺序存储的时候却很重要

2.5.5 总结

如果总是需要使用length的话，就把length放在一开始初始化的时候！

2.6 双端队列

双端队列：只允许从两端插入和删除，和传统的队列不太一样！

由此可以得到两个变种：输入受限和输出受限队列

【1】考点 ：判断输出序列的合法性！！！

（1）栈【卡特兰数】

（2）输入受限的双端序列

在栈里合法的，在这里也一定合法！

（3）输出受限的双端序列

【2】总结

3 栈和队列的应用

3.1 栈在括号匹配中的应用

IDE可视化编译器，括号必须是成双成对的

注意：最后出现的左括号最先被匹配【LIFO】，每出现一个右括号就要消耗一个左括号【出栈】！

就是说可以把从左到右进行扫描，遇到左括号就压入栈中 遇到右括号就出栈最后一个入栈的元素和其匹配，匹配成功就继续扫描，直到扫描结束时栈为空 说明括号匹配成功！

尝试不使用基本操作，只是使用指针判断是否匹配！

3.2 栈在表达式求值中的应用

后缀表达式在应用中会更加的广泛，也叫做逆波兰表达式1

注意表达式转换时有严格的左右关系！！！！不能乱哦！！！

3.2.1 中缀表达式转后缀表达式

【1】手算

可以看出中缀表达式中运算的顺序就是后缀表达式中 运算符出现的顺序，但是一个中缀表达式可能有多个后缀表达式，这样不妨方便机算，因此要有一个“左优先原则”如下：

左优先：只要左边的可以先计算，就有限算左边的！！！

【2】机算

这素考试的重点！！！！

3.2.2 后缀表达式的运算

3.2.3 后缀表达式运算【栈】

特点最后出现的操作数最先被运算：意思就是当扫描到运算符的时候 与运算符挨的最近的两个元素先运算！这样就满足栈的定义【LIFO】【后进先出】

具体的操作过程：

！！！中缀转后缀和后缀的运算两个算法结合

都是从左往右进行的！所以就有了下面的：

用笔写一下！！！！！！

3.2.4 中缀转前缀

右优先：会让一样！很爽的结果！

3.2.5 前缀表达式代码实现【栈】

从右向左扫描！ 实现的时候注意先出来的是左操作数！！！

3.2.6 总结

算法必须有确定性！

所以给前缀表达式和后缀表达式加了很多限制！

3.3 栈在递归中的应用

3.3.1 函数调用的过程

所以在func1中修改ab的值main函数中的ab值不会改变，因为改的就不是一个东西！

3.3.2 栈在递归中的应用

递归层数越多 身高约高！

红色箭头是调用的顺序，根据图可以看出有些值会被计算两次，这就是递归算法不太高效的原因之一

3.4 队列的应用

树的层次遍历：树结构的结点一层一层的遍历

【过程：加入一个结点，然后把他的左右子结点加在队尾，当一个结点的左右结点都在的话他就可以出队】

图的广度优先遍历：

思想和树差不多

队列在操作系统中的应用：

4 数组和特殊矩阵

4.1 数组

一维数组：

元素种类相同那么存储的大小也是相同的！

二维数组：

行有限和列优先可以把本来不是线性的结构拉成线性的!计算机存储的空间都是线性的：当给出行号和列好计算机就可以计算出这个元素在计算机中的存储地址，也就是说二维数组也具有随机存储的特性！

4.2 矩阵的存储

4.2.1 普通矩阵

4.2.2 对称矩阵

最喜欢考查的点：在已知行号和列号时怎么创造映射函数得到数组的下标

比如：行优先时：

当i>j时：

当i<j时：

4.2.3 三角矩阵

重点存储不是常量的区域：和对称是一样的

4.2.4 三对角矩阵（带状矩阵）

一共有3n-2个元素！

4.2.4 稀疏矩阵

创建struct 然后按照依次扫描的方法得到矩阵上的值，但是失去了随机存储的功能，因此有下面的十字链表法

总结：

坑可能在下标是不是从零开始的！