第三章栈和队列 1,教学内容:1 栈应用举例 3.3队列 3.4队列应用举例 2教学目的:(理解栈的定义、特征及在其上所定义的基本运算 (2)掌握在两种存储结构上对栈所施加的基本运算的实现 (3)理解队列的定义、特征及在其上所定义的基本运算 (4)掌握在两种存储结构上对队列所施加的基本运算的实现。 3教学重点:(1)栈的定义及逻辑特点,栈的基本运算: (2)栈的顺序存储结构及运算实现 (3)栈的链式存储结构及运算实现 (4)队列的定义及逻辑特点,队列的基本运算 (5)队列的顺序存储结构及其上的运算实现 (6)队列的链式存储结构及运算实现。 4.教学难点:(1)顺序栈的溢出判断条件 (2)循环队列的队空、队满判断条件 (3)循环队列上的插入、删除操作。 5教学时间:6学时 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 1 第三章 栈和队列 ⒈教学内容：3.1 栈 3.2 栈应用举例 3.3 队列 3.4 队列应用举例 ⒉教学目的：⑴理解栈的定义、特征及在其上所定义的基本运算； ⑵掌握在两种存储结构上对栈所施加的基本运算的实现； ⑶理解队列的定义、特征及在其上所定义的基本运算； ⑷掌握在两种存储结构上对队列所施加的基本运算的实现。 ⒊教学重点：⑴栈的定义及逻辑特点，栈的基本运算； ⑵栈的顺序存储结构及运算实现； ⑶栈的链式存储结构及运算实现； ⑷队列的定义及逻辑特点，队列的基本运算； ⑸队列的顺序存储结构及其上的运算实现； ⑹队列的链式存储结构及运算实现。 ⒋教学难点：⑴顺序栈的溢出判断条件； ⑵循环队列的队空、队满判断条件； ⑶循环队列上的插入、删除操作。 ⒌教学时间：6 学时
3.1栈 ◆栈的定义及基本运算 ◆栈的存储实现和天现 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 2 3.1 栈 栈的定义及基本运算 栈的存储实现和运算实现
3.1.1栈的定义及基本运算 ◆栈是限制在表的一端进行插入和删除的线性表。允许 插入、删除的这一端称为栈顶,另一个固定端称为栈底 当表中没有元素时称为空栈。 入栈 出栈 ◆右图所示栈中有三个元素, 进栈的顺序是a1、a2、a3,当 需要出栈时其顺序为a3、a2、 a1,所以栈又称为后进先出的tp 线性表( Last in first out) 简称LIFO表 a 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 3 3.1.1 栈的定义及基本运算 栈是限制在表的一端进行插入和删除的线性表。允许 插入、删除的这一端称为栈顶，另一个固定端称为栈底。 当表中没有元素时称为空栈。 右图所示栈中有三个元素， 进栈的顺序是a1、a2、a3，当 需要出栈时其顺序为a3、a2、 a1，所以栈又称为后进先出的 线性表（Last In First Out）， 简称 LIFO表
栈的基本操作有: (1)栈初始化: Init stack(s) 操作结果是构造了一个空栈。 (2)栈空: Empty Stack(s 操作结果是若s为空栈返回为1,否则返回为0。 (3)入栈: Push stack(s,x) 操作结果是在栈s的顶部插入一个新元素x,x成为新的栈顶元素 (4)出栈:Pop_ Stack(s) 在栈s存在且非空的情况下,操作结果是将栈s的顶部元素从栈中删除 (5)读栈顶元素: Top Stack(s) 在栈s存在且非空情况下,操作结果是读栈顶元素,栈不变化。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 4 • 栈的基本操作有： ⑴栈初始化：Init_Stack(s) 操作结果是构造了一个空栈。 ⑵判栈空：Empty_Stack(s) 操作结果是若s为空栈返回为1，否则返回为0。 ⑶入栈： Push_Stack(s，x) 操作结果是在栈s的顶部插入一个新元素x，x成为新的栈顶元素。 ⑷出栈：Pop_Stack(s) 在栈s存在且非空的情况下，操作结果是将栈s的顶部元素从栈中删除。 ⑸读栈顶元素：Top_Stack(s) 在栈s存在且非空情况下，操作结果是读栈顶元素，栈不变化
3.1.2栈的存储实现和运算实现 1顺序栈 ◆栈中的数据元素用一个预设的足够长度的一维数组来实 现: datatype data[ MAXSIZE],栈底位置可以设置在数组 的任一个端点,而栈顶是随着插入和删除而变化的,用 int top来作为栈顶的指针,指明当前栈顶的位置 将daa和top封装在一个结构中,顺序栈的类型描述如下: ◆# define maXsize1024 typedef struct datatype data[MAXsIZE int top; 3SeqStack ◆定义一个指向顺序栈的指针: SeqStack*s 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 5 3.1.2 栈的存储实现和运算实现 ⒈顺序栈 栈中的数据元素用一个预设的足够长度的一维数组来实 现：datatype data[MAXSIZE]，栈底位置可以设置在数组 的任一个端点，而栈顶是随着插入和删除而变化的，用 一个int top 来作为栈顶的指针，指明当前栈顶的位置， 将data和top封装在一个结构中，顺序栈的类型描述如下： #define MAXSIZE 1024 typedef struct {datatype data[MAXSIZE]; int top; }SeqStack； 定义一个指向顺序栈的指针： SeqStack *s;