《数据结构与算法栈与队列》由会员分享，可在线阅读，更多相关《数据结构与算法栈与队列（75页珍藏版）》请在金锄头文库上搜索。
1、 数据结构与算法数据结构与算法 第三章第三章 栈与队列栈与队列 第三章第三章 栈与队列栈与队列 教学目标 1 掌握栈和队列的特点 并能在相应的应用 问题中正确选用 2 熟练掌握栈的两种存储结构的基本操作实 现算法 特别应注意栈满和栈空的条件 3 熟练掌握循环队列和链队列的基本操作实 现算法 特别注意队满和队空的条件 第三章第三章 栈与队列栈与队列 本章重点难点 重点 重点 栈和队列的逻辑结构定义以及在栈和队列的逻辑结构定义以及在 两种两种 顺序顺序 链式链式 存储结构上如何实现存储结构上如何实现 栈和队列的基本运算栈和队列的基本运算 难点 难点 循环队列的边界处理循环队列的边界处理 3 1 3
2、 1 栈栈 栈栈 是一种特殊的线性结构 只能在一端进行 是一种特殊的线性结构 只能在一端进行 插入和删除的线性表 插入和删除的线性表 栈的相关概念栈的相关概念 1 1 栈顶 线性表中进行插入删除的一端 栈顶 线性表中进行插入删除的一端 2 2 栈底 与栈顶对应的一端 栈底 与栈顶对应的一端 3 3 入栈 插入元素 入栈 插入元素 push push 压栈 压栈 4 4 出栈 删除元素 出栈 删除元素 pop pop 弹出 弹出 1 2 3 栈的结构模拟 特点 后进先出 栈顶 栈底 栈是一种特殊的线性表 它只能在表的一端 栈顶 进行插入和删除运算 栈与一般线性表的区别 仅在于运算规则不同 进 压
3、入 PUSH 出 弹出 POP 一般线性表 逻辑结构 一对一 存储结构 顺序表 链表 运算规则 随机 顺序存取 栈 逻辑结构 一对一 存储结构 顺序栈 链栈 运算规则 后进先出 栈与一般线性表的区别 a1 a2 an 顺序栈S ai 表头 表尾 栈底base 栈顶top 低地址 高地址 写入 v i ai 读出 x v i 压入 PUSH an 1 弹出 POP x 前提 一定要预设栈顶指针top 低地址 高地址 v i a1 a2 ai an 顺序表V n an 1 顺序栈与顺序表 3 1 1 3 1 1 栈的基本运算栈的基本运算 l l 入栈入栈 l l 出栈出栈 l l 读取栈顶元素读取
4、栈顶元素 l l 栈是否为空等栈是否为空等 栈的抽象数据类型定义栈的抽象数据类型定义 Tempate Class Stack void clear bool Push const T value bool Pop T bool Top T bool isEmpty bool isFull 3 1 2 3 1 2 栈的物理实现栈的物理实现 顺序栈顺序栈 相关变量相关变量 1 1 栈的最大长度 栈的最大长度 int mSizeint mSize 2 2 栈顶的位置 栈顶的位置 int topint top 3 3 栈的指针变量 栈的指针变量 T stT st 栈顶位置top的选择影响算法时间复杂度
5、 template class arrStack private int mSize 栈的最大长度 int top 栈顶下标 T st 指向栈的指针 public arrStack int size mSize size top 1 st new T mSize 栈的顺序实现 arrStack top 1 arrStack delete st void Clear 清空栈栈的内容 top 1 入栈操作的顺序实现 图3 3 bool Push const T item if top mSize 1 cout stack is full endl 判断是否上溢出 return false else
6、 st top item return true 出栈的顺序实现 图3 3 bool Pop T return false else item st top return true void Show 显显示栈栈元素 int i for i 0 i top i cout st i cout endl 改改进进进进的的进栈进栈进栈进栈 操作操作 算法算法3 33 3 P50P50 需要注意的两个问题需要注意的两个问题 n n TopTop的两种定义方式的两种定义方式 TopTop为栈中第一个空闲位置为栈中第一个空闲位置 TopTop为栈顶元素位置为栈顶元素位置 n n 栈中元素动态变化栈中元素动
7、态变化 上溢出上溢出 overflow overflow 下溢出下溢出 underflow underflow 3 1 3 3 1 3 栈的物理实现栈的物理实现 链式栈链式栈 相关变量相关变量 1 1 栈顶的位置 栈顶的位置 Link topLink top 2 2 栈中元素的个数 栈中元素的个数 int sizeint size 4321 top 栈顶栈底 运算是受限的单链表 只能在链表头部进行操作 故 没有必要附加头结点 栈顶指针就是链表的头指针 template class Link 结点类型 Link类模板 public T data 结点的数据域 Link next 结点的指针域 L
8、ink T info Link nextValue NULL 具有两个参数的List构造函数 data info next nextValue Link Link nextValue NULL 具有一个参数的List构造函数 next nextValue 栈的链式实现 template class lnkstack private Link top 指向栈顶的指针 int size 存放元素的个数 public lnkstack top NULL size 0 lnkstack clear 清空栈栈内容 void clear while top NULL Link tmp top top to
9、p next delete tmp size 0 入栈操作的链式实现 bool push const T item Link tmp new Link item top top tmp size return true 出栈的链式实现 bool pop T if size 0 cout 栈为空 不能执行出栈操作 data tmp top next delete top top tmp size return false 取栈顶元素 bool topp T return true 显示栈中所有元素 void show Link p top while p cout data p p next c
10、out NULL N cin N while N while N push N 8 push N 8 N N 8 N N 8 while isEmpty while isEmpty pop e pop e cout e cout e 3 1 4 3 1 4 栈的应用栈的应用 表达式求值表达式求值 表达式的中缀表示法 运算符在两个操作数之表达式的中缀表示法 运算符在两个操作数之 间 间 先括号内 后括号外 先乘除后加减 其运先括号内 后括号外 先乘除后加减 其运 算次序受括号和运算符优先级的影响算次序受括号和运算符优先级的影响 表达式的后缀表示法 表达式的后缀表示法 为了能够使计算机完成四则混合
11、运算 可将为了能够使计算机完成四则混合运算 可将 中缀表示法转换为后缀表示法中缀表示法转换为后缀表示法 23 34 45 5 6 7 3 1 4 3 1 4 栈的应用栈的应用 表达式求值表达式求值 表达式的中缀表示法表达式的中缀表示法 23 34 45 5 6 7 表达式的后缀表示法 表达式的后缀表示法 23 34 45 5 6 7 后缀表示法中 无括号 操作数在运后缀表示法中 无括号 操作数在运 算符的前面算符的前面 中缀到后缀中缀到后缀的的转换规则转换规则 1 当输入的是操作数时 直接输出到后缀表达 式PostfixExp序列 2 当输入的是开括号时 也把它压栈 3 当输入的是闭括号时 先
12、判断栈是否为空 若为空 括号不匹配 应该当错误异常处理 清 栈退出 若非空 则把栈中的元素依次弹出 直到 遇到第一个开括号为止 将弹出的元素输出到后缀 表达式PostfixExp的序列中 弹出的开括号不放到 序列中 若没有遇到开括号 说明括号也不匹配 做异常处理 清栈退出 转换规则转换规则 4 当输入的是运算符时 a 循环 当 栈非空 and 栈顶不是开括号 and 栈顶运算符的优先级不低于输入的运算符 的优先级 时 反复操作将栈顶元素弹出 放 到后缀表达式序列中 b 把输入的运算符压栈 5 最后 当中缀表达式InfixExp的符号序列全 部读入时 若栈内仍有元素 把它们全部依次弹出 都放到后
13、缀表达式PostfixExp序列尾部 若弹出 的元素遇到开括号时 则说明括号不匹配 做错误 异常处理 清栈退出 输入序列 23 34 45 5 6 7 输出序列 23 34 45 5 6 7 前缀表达式转换为后缀表达式 前缀表达式转换为后缀表达式 后缀表达式求值后缀表达式求值 循环 依次顺序读用户键入的符号序列 组成并判 别语法成分的类别 1 当遇到的是一个操作数 则压入栈顶 2 当遇到的是一个运算符 就从栈中两次取出栈 顶 按照运算符对这两个操作数进行计算 然 后将计算结果压入栈顶 如此继续 直到遇到符号 这时栈顶的值就是输 入表达式的值 23 34 45 5 6 7 23 34 45 15
14、30 23 34 45 5 6 7 23 1530 5 6 11 23 34 45 5 6 7 23 1530 11 7 18 23 34 45 5 6 7 23 1530 18 85 23 34 45 5 6 7 23 85 108 23 34 45 5 6 7 108 3 2 3 2 队列队列 队列队列 是一种特殊的线性结构 只能在一端进 是一种特殊的线性结构 只能在一端进 行插入 在另一端进行删除的线性表 行插入 在另一端进行删除的线性表 队列的相关概念队列的相关概念 1 1 队头 队头 fromfrom 允许删除的一端 允许删除的一端 2 2 队尾 队尾 rearrear 允许插入的一
15、端 允许插入的一端 3 3 入队 插入元素 入队 插入元素 4 4 出队 删除元素 出队 删除元素 123 队列的结构模拟 特点 先进先出 队尾 队头 4 3 2 3 2 队列队列 队列队列 是一种特殊的线性结构 只能在一端进 是一种特殊的线性结构 只能在一端进 行插入 在另一端进行删除的线性表 行插入 在另一端进行删除的线性表 队列的相关概念队列的相关概念 1 1 队头 队头 fromfrom 允许删除的一端 允许删除的一端 2 2 队尾 队尾 rearrear 允许插入的一端 允许插入的一端 3 3 入队 插入元素 入队 插入元素 4 4 出队 删除元素 出队 删除元素 23 队列的结构模
16、拟 特点 先进先出 队尾 队头 4 3 2 1 3 2 1 队列的基本运算队列的基本运算 l l 入队入队 l l 出队出队 l l 读取队头元素读取队头元素 l l 队是否为空等队是否为空等 队的抽象数据类型定义队的抽象数据类型定义 Tempate Class Queue bool enQueue const T value bool deQueue T bool getFront T bool isEmpty 3 2 2 3 2 2 队列的物理实现队列的物理实现 顺序队列顺序队列 相关变量相关变量 1 1 队列的最大长度 队列的最大长度 int maxsizeint maxsize 2 2 队首 队首 int frontint front 3 3 队尾 队尾 int rearint rear 4 4 指向队列的指针 指向队列的指针 T quT qu 3 2 2 3 2 2 队列的物理实现队列的物理实现 顺序队列顺序队列 队首队尾的确定队首队尾的确定 front rear 情况1 队首固定 入队 O 1 出队 O n 初始队列为空 front rear 1 1 2 2 3 3 fro
