导图社区 栈和队列-数据结构第3章
后缀表达式求值:从左往右扫描,每遇到一个运算符,就将<左操作数 右操作数 运算符>变为<左操作数 运算符 右操作数>的形式。
编辑于2022-10-18 23:38:21 江苏省第三章 栈和队列 数据结构 王道考研系列
栈(Stack)
定义
一种操作受限的线性表,只能在栈顶插入、删除
特性:先进后出(Last in first out,LIFO)
术语:栈顶、栈底、空栈
基本操作
创、销
增、删(元素进栈、出栈,只能在栈顶操作)
查(获得栈顶元素,但不删除)
判空
栈的顺序存储结构
顺序栈
顺序存储,用静态数组方式实现,并需要记录栈顶指针
基本操作
创(初始化)
增(进栈)
删(出栈)
查(获取栈顶元素)
判空、判满
都是O(1)时间复杂度
两种实现
初始化时 top = -1
入栈
出栈
获得栈顶元素
x=S.data[s.top] ;
栈空/栈满条件是?
栈空条件
S.top == -1;
栈满条件
S.top == MaxSize-1;
栈长
S.top + 1
初始化时 top = 0
入栈
出栈
获得栈顶元素
x=S.data[S.top-1];
栈空/栈满条件是?
栈空条件
S.top == 0;
栈满条件
S.top == MaxSize;
共享栈
两个栈共享同一片内存空间,两个栈从两边往中间增长
初始化
0号栈 栈顶指针初始化时 top1 = -1;
1号栈 栈顶指针初始化时 top1 = MaxSize;
栈满条件
top0 + 1 == top1;
栈的链式存储结构
用链式存储方式实现的栈
两中实现方式
带头结点
不带头结点
基本操作
创(初始化)
增(进栈)
删(出栈)
查(获取栈顶元素)
判空、判满
队列(Queue)
队列的基本概念
定义
一种操作受限的线性表,只能在队尾插入、在队头删除
特性:先进先出(first into first out,FIFO)
术语
队头、队尾、空队列、队头元素、队尾元素
基本操作
创、销
增、删(入队、出队,只能在规定的一端进行)
查(获得队头元素,但不删除)
判空
队列的顺序存储结构
用顺序存储实现队列
基本操作
创(初始化)
增(进队)
删(出队)
查(获取队头元素)
判空、判满(进行增/删/查操作前的必要判断)
循环队列
循环队列的操作
队列的链式存储结构
用链式存储实现队列
带头结点
不带头结点
基本操作
创(初始化)
增(进队)
注意一个元素入队
删(出队)
注意最后一个元素出队
查(获取队头元素)
判空、判满(进行增/删/查操作前的必要判断)
双端队列
双端队列
允许从两端插入、两端删除的队列
输入受限的双端队列
允许从两端删除、从另一端插入的队列
输出受限的双端队列
允许从两端插入、从另一端删除的队列
考点:对输出序列合法性的判断
栈和队列的应用
栈在括号匹配中的应用
用栈实现括号匹配:
依次扫描所有字符
遇到左括号入栈
遇到右括号则弹出栈顶元素检查是否匹配。
匹配失败情况:
①左括号单身
②右括号单身
③左右括号不匹配
栈在表达式求值中的应用
概念
运算符、操作数、界限符(DIY概念:左操作数/右操作数)
三种算数表达式
中缀表达式
运算符在操作树中间
后缀表达式(逆波兰式)
运算符在操作数后面
前缀表达式(波兰式)
运算符在操作数前面
后缀表达式相关考点
中缀表达式转后缀表达式
①按“左优先”原则确定运算符的运算次序
②根据①中确定的次序,依次将各个运算符和与之相邻的两个操作数按<左操作数 右操作数 运算符>的规则合体
后缀表达式求值
从左往右扫描,每遇到一个运算符,就将<左操作数 右操作数 运算符>变为<左操作数 运算符 右操作数>的形式
计算
从左往右扫描,遇到操作数入栈,遇到运算符则弹出两个栈顶元素运算后入栈(注意:先弹出的元素是“右操作数”)
前缀表达式相关考点
中缀表达式转前缀表达式
①按“右优先”原则确定运算符的运算次序
②根据①中确定的次序,依次将各个运算符和与之相邻的两个操作数按<运算符 右操作数 左操作数>的规则合体
前缀表达式求值(用栈实现)
从右往左扫描,遇到操作数入栈,遇到运算符则弹出两个栈顶元素运算后入栈(注意:先弹出的元素是“左操作数”)
栈在递归中的应用
函数调用的特点:
最后被调用的函数最先执行结束(LIFO)
函数调用时,需要用一个“函数调用栈” 存储:
递归调用时,函数调用栈可称为“递归工作栈”
缺点:效率低,太多层递归可能会导致栈溢出;可能包含很多重复计算
队列在遍历中的应用
树的层次遍历
图的广度优先遍历
队列在计算机系统中的应用
多个进程争抢着使用有限的系统资源时,FCFS(First Come First Service,先来先服务)是一种常用策略
矩阵的压缩存储
数组的存储结构
一维数组
二维数组
特殊矩阵
对称矩阵
特点:对方阵中的任意一个元素,有aᵢ,ⱼ=aⱼ,ᵢ
压缩:只存储主对角线+下三角区(或主对角线+上三角区)
三角矩阵
特点:上三角区全为常量(下三角矩阵);或下三角区全为常量(上三角矩阵)
压缩:按行优先/列优先规则依次存储非常区域,并在最后一个位置存放常量c
三对角矩阵(带状矩阵)
特点:当|i-j|>1时,有aᵢ,ⱼ=0(1<=i,j<=n)
压缩:按行优先/列优先规则依次存储带状区域
稀疏矩阵
非零元素个数远小于零元素个数
压缩:只存储非零元素
顺序存储:顺序存储三元组<行,列,值>
链式存储:十字链表法
常见考题
矩阵的压缩存储需要多长的数组
由矩阵行列号<i,j>推出对应的数组下标号k
数列求和
由k推出<i,j>
如何处理不等式中的“刚好大于等于/小于等于”
向上取整/向下取整
易错点
存储上三角?下三角?
行优先?列优先
矩阵元素的下标从0?1?开始
数组下标从0?1?开始
队列的顺序实现
实现思想
用静态数组存放数据元素,设置队头 /队尾指针(front/rear)
循环队列:用模运算(取余)将存储空间在逻辑上变为“环状”
模运算
重要考点
如何 初始化、入队、出队
如何 判空、判满
如何 计算队列的队列
分析思路
确定front、rear指针的指向
①rear指向队尾元素后一个位置
②rear指向队尾元素
确定判空、判满的方法
a.牺牲一个存储单元
b.增加size变量记录队列长度
c.增加tag = 0/1用于标记最近的一次操作是 出队/入队
...