数据结构与算法“栈与队列”教学设计 北京大学信息科学技术学院赵海燕 1.栈与队列在课程中的定位和前测知识点 栈和队列作为两种重要的线性结构,在计算机科学中具有非常广泛的应用,从简单的表 达式计算到编译器对程序语法的检査,再到操作系统对各种设备的管理等等都有它们的用武 之地。从逻辑角度来说,栈和队列都是典型的线性结构。但与线性表不同的是,栈和队列上 的操作比较特殊,受到一定的限制,仅允许在线性表的一端或两端进行,因而栈和队列常被 称为操作受限的线性表,或者限制存取点的线性表 栈与队列一章主要介绍栈与队列的基本概念及其相应的存储实现,并重点介绍了栈的应 用,以表达式转换和求值为例来说明。栈与递归之间关系是本章的重点,也是难点,递归算 法到非递归算法的机械转换是本章的选讲内容。队列的顺序实现中的一些相关考虑也是本章 的一个重点,由此可揭示数据结构设计的一些准则 作为基础的数据结构,栈与队列在本课程后续的章节中多有用到,例如,树结构和图结 构的周游,因而本章在数据结构与算法课程中占有 前测知识点要求如下,可以视情况给学生补充: (1)概率的基本概念和计算 (2)排列、组合的概念和计算 (3)动态存储分配的概念。 2.学习目标 (1)理解栈和队列的基本概念; (2)熟练掌握栈和队列上的常用运算 (3)理解和掌握如何使用栈解决实际问题 (4)理解函数调用和递归调用的本质,了解栈与递归的关系 (5)了解递归算法到非递归算法的转换机理和方法; (6)掌握如何使用队列解决实际问题。 3.知识点和学时分配 理论授课4-5学时,建议安排实验6学时。 以下内容是本课程要求的基本教学内容,在授课中必须完全涵盖,各知识点建议授课时 间如下 栈的抽象数据类型 0分钟 顺序栈和链式栈 50分钟 表达式求值 60分钟 栈与递归 60分钟 队列的抽象数据类型 10分钟 顺序队列 30分钟 链式队列 20分钟 此外,可视学生的状况和程度,选择补充讲授 递归到非递归的转换 60分钟
数据结构与算法“栈与队列”教学设计 北京大学信息科学技术学院 赵海燕 1. 栈与队列在课程中的定位和前测知识点 栈和队列作为两种重要的线性结构，在计算机科学中具有非常广泛的应用，从简单的表 达式计算到编译器对程序语法的检查，再到操作系统对各种设备的管理等等都有它们的用武 之地。从逻辑角度来说，栈和队列都是典型的线性结构。但与线性表不同的是，栈和队列上 的操作比较特殊，受到一定的限制，仅允许在线性表的一端或两端进行，因而栈和队列常被 称为操作受限的线性表，或者限制存取点的线性表。 栈与队列一章主要介绍栈与队列的基本概念及其相应的存储实现，并重点介绍了栈的应 用，以表达式转换和求值为例来说明。栈与递归之间关系是本章的重点，也是难点，递归算 法到非递归算法的机械转换是本章的选讲内容。队列的顺序实现中的一些相关考虑也是本章 的一个重点，由此可揭示数据结构设计的一些准则。 作为基础的数据结构，栈与队列在本课程后续的章节中多有用到，例如，树结构和图结 构的周游，因而本章在数据结构与算法课程中占有 前测知识点要求如下，可以视情况给学生补充： （1） 概率的基本概念和计算； （2） 排列、组合的概念和计算； （3） 动态存储分配的概念。 2．学习目标 （1） 理解栈和队列的基本概念； （2） 熟练掌握栈和队列上的常用运算； （3） 理解和掌握如何使用栈解决实际问题； （4） 理解函数调用和递归调用的本质，了解栈与递归的关系； （5） 了解递归算法到非递归算法的转换机理和方法； （6） 掌握如何使用队列解决实际问题。 3. 知识点和学时分配 理论授课 4-5 学时，建议安排实验 6 学时。 以下内容是本课程要求的基本教学内容，在授课中必须完全涵盖，各知识点建议授课时 间如下： 栈的抽象数据类型 10 分钟 顺序栈和链式栈 50 分钟 表达式求值 60 分钟 栈与递归 60 分钟 队列的抽象数据类型 10 分钟 顺序队列 30 分钟 链式队列 20 分钟 此外，可视学生的状况和程度，选择补充讲授 递归到非递归的转换 60 分钟
4.重点和难点 本章重点包括 (1)栈的运算及其顺序实现 (2)中缀表达式到后缀表达式的转换 (3)后缀表达式的求值 (4)栈与递归 (5)队列运算及其顺序实现 其中,难点在于 (1)中缀表达式到后缀表达式的转换 (2)运行栈在递归调用中的作用 (3)递归到非递归的转换 授课提示 应该结合计算机科学技术的现代前沿研究课题,设计研究启发式教学案例,扩展学生 知识体系,培养主动学习、研究和创新意识 下面是栈与队列一章的重点和难点内容的讲授注意事项。 (1)栈的运算及其顺序实现 栈是一种限定仅在一端进行插入和删除的线性表,无论是往栈中插入元素还是删除栈中 的元素、抑或读取栈中的元素,都只能固定在线性表的一端进行。通常栈的这一端被称为栈 顶,与此相对,栈的另一端则叫做栈底。栈具有后进先出的特性,适合于所有具有后进先出 特性的应用。 栈可以采用顺序的存储实现也可以采用链式存储方式,但鉴于链式方式的结构开销,常 用的栈还是顺序栈。在讲授顺序栈时,应该强调为充分利用栈空间的目标设置栈顶位置时的 考虑,以向学生解传授数据结构设计的细微之道 (2)表达式求值 表达式求值是程序设计语言编译器中的一个最基本的问题。表达式是由常量、变量、运 算符、函数调用等按一定规则组合而成的。常用的程序设计语言中大多提供人们熟悉的中缀 表达式,而计算机对表达式进行求值则是通过机器指令来完成,故需要在计算过程中先把中 缀表达式转换成易于形成机器指令的后缀表达式,再对后缀表达式进行求值。 授课时需强调中缀表达式和后缀表达式的操作数和运算符在形式和计算次序上异同点, 最好辅以实例来说明,便于学生加深理解。 (3)中级表达式到后缀表达式的转换 中缀表达式的运算次序受到运算符优先级和括号的影响。因此,中缀表达式转换成等价 的后缀表达式的关键在于如何恰当地去掉中缀表达式中的括号,再在必要时按先乘除后加减 的优先规则调换运算符的先后次序。在去括号的过程中使用栈来存储有关的元素。 授课时需强调中缀表达式和后缀表达式的操作数和运算符在形式和计算次序上异同点, 最好辅以实例来说明,便于学生加深理解 (4)栈与递归 由于符合人类自顶向下抽象描述问题的思维方式,递归成为数学和计算机科学的基本概 念,是解决复杂问题的一个有力手段 许多程序设计语言都提供对递归的支持,而大多数程序设计语言运行环境所提供的函数
4．重点和难点 本章重点包括： （1） 栈的运算及其顺序实现； （2） 中缀表达式到后缀表达式的转换； （3） 后缀表达式的求值； （4） 栈与递归； （5） 队列运算及其顺序实现。 其中，难点在于 （1） 中缀表达式到后缀表达式的转换； （2） 运行栈在递归调用中的作用； （3） 递归到非递归的转换。 5．授课提示 应该结合计算机科学技术的现代前沿研究课题，设计研究启发式教学案例，扩展学生 知识体系，培养主动学习、研究和创新意识。 下面是栈与队列一章的重点和难点内容的讲授注意事项。 （1）栈的运算及其顺序实现 栈是一种限定仅在一端进行插入和删除的线性表，无论是往栈中插入元素还是删除栈中 的元素、抑或读取栈中的元素，都只能固定在线性表的一端进行。通常栈的这一端被称为栈 顶，与此相对，栈的另一端则叫做栈底。栈具有后进先出的特性，适合于所有具有后进先出 特性的应用。 栈可以采用顺序的存储实现也可以采用链式存储方式，但鉴于链式方式的结构开销，常 用的栈还是顺序栈。在讲授顺序栈时，应该强调为充分利用栈空间的目标设置栈顶位置时的 考虑，以向学生解传授数据结构设计的细微之道。 （2）表达式求值 表达式求值是程序设计语言编译器中的一个最基本的问题。表达式是由常量、变量、运 算符、函数调用等按一定规则组合而成的。常用的程序设计语言中大多提供人们熟悉的中缀 表达式，而计算机对表达式进行求值则是通过机器指令来完成，故需要在计算过程中先把中 缀表达式转换成易于形成机器指令的后缀表达式，再对后缀表达式进行求值。 授课时需强调中缀表达式和后缀表达式的操作数和运算符在形式和计算次序上异同点， 最好辅以实例来说明，便于学生加深理解。 （3）中缀表达式到后缀表达式的转换 中缀表达式的运算次序受到运算符优先级和括号的影响。因此，中缀表达式转换成等价 的后缀表达式的关键在于如何恰当地去掉中缀表达式中的括号，再在必要时按先乘除后加减 的优先规则调换运算符的先后次序。在去括号的过程中使用栈来存储有关的元素。 授课时需强调中缀表达式和后缀表达式的操作数和运算符在形式和计算次序上异同点， 最好辅以实例来说明，便于学生加深理解。 （4）栈与递归 由于符合人类自顶向下抽象描述问题的思维方式，递归成为数学和计算机科学的基本概 念，是解决复杂问题的一个有力手段。 许多程序设计语言都提供对递归的支持，而大多数程序设计语言运行环境所提供的函数
调用机制,包括递归调用,都是由底层的运行栈支持的。编译栈中的“运行时环境”指的是 目标计算机上用来管理存储器并保存执行过程所需信息的寄存器及存储器的结构。模拟运行 栈的工作机理,可以设计把一个递归算法转换成非递归算法的机械过程。 授课时如果需要可以适当补充与动态存储分配和编译栈相关的内容。建议在讲授函数调 用的机制和递归的机制,以及递归到非递归的转换时采用动画演示运行栈中的状态变化为 (5)队列及其实现 作为一种应用广泛的数据结构,队列也是一种限制访问点的线性表。队列的元素只能从 表的一端插入,另一端删除。通常把只允许删除的一端称为队头,把删除操作本身称为出队 而称表的另一端为队尾,这一端只能进行插入操作,把插入操作称为入队。队列具有先进先 出的特性。只要符合先进先出特性的应用均可运用队列,常见的应用有广度优先搜索、消息 缓冲器、操作系统的各种资源管理等 队列的存储结构和实现方法主要分为顺序和链式两种。顺序队列是较为普遍的一种队列 实现方式,一般采用环状顺序表来存放队列元素,并用两个变量分别指向队列的头和尾,往 队列中加入元素或从队列中取出元素时分别改变队列头和尾这两个变量的计数。链式队列 般用单链表方式存储队列,其中链接指针的方向是从队列的前端向尾端链接。 授课时需引导学生思考为何顺序队列采用环状,采用之后在实现上有何要求等等,以帮 助学生理解和掌握数据结构设计的精髓。 6.课后练习和实习 作为教学的重要一环,课后练习和上机实习帮助学生巩固课堂所学理论知识,训练学生 创新思维能力训练、工程实践能力。 栈与队列部分可以安排5~6道书面作业,也可酌情采用 ACM/ICPC程序竞赛题库POJ 系统安排1-2道的实习题 7.教学案例 选取中缀表达式到后缀表达式的转换为例。 中缀表达式的运算次序受到运算符优先级和括号的影响,而没有括号的后缀表达式的运 算次序与运算符出现的顺序相同。因此,中缀表达式转换成等价的后缀表达式的关键在于如 何恰当地去掉中缀表达式中的括号,再在必要时按先乘除后加减的优先规则调换运算符的先 后次序。在去括号的过程中使用栈来存储有关的元素。 实现这个转换的基本思路如下:从左至右顺序扫描中缀表达式,用栈来存放表达式中的 操作数、开括号、以及在这个开括号后面的其他暂时不能确定计算次序的东西。 (1)当输入的是操作数时,直接输出到后缀表达式序列中 (2)当遇到开括号时,将其入栈 (3)当输入遇到闭括号时,先判断栈是否为空,若为空,则表示括号不匹配,应作为错误 异常处理,清栈退出。若非空,则把栈中元素依次弹出,直到遇到第一个开括号为止, 将弹出的元素输出到后缀表达式序列中,由于后缀表达式不需要括号,弹出的开括号 不放到输出序列中,若没有遇到开括号,说明括号不配对,做异常处理,清栈退出。 (4)当输入为运算符(四则运算+-*/之一)时 a)循环,当(栈非空&&栈顶不是开括号&&栈顶运算符的优先级不低于输 入的运算符的优先级)时,反复操作 将栈顶元素弹出,放到后缀表达式序列中
调用机制，包括递归调用，都是由底层的运行栈支持的。编译栈中的“运行时环境”指的是 目标计算机上用来管理存储器并保存执行过程所需信息的寄存器及存储器的结构。模拟运行 栈的工作机理，可以设计把一个递归算法转换成非递归算法的机械过程。 授课时如果需要可以适当补充与动态存储分配和编译栈相关的内容。建议在讲授函数调 用的机制和递归的机制，以及递归到非递归的转换时采用动画演示运行栈中的状态变化为 宜。 （5）队列及其实现 作为一种应用广泛的数据结构，队列也是一种限制访问点的线性表。队列的元素只能从 表的一端插入，另一端删除。通常把只允许删除的一端称为队头，把删除操作本身称为出队； 而称表的另一端为队尾，这一端只能进行插入操作，把插入操作称为入队。队列具有先进先 出的特性。只要符合先进先出特性的应用均可运用队列，常见的应用有广度优先搜索、消息 缓冲器、操作系统的各种资源管理等。 队列的存储结构和实现方法主要分为顺序和链式两种。顺序队列是较为普遍的一种队列 实现方式，一般采用环状顺序表来存放队列元素，并用两个变量分别指向队列的头和尾，往 队列中加入元素或从队列中取出元素时分别改变队列头和尾这两个变量的计数。链式队列一 般用单链表方式存储队列，其中链接指针的方向是从队列的前端向尾端链接。 授课时需引导学生思考为何顺序队列采用环状，采用之后在实现上有何要求等等，以帮 助学生理解和掌握数据结构设计的精髓。 6．课后练习和实习 作为教学的重要一环，课后练习和上机实习帮助学生巩固课堂所学理论知识，训练学生 创新思维能力训练、工程实践能力。 栈与队列部分可以安排 5~6 道书面作业，也可酌情采用 ACM/ICPC 程序竞赛题库 POJ 系统安排 1-2 道的实习题。 7．教学案例 选取中缀表达式到后缀表达式的转换为例。 中缀表达式的运算次序受到运算符优先级和括号的影响，而没有括号的后缀表达式的运 算次序与运算符出现的顺序相同。因此，中缀表达式转换成等价的后缀表达式的关键在于如 何恰当地去掉中缀表达式中的括号，再在必要时按先乘除后加减的优先规则调换运算符的先 后次序。在去括号的过程中使用栈来存储有关的元素。 实现这个转换的基本思路如下：从左至右顺序扫描中缀表达式，用栈来存放表达式中的 操作数、开括号、以及在这个开括号后面的其他暂时不能确定计算次序的东西。 (1) 当输入的是操作数时，直接输出到后缀表达式序列中； (2) 当遇到开括号时，将其入栈； (3) 当输入遇到闭括号时，先判断栈是否为空，若为空，则表示括号不匹配，应作为错误 异常处理，清栈退出。若非空，则把栈中元素依次弹出，直到遇到第一个开括号为止， 将弹出的元素输出到后缀表达式序列中，由于后缀表达式不需要括号，弹出的开括号 不放到输出序列中，若没有遇到开括号，说明括号不配对，做异常处理，清栈退出。 (4) 当输入为运算符（ 四则运算 + - * / 之一）时 a) 循环，当（栈非空 && 栈顶不是开括号 && 栈顶运算符的优先级不低于输 入的运算符的优先级）时，反复操作 将栈顶元素弹出，放到后缀表达式序列中；
b)将输入的运算符压入栈内 (5)最后,当中缀表达式的符号全部扫描完毕时,若栈内仍有元素,则将其全部依次弹出, 放在后缀表达式序列的尾部。若在弹出的元素中遇到开括号,则说明括号不匹配,做 异常处理,清栈退出。 这样,通过对中缀表达式进行一次扫描就可将其转换成等价的后缀表达式。下图是迎合 转换的示例,如何把中缀表达式23+34*45/(5+6+7)转化为等价的后缀表达式233445* 6+7+/+,以及转换过程中栈的状态变化。授课时最好辅以动画演示为好 待处理的中缀表达式 找的状态 输出的后级表达式 23+34·45/(5+6+刀 45/(5+6+7 233445 (5+6+7+ 233445 (5+6+7+( 5+6+刀 +6+7+/(+ 6+n 233445·56 0123 3445·56 )+/(+ 233445·56+7 233445·56+7+| 8.总结 栈与队列是非常重要的数据结构,在实际中具有广泛的应用,也是数据结构与算法课程 中最有趣味的部分。本课程后续章节所涉及的非线性结构上的周游等运算均用到栈和队列的 知识 除了要求学生掌握栈和队列的基本运算,递归的本质,栈与递归的内在关系,栈和队列 的应用场景之外,还需提醒学生应根据实际应用的特点、规模等,选择栈或队列的合适的实 现方式。 参考文献: 1.张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—一普 通高等教育“十一五”国家级规划教材。 2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pkueducn/pkujpk/course/sjjg
b) 将输入的运算符压入栈内； (5) 最后，当中缀表达式的符号全部扫描完毕时，若栈内仍有元素，则将其全部依次弹出， 放在后缀表达式序列的尾部。若在弹出的元素中遇到开括号，则说明括号不匹配，做 异常处理，清栈退出。 这样，通过对中缀表达式进行一次扫描就可将其转换成等价的后缀表达式。下图是迎合 转换的示例，如何把中缀表达式 23 +34 *45 /（5+6+7）转化为等价的后缀表达式23 34 45 * 5 6 + 7 + / + ，以及转换过程中栈的状态变化。授课时最好辅以动画演示为好。 14 + / 23 34 45 * 5 6 + 7 + 13 ) + / ( + 23 34 45 * 5 6 + 7 15 23 34 45 * 5 6+ 7 + / + 12 7) +/ ( + 23 34 45 * 5 6 + 7 9 + 6 ＋ 7) + / ( + 10 6 ＋ 7) + / ( + 23 34 45 * 5 6 11 ＋ 7) + / ( + 23 34 45 * 5 6 + 8 5 + 6 ＋ 7) + / ( 23 34 45 * 5 7 ( 5 + 6 ＋ 7) + / ( 6 / ( 5 + 6 ＋ 7) + / 23 34 45 * 5 45 / ( 5 + 6 ＋ 7) + * 23 34 45 4 * 45 / ( 5 + 6 ＋ 7) + * 3 34 * 45 / ( 5 + 6 ＋ 7) + 23 34 2 + 34 * 45 / ( 5 + 6 ＋ 7) + 1 23 + 34 * 45 / ( 5 + 6 ＋ 7) 23 栈的状态 输出的后缀表达式 （底-----顶） 待处理的中缀表达式 （左------右） 步骤 14 + / 23 34 45 * 5 6 + 7 + 13 ) + / ( + 23 34 45 * 5 6 + 7 15 23 34 45 * 5 6+ 7 + / + 12 7) +/ ( + 23 34 45 * 5 6 + 7 9 + 6 ＋ 7) + / ( + 10 6 ＋ 7) + / ( + 23 34 45 * 5 6 11 ＋ 7) + / ( + 23 34 45 * 5 6 + 8 5 + 6 ＋ 7) + / ( 23 34 45 * 5 7 ( 5 + 6 ＋ 7) + / ( 6 / ( 5 + 6 ＋ 7) + / 23 34 45 * 5 45 / ( 5 + 6 ＋ 7) + * 23 34 45 4 * 45 / ( 5 + 6 ＋ 7) + * 3 34 * 45 / ( 5 + 6 ＋ 7) + 23 34 2 + 34 * 45 / ( 5 + 6 ＋ 7) + 1 23 + 34 * 45 / ( 5 + 6 ＋ 7) 23 栈的状态 输出的后缀表达式 （底-----顶） 待处理的中缀表达式 （左------右） 步骤 8．总结 栈与队列是非常重要的数据结构，在实际中具有广泛的应用，也是数据结构与算法课程 中最有趣味的部分。本课程后续章节所涉及的非线性结构上的周游等运算均用到栈和队列的 知识。 除了要求学生掌握栈和队列的基本运算，递归的本质，栈与递归的内在关系，栈和队列 的应用场景之外，还需提醒学生应根据实际应用的特点、规模等，选择栈或队列的合适的实 现方式。 参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/