第三章栈和队列

第三章栈和队列 2 教学目标掌握栈和队列的基本概念 ADT描述方法 掌握栈的顺序存储结构和链式存储结构的基本操作及其实现算法 掌握循环队列和链队列的基本操作实现算法 学会运用栈和队列解决实际问题 3 1栈3 2栈的应用举例3 4队列 3 栈和队列是两种常用的数据类型 栈和队列也是两种特殊的线性表 它们是运算时要受到某些限制的线性表 故也称为限定性的数据结构 通常称 栈和队列是限定插入和删除只能在表的 端点 进行的线性表 4 如果所有的操作均被限定在线性表的一端 那么就称该线性表为栈 Stack 如果线性表的一端仅允许插入元素 而另一端仅允许删除元素 那么该线性表被称为队列 Queue 栈和队列是两种在计算机程序设计中广泛运用的线性表 5 一 栈的概念 3 1栈的概念 3 1栈 1 栈的定义 栈 限定只能在表的一端进行插入和删除的特殊的线性表设栈s a1 a2 ai an 其中a1是栈底元素 an是栈顶元素 出栈 栈顶 top 允许插入和删除的一端 约定top始终指向新数据元素将存放的位置 栈底 bottom 不允许插入和删除的一端 插入 即进栈 在n 1位置插入 删除 即出栈 删除第n位置元素 栈的特点后进先出 6 2 栈的类型定义 抽象数据类型栈的定义如下 P44 3 1栈的概念 7 3 1栈的表示和实现 二 栈的表示和实现 1 顺序存储和实现 顺序栈 用一组连续的存储单元存放自栈底到栈顶的数据元素 一般用一维数组表示 设置一个简单变量top指示栈顶位置 称为栈顶指针top 约定栈顶指针指向栈顶元素的下一个位置 8 进栈 A 出栈 B C D E F 栈满 栈空 栈顶指针top 指向实际栈顶后的空位置 初值为0 当栈满时再做进栈运算必定产生空间溢出 简称 上溢 overflow 当栈空时再做退栈运算也将产生溢出 简称 下溢 underflow 3 1栈的表示实现 9 上溢是一种出错状态 应该设法避免之 下溢则可能是正常现象 因为栈在程序中使用时 其初态或终态都是空栈 所以下溢常常用来作为程序控制转移的条件 顺序栈的操作算法 顺序栈的类型定义 栈的顺序存储表示 defineSTACK NINT SIZE100 存储空间初始分配量 defineSTACKINCREMENT10 存储空间分配增量typedefstruct SElemType base 在栈构造之前和销毁之后 bade的值为NULLSElemType top 栈顶指针intstacksize 当前已分配的存储空间 以元素为单位 SqStack 10 11 3 1栈的表示和实现 2 判断栈是否为满 3 判断栈是否为空 12 3 1栈的表示和实现 4 取栈顶元素 13 3 1栈的表示和实现 5 进 压 栈push StatusPush SqStack push 分析演示 14 3 1栈的表示和实现 statusPop SqStack Pop 6 出栈pop 分析演示 15 例1 如书中P44页图3 1 b 所示铁道车厢调度 1 如果进站的车厢序列为123 则可能得到的出站车厢序列是什么 2 如果进站的车厢序列为123456 则能否得到435612和135426的出站序列 16 例2 如下列算法 执行完后能输出什么结果 Voidmain stacks charx y initstack s x c y k push s x push s a push s y pop s x push s t push s x pop s x push s s while Stackempty s pop s y printf y printf x c a y 由上算法分析 设定了栈S 栈S的元素类型为char push为进栈 pop为出栈 栈S t c s x k 17 例3 栈S中存放了已知数组a 2 4 6 8 10 中的元素 写一算法将数组中的值逆置 即 a 1 的值2与a 5 的值10互换 如下图 Statusalgo1 stacks inti n a 5 n 0 While stackempty s n pop s a n for i 1 i 5 i push s a i 18 2 链式存储和实现 3 1栈的表示和实现 链栈 即栈的链式存储结构 与线性链表类似 如图所示 注意 链栈中指针的方向 19 3 1栈的表示和实现 链栈的操作算法 链栈的类型定义 typedefstructLNode 结点类型ElemTypedata structLNode next Lnode Linkstack LinkstackS StatusInitLStack Linkstack InitLStack 1 建立一个空栈 20 StatusGettopLStack Linkstack GettopLStack 2 取栈顶元素 3 1栈的表示和实现 21 StatusPushLStack Linkstack PushLStack 3 进 压 栈push 22 3 1栈的表示和实现 StatusPopLStack Linkstack PopLStack 4 出栈push 23 3 1栈的表示和实现 例4 在栈顶指针为HS的链栈中 写出计算该链栈中结点个数的函数 Intcount LinkListHS LinkListp intn 0 p HS While P n p p next return n 24 例若进栈序列为3 5 7 9 进栈过程中可以出栈 则不可能的一个出栈次序是 7 5 3 9 b 9 7 5 3 c 7 5 9 3 d 9 5 7 3 例用一维数组设计栈 初态是栈空 top 0 现有输入序列是a b c d 经过push push pop push pop push操作后 输出序列是 栈顶指针是 b c 2 d 25 小结1栈是限定仅能在表尾一端进行插入 删除操作的线性表 2栈的元素具有后进先出的特点 3栈顶元素的位置由一个称为栈顶指针的变量指示 进栈 出栈操作要修改栈顶指针 26 3 2栈的应用举例 例1数制转换对于输入的任意一个非负十进制数 显示输出与其等值的八进制数 3 2栈的应用 例把十进制数159转换成八进制数 27 3 2栈的应用 voidconversion InitStack s 建空栈scanf d 28 3 2栈的应用 例2括号匹配的检验 假设在表达式中 或 等为正确的格式 或 或 均为不正确的格式 则检验括号是否匹配的方法 可用 期待的急迫程度 这个概念来描述 例如 考虑下列括号序列 12345678 分析可能出现的不匹配的情况 到来的右括弧并非是所 期待 的 到来的是 不速之客 直到结束 也没有到来所 期待 的括弧 29 3 2栈的应用 算法的设计思想 1 凡出现左括弧 则进栈 2 凡出现右括弧 首先检查栈是否空若栈空 则表明该 右括弧 多余 否则和栈顶元素比较 若相匹配 则 左括弧出栈 否则表明不匹配 3 表达式检验结束时 若栈空 则表明表达式中匹配正确 否则表明 左括弧 有余 30 3 2栈的应用 Statusmatching string 31 例3行编辑程序问题 在用户输入一行的过程中 允许用户输入出差错 并在发现有误时可以及时更正 合理的作法是 设立一个输入缓冲区 用以接受用户输入的一行字符 然后逐行存入用户数据区 并假设 为退格符 为退行符 假设从终端接受了这样两行字符 whli ilr e s s outcha putchar s 则实际有效的是下列两行 while s putchar s 3 2栈的应用 32 while ch EOF 从终端接收下一个字符 ClearStack S 重置S为空栈if ch EOF ch getchar while ch EOF EOF为全文结束符 将从栈底到栈顶的字符传送至调用过程的数据区 3 2栈的应用 33 例4表达式求值 表达式的构成操作数 运算符 界符 如括号 表达式的求值 按照四则运算法则 例5 6 1 2 4计算过程为 5 6 1 2 4 5 6 3 4 5 18 4 23 4 19 1 2 3 4 3 2栈的应用 表达式求值是程序设计语言编译中的一个最基本问题 它的实现需要借助栈来完成 介绍一种简单直观 广为使用的算法 即 算符优先法 34 表达式中任何相邻运算符c1 c2的优先关系有 c1c2 c1的优先级高于c2 注 c1c2是相邻算符 c1在左 c2在右 算符间的优先关系表 3 2栈的应用 35 基本思想 实现算符优先算法 可以使用两个工作栈 一个称为OPTR 用以寄存运算符 另一个称为OPND 用以寄存操作数或运算结果 1 首先置操作数栈为空栈 表达式起始符 为运算符的栈底元素 2 依次读入表达式中每个字符 若是操作数则进OPND栈 若是运算符 则和OPTR栈的栈顶运算符比较 高进栈 否则低于或相同则作相应操作 直至整个表达式求值完毕 即OPTR栈的栈顶元素和当前读入的字符均为 例 S 4 2 3 10 5 36 如下所示 操作过程 例如 利用算符优先算法对算术表达式3 7 2 求值 37 OperandTypeEvaluateExpression 算术表达式求值设OPTR和OPND分别为运算符栈和运算数栈 InitStack OPET Push OPTR initStack OPND c getchar while c GetTop OPTR if In c OP Push OPND c c getchar 不是运算符则进栈elseswitch Precede GetTop OPTR c case 栈顶元素优先权低Push OPTR c c getch break 算法描述P53 38 case 脱括号并接收下一个字符Pop OPTR x c getch break case 退栈并将运算结果入栈Pop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b break swith whilereturnGetTop OPND EvaluateExpression 例 地图四染色问题 四染色 定理是计算机科学中著名的定理之一 使地图中相邻的国家或行政区域不重色 最少可用四种颜色对地图着色 证明此定理的结论 利用栈采用回溯法对地图着色 思想 对每个行政区编号 1 7 对颜色编号 a b c d 从第一号行政区开始逐一染色 每一个区域逐次用四种颜色进行试探 若所取颜色与周围不重 则用栈记下来该区域的色数 否则依次用下一色数进行试探 若出现a d均与周围发生重色 则需退栈回溯 修改当前栈顶的色数 40 1 2 4 5 6 7 3 1 粉色2 黄色3 红色4 绿色 41 例 迷宫求解 通常用的是 穷举求解 的方法 42 求迷宫路径算法的基本思想是 若当前位置 可通 则纳入路径 继续前进 若当前位置 不可通 则后退 换方向继续探索 若四周 均无通路 则将当前位置从路径中删除出去 43 设定当前位置的初值为入口位置 do 若当前位置可通 则 将当前位置插入栈顶 若该位置是出口位置 则算法结束 否则切换当前位置的东邻方块为新的当前位置 否则 while 栈不空 求迷宫中一条从入口到出口的路径的算法 44 若栈不空且栈顶位置尚有其他方向未被探索 则设定新的当前位置为 沿顺时针方向旋转找到的栈顶位置的下一相邻块 若栈不空但栈顶位置的四周均不可通 则 删去栈顶位置 从路径中删去该通道块若栈不空 则重新测试新的栈顶位置 直至找到一个可通的相邻块或出栈至栈空 若栈空 则表明迷宫没有通路 45 3 4队列一 队列的概念二 队列的顺序存储和实现三 队列的链式存储和实现 46 一 队列的概念定义 队列是限定只能在表的一端进行插入 在表的另一端进行删除的线性表队尾 rear 允许插入的一端队头 front 允许删除的一端队列特点 先进先出 FIFO 双端队列 47 a1a2a3an 入队列 队头 队尾 出队列 队列的示意图 队列的特点先进先出 第一个入队的元素在队头最后一个入队的元素在队尾第一个出队的元素为队头元素最后一个出队的元素为队尾元素 48 队列的类型定义 ADTQueue 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 约定其中a1端为队列头 an端为队列尾 基本操作 P59 ADTQueue 队列的主要运算 1 设置一个空队列 2 插入一个新的队尾元素 称为进队 3 删除队头元素 称为出队 4 读取队头元素 49 二 队列的顺序存储和实现 J1 J2 J3 设两个指针front rear 约定 Rear始终指向队尾元素的下一个位置 front始终指向队头元素 空队列条件 front rear入队列 sq rear x 出队列 x sq front 50 存在问题设数组维数为M 则 当front 1 rear M 1时 再有元素入队发生溢出 真溢出当front 1 rear M 1时 再有元素入队发生溢出 假溢出解决方案 循环队列 51 2 循环队列基本思想 把队列设想成环形 让sq 0 接在sq M 1 之后 若rear 1 M 则令rear 0 实现 利用 模 运算入队 rear rear 1 M sq rear x 出队 front front 1 M x sq front 队满 队空判定条件 52 队空 front rear队满 front rear 解决方案 1 另外设一个标志以区别队空 队满2 少用一个元素空间 队空 front rear队满 rear 1 M front 53 循环队列类型定义 defineMAXQSIZE100 最大队列长度typedefstruct QElemType base 动态分配存储空间intfront 头指针 若队列不空 指向队列头元素intrear 尾指针 若队列不空 指向 队列尾元素的下一个位置 SqQueue 54 循环队列的主要运算 1 初始化操作功能 建一个空队列Q StatusInitQueue SqQueue 55 2 入队操作功能 将元素x插入队尾 算法 StatusEnQueue SqQueue 动画演示 56 3 出队操作功能 删除队头元素 StatusDeQueue SqQueue 动画演示 57 三 队列的链式存储和实现 front rear 空链队列 链队列图示 1 链队列 58 2 链队列的类型定义结点类型 typedefstructQNode QElemTypedata structQNode next QNode QueuePtr 链队列类型 typedefstruct QueuePtrfront 队头指针QueuePtrrear 队尾指针 LinkQueue 59 链队列的主要运算 1 初始化操作功能 建一个空队列Q StatusInitQueue LinkQueue 60 2 入队操作功能 将元素x插入队尾 p data e p next NULL Q rear next p Q rear p 61 算法 StatusEnQueue LinkQueue 62 3 出队操作功能 删除队头元素 p Q front next e p data Q front next p next 63 算法 StatusDeQueue LinkQueue 64 小结1队列是限定仅能在表尾一端进行插入 表头一端删除操作的线性表 2队列中的元素具有先进先出的特点 3队头 队尾元素的位置分别由称为队头指针和队尾指针的变量指示 4入队操作要修改队尾指针 出队操作要修改队头指针 65 例 循环队列SQ采用数组空间SQ base 0 n 1 存放其元素值 已知其头尾指针分别是front和rear 则判定此循环队列Q为空的条件是 A Q rear Q front nB Q rear Q front 1 nC Q rear Q frontD Q rear Q front 1 C 例 循环队列SQ采用数组空间SQ base 0 n 1 存放其元素值 已知其头尾指针分别是front和rear 则判定此循环队列Q为满的条件是 A Q rea Q frontB Q front Q rearC Q front Q rear 1 nD Q front Q rear 1 n C 66 例 循环队列用数组A 0 m 1 存放其元素值 已知其头尾指针分别是front和rear则当前队列中的元素个数是 A rear front m m B rear front 1 C rear front 1 D rear front B 例 栈和队列的共同点是 A 都是先进后出 B 都是先进先出 C 只允许在端点处插入和删除元素 D 没有共同点 C 67 例 以数组Q 0 m 1 存放循环队列中的元素 变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数 队列第一个元素的实际位置是 A rear qulen B rear qulen m C m qulen D 1 rear m qulen m D 68 例 若在一个大小为6的数组上实现循环队列 且当前rear和front的值分别为0和3 当从队列中删除一个元素 再加入两个元素后 rear和front的值分别是 例 判定一个链队列Q 最多元素个数为N 为空的条件是 A Q front Q rearB Q front Q rearC Q