数据结构与算法栈与队列教学设计

1、数据结构与算法“栈与队列”教学设计北京大学信息科学技术学院赵海燕1. 栈与队列在课程中的定位和前测知识点栈和队列作为两种重要的线性结构， 在计算机科学中具有非常广泛的应用， 从简单的表达式计算到编译器对程序语法的检查， 再到操作系统对各种设备的管理等等都有它们的用武之地。从逻辑角度来说，栈和队列都是典型的线性结构。但与线性表不同的是，栈和队列上的操作比较特殊， 受到一定的限制， 仅允许在线性表的一端或两端进行， 因而栈和队列常被称为操作受限的线性表，或者限制存取点的线性表。栈与队列一章主要介绍栈与队列的基本概念及其相应的存储实现， 并重点介绍了栈的应用，以表达式转换和求值为例来说明。栈与递归之

2、间关系是本章的重点，也是难点，递归算法到非递归算法的机械转换是本章的选讲内容。 队列的顺序实现中的一些相关考虑也是本章的一个重点，由此可揭示数据结构设计的一些准则。作为基础的数据结构， 栈与队列在本课程后续的章节中多有用到，构的周游，因而本章在数据结构与算法课程中占有例如， 树结构和图结前测知识点要求如下，可以视情况给学生补充：（ 1） 概率的基本概念和计算；（ 2） 排列、组合的概念和计算；（ 3） 动态存储分配的概念。2学习目标（ 1） 理解栈和队列的基本概念；（ 2） 熟练掌握栈和队列上的常用运算；（ 3） 理解和掌握如何使用栈解决实际问题；（ 4） 理解函数调用和递归调用的本质，了解栈

3、与递归的关系；（ 5） 了解递归算法到非递归算法的转换机理和方法；（ 6） 掌握如何使用队列解决实际问题。3. 知识点和学时分配理论授课 4-5 学时，建议安排实验6 学时。以下内容是本课程要求的基本教学内容，在授课中必须完全涵盖，各知识点建议授课时间如下：栈的抽象数据类型10 分钟顺序栈和链式栈50 分钟表达式求值60 分钟栈与递归60 分钟队列的抽象数据类型10 分钟顺序队列30 分钟链式队列20 分钟此外，可视学生的状况和程度，选择补充讲授递归到非递归的转换60 分钟4重点和难点本章重点包括：（ 1） 栈的运算及其顺序实现；（ 2） 中缀表达式到后缀表达式的转换；（ 3） 后缀表达式的求

4、值；（ 4） 栈与递归；（ 5） 队列运算及其顺序实现。其中，难点在于（ 1） 中缀表达式到后缀表达式的转换；（ 2） 运行栈在递归调用中的作用；（ 3） 递归到非递归的转换。5授课提示应该结合计算机科学技术的现代前沿研究课题，设计研究启发式教学案例，扩展学生知识体系，培养主动学习、研究和创新意识。下面是栈与队列一章的重点和难点内容的讲授注意事项。（ 1）栈的运算及其顺序实现栈是一种限定仅在一端进行插入和删除的线性表，无论是往栈中插入元素还是删除栈中的元素、 抑或读取栈中的元素，都只能固定在线性表的一端进行。通常栈的这一端被称为栈顶，与此相对，栈的另一端则叫做栈底。栈具有后进先出的特性，适合于

5、所有具有后进先出特性的应用。栈可以采用顺序的存储实现也可以采用链式存储方式，但鉴于链式方式的结构开销，用的栈还是顺序栈。在讲授顺序栈时， 应该强调为充分利用栈空间的目标设置栈顶位置时的考虑，以向学生解传授数据结构设计的细微之道。常（ 2）表达式求值表达式求值是程序设计语言编译器中的一个最基本的问题。表达式是由常量、变量、 运算符、函数调用等按一定规则组合而成的。常用的程序设计语言中大多提供人们熟悉的中缀表达式， 而计算机对表达式进行求值则是通过机器指令来完成，故需要在计算过程中先把中缀表达式转换成易于形成机器指令的后缀表达式，再对后缀表达式进行求值。授课时需强调中缀表达式和后缀表达式的操作数和

6、运算符在形式和计算次序上异同点，最好辅以实例来说明，便于学生加深理解。（ 3）中缀表达式到后缀表达式的转换中缀表达式的运算次序受到运算符优先级和括号的影响。因此，中缀表达式转换成等价的后缀表达式的关键在于如何恰当地去掉中缀表达式中的括号， 再在必要时按先乘除后加减的优先规则调换运算符的先后次序。在去括号的过程中使用栈来存储有关的元素。授课时需强调中缀表达式和后缀表达式的操作数和运算符在形式和计算次序上异同点，最好辅以实例来说明，便于学生加深理解。（ 4）栈与递归由于符合人类自顶向下抽象描述问题的思维方式， 递归成为数学和计算机科学的基本概念，是解决复杂问题的一个有力手段。许多程序设计语言都提供

