《数据结构》课程教学资源：电子教案 第3章 栈和队列

第3章栈和队列 3.1 3.2队列 本章小结

第3章 栈和队列 3.1 栈 3.2 队列 本章小结

3.1栈 3.1.1栈的定义 3.1.2栈的顺序存储结 构及其基本运犷奥现 3.1.3栈的链式存储结构及 其基本运算的实现 3.1.4栈的应用例子

3.1.1 栈的定义 3.1.2 栈的顺序存储结 构及其基本运算实现 3.1.3 栈的链式存储结构及 其基本运算的实现 3.1.4 栈的应用例子 3.1 栈

3.1.1栈的定义 栈是一种只能在一端进行插入或删除操 作的线性表。表中允许进行插入、删除操作 的一端称为栈顶。 栈顶的当前位置是动态的栈顶的当前位 置由一个称为栈顶指针的位置指示器指示。 表的另一端称为栈底。 当栈中没有数据元素时称为空栈。 栈的插入操作通常称为进栈或入栈,栈的 删除操作通常称为退栈或出栈

栈是一种只能在一端进行插入或删除操 作的线性表。表中允许进行插入、删除操作 的一端称为栈顶。 栈顶的当前位置是动态的,栈顶的当前位 置由一个称为栈顶指针的位置指示器指示。 表的另一端称为栈底。 当栈中没有数据元素时,称为空栈。 栈的插入操作通常称为进栈或入栈,栈的 删除操作通常称为退栈或出栈。 3.1.1 栈的定义

4 433 dcba 43310 cba 4331 0 0 (a)空栈 (b)元素a入栈(c)元素b、c、d入栈(d元素d出栈

栈的几种基本运算如下: (1)初始化栈 EInitstack(&s):构造一个空栈s (2)销毁栈 ClearStack(&s):释放栈s占用的 存储空间。 (3)求栈的长度 StackLength(s):返回栈s中 的元素个数。 (4)判断栈是否为空 StackEmpty(s):若栈s 为空,则返回真;否则返回假

栈的几种基本运算如下: (1)初始化栈InitStack(&s):构造一个空栈s 。 (2)销毁栈ClearStack(&s):释放栈s占用的 存储空间。 (3)求栈的长度StackLength(s):返回栈s中 的元素个数。 (4)判断栈是否为空StackEmpty(s):若栈s 为空,则返回真；否则返回假

(5)进栈Push(&S,e):将元素e插入到栈s中作 为栈顶元素。 ()出栈Pop(&s,&e):从栈s中退出栈顶元素, 并将其值赋给e。 (7)取栈顶元素 GetTop(s,&e):返回当前的栈 顶元素,并将其值赋给e。 (8)显示栈中元素 DispStack(s):从栈顶到栈 底顺序显示栈中所有元素

(5)进栈Push(&S,e):将元素e插入到栈s中作 为栈顶元素。 (6)出栈Pop(&s,&e):从栈s中退出栈顶元素, 并将其值赋给e。 (7)取栈顶元素GetTop(s,&e):返回当前的栈 顶元素,并将其值赋给e。 (8)显示栈中元素DispStack(s):从栈顶到栈 底顺序显示栈中所有元素

∥3.1.2栈的顺序存情结构及其基本运算奥现 假设栈的元素个数最大不超过正整数 Maxsize,所有的元素都具有同一数据类型 ElemType,则可用下列方式来定义栈类型 Sastack. typedef struct ElemType elem MaxSizel int top 栈指针* SqStack

3.1.2 栈的顺序存储结构及其基本运算实现 假设栈的元素个数最大不超过正整数 MaxSize,所有的元素都具有同一数据类型 ElemType,则可用下列方式来定义栈类型 SqStack: typedef struct { ElemType elem[MaxSize]； int top； /*栈指针*/ } SqStack；

例3.1设有4个元素a、b、c、d进栈,给 出它们所有可能的出栈次序。 答:所有可能的出栈次序如下 abcd abdc acbd acdb adcb bacd bade bcad beda bdca cbad cbda cdba dcba

例3.1 设有4个元素a、b、c、d进栈,给 出它们所有可能的出栈次序。 答:所有可能的出栈次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba

例3.2设一个栈的输入序列为A,B,C,D,则 借助一个栈所得到的输出序列不可能是 (A)A, B, C, B)D, C,B,A (C)A, CD, B D) D,A, B, C 答:可以简单地推算,得容易得出D,A,B,C 是不可能的,因为D先出来,说明A,B,C,D均在 栈中按照入栈顺序在栈中顺序应为D,C,B,A, 出栈的顺序只能是D,C,B,A。所以本题答案 为D

例3.2 设一个栈的输入序列为A,B,C,D,则 借助一个栈所得到的输出序列不可能是 。 (A) A,B,C,D (B) D,C,B,A (C) A,C,D,B (D) D,A,B,C 答:可以简单地推算,得容易得出D,A,B,C 是不可能的,因为D先出来,说明A,B,C,D均在 栈中,按照入栈顺序,在栈中顺序应为D,C,B,A, 出栈的顺序只能是D,C,B,A。所以本题答案 为D

例33已知一个栈的进栈序列是1,2,3 ●●● n 其输出序列是P1P2…Dn,若p=n,则p的值。 (A)i (B)n-1 (C)n-计+1(①D)不确定 答:当p=n时,输出序列必是n,n-1,3,2,1, 则:p2=n-1,p3=n-2,…,pn=1,推断出p=n-+1,所以 本题答案为C

例3.3 已知一个栈的进栈序列是1,2,3,…,n, 其输出序列是p1 ,p2 ,…,pn ,若p1=n,则pi的值 。 (A) i (B) n-i (C) n-i+1 (D) 不确定 答:当p1=n时,输出序列必是n,n-1,…,3,2,1, 则:p2=n-1,p3=n-2,…,pn =1,推断出pi=n-i+1,所以 本题答案为C