栈
定义
- 只能在栈顶进行插入和删除的线性表
- 后进先出结构
- 重要的数学结论：n个不同的元素，进栈顺序已知，则出栈顺序不同的排列有
顺序存储
- 利用连续存储单元存放元素，同时附设一个栈顶指针top
- top可以表示栈顶元素的下标（非空情况从0开始），也可以表示栈顶元素的位序(数值上等于栈大小，非空情况从1开始)
- 前者空栈时，top为-1；后者空栈时top为0
- 前者进栈为
，后者进栈为 - 前者出栈为
，后者出栈为 - 共享栈
- 将两个栈的栈底设置在一维数组的两端，栈顶向内延申共享空间。
- 以top表示栈顶元素下标为例
时1栈为空 时2栈为空 时栈满
链式存储
- 采用链式存储的栈，优点是便于多个栈共享存储空间，提高效率，不存在栈满上溢的情况。
- 通常用单链表实现，所有操作在表头进行
- 对于带头结点和不带头结点的链栈，具体的实现会有不同
队列
定义
- 只能在队头删除，在队尾插入的受限线性表
- 先进先出
顺序存储
- 使用连续的存储单元存放队列中的元素，附设指针front和rear。（不同教材指针定义不唯一，本笔记规定front表示队头位置，rear表示队尾元素的下一个位置）
- 使用顺序队列存在假溢出问题，即下标到了Maxsize，但是数组中还有空位置
- 可以改进为循环队列
- 初始：
- 入队：
- 出队：
- 队长：
- 这里可以发现，最大容量实际上到不了
，原因队空和队满的判断都是 ，处理方法有三种 - 牺牲一个单元，默认情况，即队满判断是
- 增加一个size记录元素个数，以此区分队满和队空
- 增设tag标记，删除元素后tag为0，插入元素后tag为1。初始tag为0。以此记录最近一次操作是插入还是删除来判断队满和队空
- 牺牲一个单元，默认情况，即队满判断是
- 初始：
链式存储
- 队列的链式称为链队列
- 本质上是同时带有队头指针和队尾指针的单链表
- 不带头结点情况
- 当front和rear都是NULL时，队列为空
- 出队先判断是否空，空则无法出队；不空则front指向其后继。若没有后继，则front和rear都置NULL
- 入队先判断是否空，不空则将新结点插入到rear的后面并更新rear；空则设置front和rear都指向新结点
- 带头结点情况（统一了操作，更方便，front此时就是头结点）
- 当front=rear时，队列为空
- 入队插入到rear后并更新rear
- 出队判断是否空，空则无法出队；不空则删除front的后继。若front后继为rear，则rear=front
- 双端队列
- 普通情况：在两端都可以入队或出队
- 输出受限：只能在一端出队，可在两端入队
- 输入受限：只能在一端入队，可在两端出队
栈和队列的应用
括号匹配
- 问题：假设输入表达式包含圆括号方括号，任意嵌套，要求判断表达式合法性
- 算法：利用栈，遇到左括号压栈，遇到右括号则和栈中左括号进行匹配消解，不匹配则不合法。
表达式求值
- 后缀表达式的值计算：遇到操作数压栈，遇到操作符则弹出操作数进行计算，结果压栈
- 中缀表达式转后缀表达式：
- 人脑方法：利用二叉树的中序遍历和后序遍历得到结果
- 计算机算法
- 遇到数字直接输出到后缀表达式
- 遇到'('入栈
- 遇到')'依次弹出栈，加到后缀表达式，直到弹出了'('，不用加到后缀表达式
- 遇到其他运算符根据优先级规定，可能入栈，可能连续弹出，因为不好记，所以直接对照人脑方法得出的答案即可（仅限笔试）。
递归
- 任何递归算法都可以用栈改成非递归算法
- 当然除了用栈，也可以根据状态转移方程用dp来做
广度优先遍历
又叫做层次遍历，队列的应用
计算机系统
队列在操作系统的资源管理中也有应用：
- 打印机数据缓冲区就是一个数据队列
- cpu资源竞争也是进程的队列。
数组和特殊矩阵
定义
- 数组是由
个( )同类型数据元素构成的有限序列，每个数据元素称为一个数组元素 - 数组下标取值范围叫做维界
- 数组是线性表的推广
- 一维数组可以看作是线性表
- 二维数组可以看作是数据元素是定长线性表的线性表
- 数组一旦被定义，维数和维界都不变
- 除了初始化和销毁，数组只能存取元素、修改元素（不能叫插入和删除，这个应该是和线性表的区别）
存储结构
- 数组本身是逻辑结构，但是大部分计算机语言都提供数组数据类型
- 逻辑意义上的数组可以用计算机语言中的数组数据类型进行存储
， 是每个元素所占的存储单元个数 - 多维数组映射方法(假设m行n列)
- 行优先：
- 列优先：
- 行优先：
矩阵的压缩存储
- 压缩存储：相同值元素只分配一个存储空间，零元素不分配空间，能节约存储
- 特殊矩阵
- 矩阵有很多相同的元素，或很多零元素，并且这些元素分布有一定规律。
- 常见的特殊矩阵：对称矩阵、上三角矩阵、下三角矩阵、对角矩阵、三对角矩阵
对称矩阵
- 只存放下三角部分，包括对角元素，把
用 压缩表示 - 对于
， ，其前面有元素个数 （二维矩阵按行优先展开为一维数组，后同），故其对应于 。数组下标都是从0开始的。
三角矩阵
- 下三角矩阵上三角区域元素为常数
- 上三角矩阵下三角区域元素为常数
- 注意在数学里，这个常数大都是0，但这里认为是某常数C
- 存储和对称矩阵类似，但要多一个位置存储该常数即可
三对角矩阵
- 又叫做带状矩阵，所有非零元素都集中在以主对角线为中心的3条对角线区域
- 同样可以按行优先方式展开到一维数组中
稀疏矩阵
- 对于非零元素个数远少于矩阵元素个数的情况，矩阵为稀疏矩阵
- 采用三元组(行标，列标，值)的方式进行压缩
- 稀疏矩阵压缩后无法随机存取
- 稀疏矩阵的三元组可以用数组存储也可以用十字链表存储
十字链表
- 每一行都有行头结点
- 每一列都有列头结点
- 数据结点除了三元组，还包括列后继指针，行后继指针
