一、栈
1、栈的基本概念
线性表是具有相同数据类型的n（n≥0）个数据元素的有限 序列，其中n为表长，当n = 0时线
性表是一个空表。若用L命名线性表，则其一般表示为
L = (a1, a2, … , ai, ai+1, … , an)
栈（Stack）是只允许在一端进行插入或删除操作的线性表
栈的基本操作
InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。
Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素
其他常用操作：
StackEmpty(S)：判断一个栈 S 是否为空。若S为空，则返回true，否则返回false。
栈的常考题型
栈的常考题型
2、栈的顺序存储结构
顺序栈的定义
![]()
顺序栈的定义
初始化操作
![]()
初始化操作
进栈操作
![]()
进栈操作
出栈操作
![]()
出栈操作
读栈顶元素操作
![]()
读栈顶元素操作
共享栈：两个栈共用同一片空间。
![]()
共享栈
重要考点
![]()
重要考点
3、栈的链式存储结构
- 在链表中，头插法建立单链表对应着链栈的进栈
- 在链表中，单链表的删除操作对应着链栈的出栈
链栈的定义
![]()
链栈的定义
重要考点
![]()
重要考点
二、队列
1、队列的基本概念
队列的定义：
线性表是具有相同数据类型的n（n≥0）个数据元素的有限 序列，其中n为表长，当n = 0时线
性表是一个空表。若用L命名线性表，则其一般表示为
L = (a1, a2, … , ai, ai+1, … , an)
栈（Stack）是只允许在一端进行插入或删除操作的线性表。
队列（Queue）是只允许在一端进行插入，在另一端删除的线性表。
队列的基本操作
InitQueue(&Q)：初始化队列，构造一个空队列Q。
DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。
EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。
- 其他常用操作
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
重要考点
![]()
重要考点
2、队列的顺序存储结构
初始化操作
![]()
初始化操作
入队操作
![]()
入队操作
循环队列
![]()
循环队列
循环队列的入队操作
![]()
循环队列入队操作
重要考点
![]()
重要考点
3、队列的链式存储结构
链式队列实现
![]()
链式队列
初始化
-
带头结点带头结点初始化
-
不带头结点不带头结点初始化
入队操作
-
带头结点带头结点的入队操作
-
不带头结点不带头结点的入队操作
出队操作
-
带头结点带头结点的出队操作
-
不带头结点不带头结点的出队操作
队列满的条件
- 链式存储——一般不会队满，除非内存不足。
重要考点
![]()
重要考点
4、双端队列
双端队列图示
![]()
双端队列
受限制的双端队列
![]()
受限制双端队列
考点： 判断输出序列合法性
重要考点
![]()
重要考点
三、栈和队列的应用
1、栈在括号匹配中的应用
括号匹配问题
![]()
括号匹配
算法思路图示
![]()
算法图示
算法实现
![]()
算法实现
重要考点
用栈实现括号匹配：
依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。
匹配失败情况：
①左括号单身②右括号单身③左右括号不匹配
2、栈在表达式求值中的应用
算数表达式由三个部分组成：操作数、运算符、界限符(界限符是必不可少的，反映了计算的先后顺序)
常用的算术表达式都是中缀表达式，在此基础上，人们转化了前缀表达式和后缀表达式
- 中缀表达式：运算符在两个操作数中间。
- 前缀表达式：运算符在两个操作数前面。
- 后缀表达式：运算符在两个操作数后面。
中缀转后缀的手算方法：
① 确定中缀表达式中各个运算符的运算顺序。
② 选择下一个运算符，按照「左操作数 右操作数 运算符」的方式组合成一个新的操作数。
③ 如果还有运算符没被处理，就继续 ②。
后缀表达式的手算方法：
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数。
注意：两个操作数的左右顺序。
用栈实现后缀表达式的计算（计算机）：
①从左往右扫描下一个元素，直到处理完所有元素
②若扫描到操作数则压入栈，并回到①；否则执行③
③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①
中缀转前缀的手算方法：
① 确定中缀表达式中各个运算符的运算顺序
② 选择下一个运算符，按照「运算符 左操作数 右操作数」的方式组合成一个新的操作数
③ 如果还有运算符没被处理，就继续 ② - “右优先”原则：只要右边的运算符能先计算，就优先算右边的。
重要考点
![]()
重要考点
3、栈在递归中的应用
函数调用的过程
![]()
函数调用
重要考点
函数调用的特点：最后被调用的函数最先执行结束（LIFO）
函数调用时，需要用一个“函数调用栈” 存储：
① 调用返回地址
② 实参
③ 局部变量
递归调用时，函数调用栈可称为“递归工作栈”
每进入一层递归，就将递归调用所需信息压入栈顶
每退出一层递归，就从栈顶弹出相应信息
- 缺点：效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算
4、队列在层次遍历中的应用
该过程简单的描述如下：
① 根节点入队。
② 若队空（所有节点都已经处理完毕），则遍历结束；否则重复③操作。
③ 队列中第一个节点出队，并访问之。若其有左孩子，则将左孩子入队，若其有右孩子，则将右孩子入队，返回②。
上图二叉树的层次遍历过程如下
| 序 | 说明 | 队内 | 队外 |
|---|---|---|---|
| 1 | 1入队 | 1 | |
| 2 | 1出队，2、3入队 | 2、3 | 1 |
| 3 | 2出队，4、5入队 | 3、4、5 | 1、2 |
| 4 | 3出队，6、7入队 | 4、5、6、7 | 1、2、3 |
| 5 | 4出队 | 5、6、7 | 1、2、3、4 |
| 6 | 5出队，8、9入队 | 6、7、8、9 | 1、2、3、4、5 |
| 7 | 6出队 | 7、8、9 | 1、2、3、4、5、6 |
| 8 | .... | .... | ..... |
5、队列在计算机系统中的应用
多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service，先来先服务）是一种常用策略。
四、特殊矩阵的压缩方式
1、数组的定义
数组是由n个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称之为该元素的下标，下标的取值范围称为数组的维界。
2、数组的储存结构
各数组元素大小相同，且物理上连续存放。
数组元素a[i] 的存放地址 = LOC + i * sizeof(ElemType) (0≤i<10)
3、矩阵的压缩储存
普通矩阵的存储
可用二维数组存储某些特殊矩阵可以压缩存储空间。
- 注意：描述矩阵元素时，行、列号通常从 1 开始；而描述数组时通常下标从0开始
（具体看题目给的条件，注意审题！）
对称矩阵的压缩存储
若 n 阶方阵中任意一个元素 ai,j都有 ai,j = aj,i
则该矩阵为对称矩阵
下三角区：i>j
上三角区：i<j
主对角线：i=j
普通存储：n*n 二维数组
压缩存储策略：只存储主对角线+下三角区（或主对角线+上三角区）
策略：只存储主对角线+下三角区，按行优先原则将各元素存入一维数组中。
三角矩阵的压缩存储
下三角矩阵：除了主对角线和下三角区，其余的元素都相同。
上三角矩阵：除了主对角线和上三角区，其余的元素都相同。
压缩存储策略：按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c。
三对角矩阵的压缩存储
三对角矩阵，又称带状矩阵：
当 |i - j|>1 时，有 ai,j = 0 （1≤ i, j ≤n）
压缩存储策略：
按行优先（或列优先）原则，只存储带状部分。
4、稀疏矩阵
非零元素远远少于矩阵元素的个数
压缩存储策略：
顺序存储——三元组 <行，列，值>
5、考点回顾
![]()
考点回顾