7、对递归的支持，而大多数程序设计语言运行环境所提供的函数调用机制，包括递归调用，都是由底层的运行栈支持的。编译栈中的“运行时环境”指的是目标计算机上用来管理存储器并保存执行过程所需信息的寄存器及存储器的结构。模拟运行栈的工作机理，可以设计把一个递归算法转换成非递归算法的机械过程。授课时如果需要可以适当补充与动态存储分配和编译栈相关的内容。建议在讲授函数调用的机制和递归的机制，以及递归到非递归的转换时采用动画演示运行栈中的状态变化为宜。（ 5）队列及其实现作为一种应用广泛的数据结构，队列也是一种限制访问点的线性表。队列的元素只能从表的一端插入， 另一端删除。 通常把只允许删除的一端称为队头，把删除

8、操作本身称为出队；而称表的另一端为队尾，这一端只能进行插入操作，把插入操作称为入队。队列具有先进先出的特性。 只要符合先进先出特性的应用均可运用队列，常见的应用有广度优先搜索、消息缓冲器、操作系统的各种资源管理等。队列的存储结构和实现方法主要分为顺序和链式两种。顺序队列是较为普遍的一种队列实现方式， 一般采用环状顺序表来存放队列元素，并用两个变量分别指向队列的头和尾，往队列中加入元素或从队列中取出元素时分别改变队列头和尾这两个变量的计数。链式队列一般用单链表方式存储队列，其中链接指针的方向是从队列的前端向尾端链接。授课时需引导学生思考为何顺序队列采用环状，采用之后在实现上有何要求等等，以帮助学

9、生理解和掌握数据结构设计的精髓。6课后练习和实习作为教学的重要一环，课后练习和上机实习帮助学生巩固课堂所学理论知识，训练学生创新思维能力训练、工程实践能力。栈与队列部分可以安排56 道书面作业，也可酌情采用ACM/ICPC程序竞赛题库POJ系统安排 1-2 道的实习题。7教学案例选取中缀表达式到后缀表达式的转换为例。中缀表达式的运算次序受到运算符优先级和括号的影响， 而没有括号的后缀表达式的运算次序与运算符出现的顺序相同。 因此，中缀表达式转换成等价的后缀表达式的关键在于如何恰当地去掉中缀表达式中的括号， 再在必要时按先乘除后加减的优先规则调换运算符的先后次序。在去括号的过程中使用栈来存储有关

10、的元素。实现这个转换的基本思路如下： 从左至右顺序扫描中缀表达式， 用栈来存放表达式中的操作数、开括号、以及在这个开括号后面的其他暂时不能确定计算次序的东西。(1) 当输入的是操作数时，直接输出到后缀表达式序列中；(2) 当遇到开括号时，将其入栈；(3) 当输入遇到闭括号时，先判断栈是否为空，若为空，则表示括号不匹配，应作为错误异常处理， 清栈退出。 若非空，则把栈中元素依次弹出， 直到遇到第一个开括号为止，将弹出的元素输出到后缀表达式序列中， 由于后缀表达式不需要括号， 弹出的开括号不放到输出序列中，若没有遇到开括号，说明括号不配对，做异常处理，清栈退出。(4)当输入为运算符（四则运算+ -

11、 * /之一）时a) 循环，当（栈非空 & 栈顶不是开括号 & 栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作将栈顶元素弹出，放到后缀表达式序列中；b) 将输入的运算符压入栈内；(5) 最后，当中缀表达式的符号全部扫描完毕时， 若栈内仍有元素， 则将其全部依次弹出，放在后缀表达式序列的尾部。 若在弹出的元素中遇到开括号， 则说明括号不匹配， 做异常处理，清栈退出。这样，通过对中缀表达式进行一次扫描就可将其转换成等价的后缀表达式。下图是迎合转换的示例， 如何把中缀表达式23 +34 *45 /（ 5+6+7）转化为等价的后缀表达式23 34 45 * 56 + 7 + / + ，以及

12、转换过程中栈的状态变化。授课时最好辅以动画演示为好。步骤待处理的中缀表达式栈的状态输出的后缀表达式（左 - 右）（底 - 顶）123 + 34 * 45 / ( 5 + 6 7)232+ 34 * 45 / ( 5 + 6 7)+334 * 45 / ( 5 + 6 7)+23344* 45 / ( 5 + 6 7)+ *545 / ( 5 + 6 7)+ *23 34 456/ ( 5 + 6 7)+ /23 34 45 *7( 5 + 6 7)+ / (85 + 6 7)+ / (23 34 45 * 59+ 6 7)+ / ( +106 7)+ / ( +2334 45 * 5 611

13、7)+ / ( +2334 45 * 5 6 +127)+/ ( +2334 45 * 5 6 + 713)+ / ( +23 34 45 * 5 6 + 714+ /23 34 45 * 5 6 + 7 +1523 34 45 * 5 6+ 7 + / +8总结栈与队列是非常重要的数据结构， 在实际中具有广泛的应用， 也是数据结构与算法课程中最有趣味的部分。 本课程后续章节所涉及的非线性结构上的周游等运算均用到栈和队列的知识。除了要求学生掌握栈和队列的基本运算，递归的本质， 栈与递归的内在关系，栈和队列的应用场景之外， 还需提醒学生应根据实际应用的特点、 规模等， 选择栈或队列的合适的实现方式。参考文献：1. 张铭，王腾蛟，赵海燕， 数据结构与算法 ，高等教育出版社， 2