本教案由本书作者张光河撰写，若有任何问题可邮件到 guanghezhang@163.com
1
本教案仅用于张光河主编的书号为
978-7-115-48577-9 的数据结构教材。
本教案由本书作者张光河撰写，若有任何问题可邮件到 guanghezhang@163.com
2
数据结构
（Python 语言描述）
教 案
～ 学年 第 学期
教 学 单 位
课 程 名 称 数据结构
课 程 编 号
学 时 学 分
适 用 专 业 年 级
授 课 教 师
职 称 职 务
本教案由本书作者张光河撰写，若有任何问题可邮件到 guanghezhang@163.com
3
第 三 章 教 学 实 施 计 划
章节名称
第 3 章 栈、队列和递归
学 时
6
教学目的和教学要求（分了解、理解、掌握 三个层次）
了解：
特殊队列的基本概念、递归到非递归的转换。
理解：
递归算法执行过程中栈的状态变化过程。
掌握：
栈和队列的特点，并能在相应的应用问题中正确选用；
栈的顺序栈和链栈的进栈出栈算法，特别应注意栈满和栈空的条件；
循环队列和链队列的进队出队算法，特别是循环队列中队头与队尾指针的变化情况。
教学内容（包括基本内容、重点、难点）
基本内容：
栈的类型定义，栈的顺序存储和链接存储的表示和实现；
栈的应用（如迷宫求解和回文诗判断）；
队列的类型定义，队列的顺序存储(循环队)和链接存储的表示和实现；
队列的应用（如男女混合比赛分组问题）；
栈与递归的实现（汉诺塔问题）。
教学重点：
栈的顺序存储和链接存储的表示和实现；
队列的顺序存储(循环队)和链接存储的表示和实现。
教学难点：
栈的应用；
队列的应用。
上机实验和课后作业
本教案由本书作者张光河撰写，若有任何问题可邮件到 guanghezhang@163.com
4
上机实验：
完成 P154 基础实验 1 实现顺序栈的基本操作；
完成 P155 基础实验 2 实现链栈的基本操作；
完成 P155 基础实验 3 实现顺序队列的基本操作；
完成 P156 基础实验 5 实现链式队列的基本操作；
课后习题：
P158 选择题和填空题；
P159 编程题 1 和 6；
本教案由本书作者张光河撰写，若有任何问题可邮件到 guanghezhang@163.com
5
第 三 章 课 堂 教 学 实 施 计 划
第 5 课
教学过程设计： 复习 分钟；新课 分钟
讨论 分钟；其它 分钟
授课类型（请打√）：理论课□ 讨论课□ 实验课□ 习题课□ 其它□
教学方式（请打√）：讲 授□ 讨 论□ 示 教□ 指 导□ 其它□
教学手段（请打√）：多媒体□ 模 型□ 实 物□ 挂 图□ 音像□ 其它□
课堂教学：
栈和队列是十分重要的两种数据结构，它们被大量应用于各种计算机软件的设计和开发之中。从数据结构的角度来
看，它们都是一种特殊的线性表，我们可将其称为限定性数据结构。本章我们将介绍栈和队列的基本概念、存储方式及
典型应用，然后再介绍递归的基本概念、如何设计和实现递归算法，最后再借助于栈详细阐述如何将递归过程转换为非
递归过程。
3.1 栈
栈 是 一 种 只 能 在 一 端 进 行 操 作 的 线 性 表 ， 它 最 大 的 特 点 是 进行数 据 操 作 时 必 须 遵 循 “ 后 进 先 出
（
Last In First Out
，
LIFO
）
”
的原则。在本节中，我们首先将介绍栈的基本概念，然后根据其存储方式的不同，分
别介绍栈的顺序存储和链式存储，最后介绍栈的典型应用。
3.1.1 栈的基本概念
通常我们限定栈（
Stack
）的基本操作均只发生在栈的某一端，如取栈顶元素、在栈中插入或删除某一元素等。
我们把可以进行上述操作的这一端称为栈顶（
top
），而无法进行上述操作的另一端则被称为栈底（
bottom
）。栈中的
元素个数即为栈的长度，当栈中不包含任何元素时被称为空栈，此时栈中元素个数为零。栈的抽象数据类型的定义
参见教材
P88
表
3-1
。
3.1.2 栈的顺序存储
所谓栈的顺序存储，就是采用一组物理上连续的存储单元来存放栈中所有元素，并使用
top
指针指示当前栈中
的栈顶元素。我们通过使用顺序栈来实现栈的顺序存储，接下来我们将介绍如何实现顺序栈的一些基本操作。
1．顺序栈的基本操作
在文件
ex030102.py
中我们定义了一个用于顺序栈基本操作的
SequenceStack
类，参见教材
P90
表
3-2
。我们将
具体实现
__init__(self)
、
IsEmptyStack(self)
、
PushStack(self,x)
、
PopStack(self)
、
GetTopStack(self)
、
StackTraverse(self)
和
CreateStackByInput(self)
这
7
个方法。读者可根据自己的需要，自行实现其余方法。
（
1
）初始化栈函数的实现
我们先调用
SequenceStack
类的成员函数
__init__(self)
初始化一个顺序栈，其算法思路如下。
①
对栈空间进行初始化。
②
对栈顶指针进行初始化。
（
2
）判断栈是否为空的函数实现
我们调用
SequenceStack
类的成员函数
IsEmptyStack(self)
来判断当前栈是否为空，其算法思路如下。
①
将当前栈顶指针的值与之前初始化时设置的栈顶指针的值相比较。
