中国地质大学（武汉）：《数据结构和VC编程》课程教学资源（课件讲稿）第三章 栈和队列

第三章栈和队列 3.1栈 栈的主要操作如下： (1)、建立一个空栈 (2)、进栈 (3)、出栈： (4)、判断一个栈是否为空？ (5)、判断栈是否已满？ (6)、获得栈顶元素值 PT PRESS 退出 按续不一列

第三章 栈和队列 3．1栈 栈的主要操作如下： （1）、建立一个空栈 （2）、进栈 （3）、出栈： ( 4 ) 、判断一个栈是否为空？ （5）、判断栈是否已满？ （6）、获得栈顶元素值 退出

出栈a·41 进栈a1☑2，…a, an 4 a 图3-1 PT PRESS 然东续下一 n

图3-1

3.1.2栈的表示和操作的实现 1、顺序存储的栈 #define MAXSIZE 50 typedef struct {elemtype elem[MAXSIZE]; int top; }SQSTACK; (1)、建立一个空栈 void initstack(SQSTACK *s) {(*s.top=-1;} (2)、判断一个栈是否为空 int stackempty(SQSTACK s) {if (s.top==-1)return 1;else return 0; PT PRESS

3．1．2栈的表示和操作的实现 1、顺序存储的栈 #define MAXSIZE 50 typedef struct {elemtype elem[MAXSIZE]; int top; }SQSTACK; （1）、建立一个空栈 void initstack(SQSTACK *s) {(*s).top=-1; } ( 2 ) 、判断一个栈是否为空 int stackempty(SQSTACK s) {if (s.top==-1) return 1; else return 0; }

(3)、让一个数据元素为e的结点进栈。 算法3.1 如书第42页所示 (4)、出栈一个结点并得到栈顶数据元素值 算法3.2 如书第42页所示 (5)、获取栈顶元素值 void getelm(SQSTACK s,elemtype *e) {if(s.top==-1){printf(“栈空n”);return; *e=s.elem[s.top]; PT PRESS

( 3 )、让一个数据元素为e的结点进栈。 算法 3.1 如书第42页所示 ( 4 )、出栈一个结点并得到栈顶数据元素值 算法 3.2 如书第42页所示 （5）、获取栈顶元素值 void getelm(SQSTACK s, elemtype *e) { if (s.top==-1) {printf(“栈空\n”); return; *e=s.elem[s.top]; }

1、接存储的栈 (1)、建立一个空栈 NODEPTR top; top=NULL; (2)、让一个数据元素为e的结点进栈 算法3.3 如书第43页所示 PT PRESS 然东续了一列 n

1、接存储的栈 (1)、建立一个空栈 NODEPTR top; top=NULL; (2)、让一个数据元素为e的结点进栈 算法 3．3 如书第43页所示

(③)、出栈一个结点并得到栈顶数据元素值 算法3.4 如书第43页所示 PT PRESS 然东续下一配 n

(3)、出栈一个结点并得到栈顶数据元素值 算法 3．4 如书第43页所示

3.1.3栈的应用举例 1、子程序的调用和返回 Main() Sub ( Sub;() Sub） { { { Sub () Sub Sub ) r: 图3-2 PT PRESS 按续不一

3．1．3栈的应用举例 1、子程序的调用和返回 图3-2

1、算术表达式求值 表3.1算符的栈内、外优先级 算符 优先级函数 (x) isp(x)(栈内) ielp(x)(栈外) A、一目减 3 4 *,/ 2 2 +,一 1 1 ( 0 4 PT PRESS 然东续了一 n

1、算术表达式求值 表3．1 算符的栈内、外优先级 算符 优先级函数 （x） isp（x）（栈内） ielp（x）（栈外） ^、一 目 减 3 4 *，/ 2 2 q  R( + q，)  C(q) 1 1 （ 0 4

[例1]计算：2+3*2^2^2*5-2； 22232 22232 g 232 232 2232 2232 4232 632 望 582 582 6 48 5 =240 ch tLu ch 图3-3 PT PRESS 续不一 n

[例1] 计算：2+3*2^2^2*5-2; 图3-3

1例2]计算3*2^(4+2*2-6)-5； 23 23 2 423 423 2423 2423 22423 22423 4423 哥 823 6823 6823 g 223 12 48◆5 =240 S 5 12 88tw ch 图3.4 PT PRESS 续不一 n

[例2] 计算3*2^(4+2*2-6)-5; 图3．4