第三章栈和队列 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;
通常0下标端设为栈底,这样空栈时栈顶指针top=-1;入 栈时,栈顶指针加1,即s>top++;出栈时,栈顶指针减 1,即>0op=。栈操作的示意图如图所示 EDCBA A EDCBA2 (a空栈 b)一个元素()5个元素(d3个元素(e)空栈 图(a)是空栈,图(c)是A、B、C、D、E5个元素依次入栈之后,图(d)是在 图(c)之后E、D相继出栈,此时栈中还有3个元素,或许最近出栈的元素D、 E仍然在原先的单元存储着,但top指针已经指向了新的栈顶,则元素D、E 已不在栈中了。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 • 通常0下标端设为栈底，这样空栈时栈顶指针top=-1; 入 栈时，栈顶指针加１，即s->top++; 出栈时，栈顶指针减 １，即s->top--。栈操作的示意图如图所示。 图(a)是空栈，图(c)是A、B、C、D、E 5个元素依次入栈之后，图(d)是在 图(c)之后E、D相继出栈，此时栈中还有3个元素，或许最近出栈的元素D、 E仍然在原先的单元存储着，但top指针已经指向了新的栈顶，则元素D、E 已不在栈中了
(1)置空栈 首先建立栈空间,然后初始化栈顶指针。 SeqStack *Init Seqstack i Seqstack * S, =malloc(sizeof( SeqStack) S->top=-1 return s 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 ⑴ 置空栈 首先建立栈空间，然后初始化栈顶指针。 SeqStack *Init_SeqStack( ) { SeqStack *s; s=malloc(sizeof(SeqStack)); s->top= -1; return s; }
(2)判空栈 int Empty Seqstack(Seqstack*s d if(s->top==-1) return 1 else return 0 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 8 ⑵判空栈 int Empty_SeqStack(SeqStack *s) { if (s->top= = -1) return 1; else return 0; }
(3)入栈 int Push Seq Stack(SeqStack*s, datatype x Rif(s->top==MAXSIZE-1 return 0 /栈满不能入栈* else i S->top++ S->data[s->top]=X, return 1 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 9 ⑶入栈 int Push_SeqStack(SeqStack *s, datatype x) {if (s->top= =MAXSIZE-1) return 0; /*栈满不能入栈*/ else { s->top++; s->data[s->top]=x; return 1; } }
(4)出栈 P int Pop_ SeqStack(SeqStack*s, datatype*x) f if(Empty Seqstack (s)) return 0 *栈空不能出栈* else (Axs->data[s->top S->top--, return }/栈顶元素存入*x,返回* 2021年1月21日 数据结构讲义 10
2021年1月21日 数据结构讲义 10 ⑷出栈 int Pop_SeqStack(SeqStack *s, datatype *x) { if (Empty_SeqStack(s)) return 0; /*栈空不能出栈 */ else { *x=s->data[s->top]; s->top--; return 1; } /*栈顶元素存入*x，返回*/ }