第3章 栈和队列

第三章栈和队列 本章内容3 1栈3 1 1栈的定义及基本运算3 1 2栈的存储结构和实现3 1 3栈的应用3 2队列3 2 1队列的定义及基本运算3 2 2队列的存储结构和实现3 2 3队列的应用 1 3 1 1栈的定义及基本运算 栈 Stack 的定义 栈 Stack 是限制在表尾进行插入和删除运算的线性表 表尾端称为栈顶 top 表头端称为栈底 bottom 当表中没有元素时称为空栈 入栈 出栈 栈S a1 a2 a3 an a1称为栈底元素 an为栈顶元素 栈中元素是按a1 a2 a3 an的次序进栈的 退栈的第一个元素应为栈顶元素an 2 3 1 1栈的定义及基本运算 栈的运算演示 1 A B C D四个元素依次进入一个栈 再依次出栈 得到一个输出序列DCBA ABCD DCBA 栈的特点栈的修改是按后进先出的原则进行的 因此 栈称为后进先出表 LIFO 3 3 1 1栈的定义及基本运算 栈的运算演 2 能否由入栈序列A B C D E得到出栈序列CBDAE ABCDE 操作序列 出栈序列 元素A入栈 A A 元素B入栈 B B 元素C入栈 C C 4 3 1 1栈的定义及基本运算 栈的运算演示 2 能否由入栈序列A B C D E得到出栈序列CBDAE DE 操作序列 出栈序列 元素A入栈 A 元素B入栈 B 元素C入栈 元素C出栈 C C 元素B出栈 B 5 3 1 1栈的定义及基本运算 栈的运算演示 2 能否由入栈序列A B C D E得到出栈序列CBDAE DE 操作序列 出栈序列 元素A入栈 A 元素B入栈 元素C入栈 元素C出栈 C 元素B出栈 B 元素D入栈 D D 元素D出栈 D 元素A出栈 A 6 3 1 1栈的定义及基本运算 栈的运算演示 2 能否由入栈序列A B C D E得到出栈序列CBDAE E 操作序列 出栈序列 元素A入栈 元素B入栈 元素C入栈 元素C出栈 C 元素B出栈 B 元素D入栈 元素D出栈 D 元素A出栈 A 元素E入栈 E E 元素E出栈 E 7 例3 1设有4个元素a b c d进栈 给出它们所有可能的出栈次序 答 所有可能的出栈次序如下 abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba 8 例3 2设一个栈的输入序列为A B C D 则借助一个栈所得到的输出序列不可能是 A A B C D B D C B A C A C D B D D A B C 答 可以简单地推算 得容易得出D A B C是不可能的 因为D先出来 说明A B C D均在栈中 按照入栈顺序 在栈中顺序应为D C B A 出栈的顺序只能是D C B A 所以本题答案为D 9 例3 3已知一个栈的进栈序列是1 2 3 n 其输出序列是p1 p2 pn 若p1 n 则pi的值 A i B n i C n i 1 D 不确定 答 当p1 n时 输出序列必是n n 1 3 2 1 则有 p2 n 1 p3 n 2 pn 1推断出pi n i 1 所以本题答案为C 10 例3 4设n个元素进栈序列是1 2 3 n 其输出序列是p1 p2 pn 若p1 3 则p2的值 A 一定是2 B 一定是1 C 不可能是1 D 以上都不对 答 当p1 3时 说明1 2 3先进栈 立即出栈3 然后可能出栈 即为2 也可能4或后面的元素进栈 再出栈 因此 p2可能是2 也可能是4 n 但一定不能是1 所以本题答案为C 11 栈的基本运算 1 初始化栈InitStack S 2 入栈Push S e 3 出栈Pop S e 4 获取栈顶元素GetTop S e 5 判断栈是否为空StackEmpty S 3 1 1栈的定义及基本运算 12 3 1 2栈的存储结构和实现 栈 顺序栈 栈的顺序存储结构简称为顺序栈 即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 同时附设栈顶指针top和栈底指针base 可用数组来实现顺序栈 指针base始终指向栈底的位置 若base NULL 则表明栈结构不存在 指针top的初值指向栈底 当top base时为空栈 约定非空栈中的栈顶指针始终指向栈顶元素的下一个位置上 每当插入新的栈顶元素时 指针top加1 删除栈顶元素时 指针top减1 13 14 3 1 2栈的存储结构和实现 顺序栈的类型定义 栈的顺序存储表示 defineSTACK INIT SIZE100 defineSTACKINCREMENT10typedefstruct SElemType base 栈底指针 栈构造前和销毁后为空SElemType top 栈顶指针 指向栈顶元素的下一位置intstacksize 当前已分配的存储空间 以元素为单位 SqStack 15 顺序栈设S是SqStack类型的变量 base是栈底指针 top是栈顶指针 栈不存在条件S base NULL 栈空条件S top S base 插入栈顶元素 栈顶指针S top S top 1 删除栈顶元素 栈顶指针S top S top 1 栈满条件S top S base S stacksize 3 1 2栈的存储结构和实现 16 进栈 入栈示例 17 出栈 退栈示例 18 3 1 2栈的存储结构和实现 顺序栈的C语言实现 1 初始化StatusInitStack SqStack InitStack 19 2 判断栈空intStackEmpty SqStackS return S base S top 3 判断栈满intStackFull SqStackS return S top S base S stacksize 3 1 2栈的存储结构和实现 20 4 取栈顶元素StatusGetTop SqStackS SElemType 21 3 1 2栈的存储结构和实现 5 元素入栈StatusPush SqStack 22 6 出栈操作StatusPop SqStack 注意 取栈顶元素与出栈不同之处在于出栈操作改变栈顶指针top的位置 而取栈顶元素操作不改变栈的栈顶指针 23 3 1 2栈的存储结构和实现 链栈 栈的链式存储结构称为链栈 它是运算是受限的单链表 插入和删除操作仅限制在表头位置上进行 由于只能在链表头部进行操作 故链表没有必要像单链表那样附加头结点 栈顶指针就是链表的头指针 链栈的类型说明如下 typedefstructstacknode SElemTypedata structstacknode next stacknode LinkStack 24 3 1 2栈的存储结构和实现 链栈 栈 思考 链栈是否需要另外设置头指针 建立链栈适合用哪种插入法 链栈的基本操作的实现 栈空条件 S NULL栈满条件 无 25 1 进栈操作 StatusPush L LinkStack 2 出栈操作StatusPop L LinkStack 26 3 2栈的应用举例 根据栈的FILO特性 用作某些处理问题的工具 1 数制转换例 43 10 101011 2 输出 27 voidconversion InitStack S 构造空栈scanf d 3 2栈的应用举例 28 2 括号匹配设一个表达式中可以包含三种括号 和 和 和 并且这三种括号可以按照任意的次序嵌套使用 考查表达式中的括号是否匹配 例如 例 a b c d e f while m a 8 t m m 1 t t 1 实现方法 利用栈进行表达式中的括号匹配自左至右扫描表达式 若遇左括号 则将左括号入栈 若遇右括号 则将其与栈顶的左括号进行匹配 若配对 则栈顶的左括号出栈 否则出现括号不匹配错误 3 2栈的应用举例 29 3 迷宫问题寻找一条从入口到出口的通路 在求解时 通常用的是 穷举求解 的方法 即从入口出发 顺某一方向向前试探 若能走通 则继续往前走 否则沿原路退回 换一个方向再继续试探 直至所有可能的通路都试探完为止 为了保证在任何位置上都能沿原路退回 称为回溯 需要用一个后进先出的栈来保存从入口到当前位置的路径 3 2栈的应用举例 30 对于迷宫中的每个方块 有上下左右四个方块相邻 第i行第j列的当前方块的位置为 i j 规定右边方块为方位0 顺时针方向递增编号 在试探过程中 假设从方位0到方位3的方向查找下一个可走的方块 即先从向右开始 按照顺时针方向搜索下一步可能前进的位置 3 2栈的应用举例 i j 31 3 迷宫问题 1 1 3 2栈的应用举例 32 3 迷宫问题 33 首先用如图3 3所示的方块图表示迷宫 对于图中的每个方块 用空白表示通道 用阴影表示墙 所求路径必须是简单路径 即在求得的路径上不能重复出现同一通道块 34 为了表示迷宫 设置一个数组mg 其中每个元素表示一个方块的状态 为0时表示对应方块是通道 为1时表示对应方块为墙 如图3 3所示的迷宫 对应的迷宫数组mg如下 3 2栈的应用举例 intmg M N M 10 N 10 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 35 为了便于回溯 对于可走的方块都要进栈 并试探它的下一可走的方位 将这个可走的方位保存到栈中 为此 将栈中元素定义为 struct inti 当前方块的行号 intj 当前方块的列号 intdi di是下一可走相邻方位的方位号 st MaxSize 定义栈 inttop 1 初始化栈指针 36 求解迷宫 1 1 到 M 2 N 2 路径的过程是 先将入口进栈 初始方位设置为 1 在栈不空时循环 取栈顶方块 不退栈 若该方块是出口 则输出栈中方块即为路径 否则 找下一个可走的相邻方块 若不存在这样的方块 则退栈 若存在这样的方块 则将其方位保存到栈顶元素中 并将这个可走的相邻方块进栈 初始方位设置为 1 为了保证试探的可走相邻方块不是已走路径上的方块 如 i j 已进栈 在试探 i 1 j 的下一可走方块时 又试探到 i j 这样可能会引起死循环 为此 在一个方块进栈后 将对应的mg数组元素值改为 1 变为不可走的相邻方块 当退栈时 表示没有可走相邻方块 将其恢复为0 37 38 voidmgpath 路径为 1 1 M 2 N 2 inti j di find k top 初始方块进栈Stack top i 1 Stack top j 1 Stack top di 1 mg 1 1 1 while top 1 栈不空时循环 i Stack top i j Stack top j di Stack top di 读栈顶元素if i M 2 39 find 0 未找到通道while di 4 40 if find 1 找到了下一个可走方块 Stack top di di 修改原栈顶元素的di值top 下一个可走方块进栈Stack top i i Stack top j j Stack top di 1 mg i j 1 避免重复走到该方块 else 没有路径可走 则退栈 top 出栈mg Stack top i Stack top j 0 让该位置变为其他路径可走方块 printf 没有可走路径 n 41 4 表达式求值 算符优先法4 2 3 10 5 先乘除 后加减 从左算到右 先括号内 后括号外 4 2 3 10 5 4 6 10 5 10 10 5 10 2 8 表达式由操作数 operand 运算符 operator 和界限符 delimiter 组成的 其中操作数可以是常数 也可以是变量或常量的标识符 运算符可以是算术运算符 关系运算符和逻辑运算符 界限符为左右括号和标识表达式结束的结束符 将运算符和界限符统称为算符 它们构成的集合命名为OP 3 2栈的应用举例 42 四则运算法则实际上可以理解为任意两个相继出现的算符c1和c2之间的优先关系 优先关系至多是下列三种关系之一 1 2 1的优先权大于 2 用上述求表达式值的方法称为 算符优先法 下表给出了 和 的算术运算符间的优先级关系 算符间的优先关系 当前待比较的字符 运算符栈栈顶字符 算符优先算法 用两个工作栈 一个称作OPTR 用于存放运算符 另一个称作OPND 用以存放操作数或运算结果 首先置操作数栈为空栈 表达式起始符 为运算符的栈底元素 依次读入表达式中每个字符 若是操作数则进OPND栈 若是运算符 则和OPTR栈的栈顶运算符比较优先权后作相应操作 直到整个表达式求值完毕 OPTR栈的栈顶元素和当前读入的字符均为 45 OperandTypeEvaluateExpression InitStack OPTR Push OPTR InitStack OPND c getchar while c GetTop OPTR if In c OP Push OPND c c getchar else 不是运算符则进栈switch Precede GetTop OPTR c case 栈顶元素优先权低Push OPTR c c getchar break case 脱括号并接收下一字符Pop OPTR x c getchar break 3 2栈的应用举例 46 case 退栈并将运算结果入栈Pop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b break switch whilereturnGetTop OPND EvaluateExpression 3 2栈的应用举例 47