3.1栈 3.1.1抽象数据类型栈的定义 Pop(&S,&e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并 用e返回其值。 a a2 -16 145
— 16 — 3.1 栈 Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并 用 e 返回其值。 a1 a2 … … an-1 an 3.1.1 抽象数据类型栈的定义
3.1栈 —3.1.1抽象数据类型栈的定义 1.一个栈的入栈序列是1,2,3，其出栈序列有 几种可能？ 2.一个栈的入栈序列是a,b,C,d,e,则栈的 不可能的输出序列是。 (A)edcba (B)decba (C)dceab (D)abcde -17 145
— 17 — 3.1 栈 2.一个栈的入栈序列是a，b，c，d，e，则栈的 不可能的输出序列是。 （A）edcba （B）decba （C）dceab （D）abcde 1.一个栈的入栈序列是1，2，3，其出栈序列有 几种可能？ 3.1.1 抽象数据类型栈的定义
3.1栈 3.1.2栈的表示和实现 顺序栈 ∥--栈的顺序存储表示 #define STACK INIT SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType*base;/栈底指针 SElemType *top; /栈顶指针 int stacksize; /最大容量 SqStack; -18 1945
— 18 — 3.1 栈 //----- 栈的顺序存储表示 ----- #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int stacksize; //最大容量 } SqStack; 3.1.2 栈的表示和实现 顺序栈
3.1栈 句栈顶 3.1.2栈的表示式 当栈用顺序结构存储时， 栈的基本操作如建空栈、进 顺序栈的图 栈、出栈等如何实现？ n 80 n-1 an-1 n-2 S.stacksize 100 S.top 81 1 S.base a 0 19 1945
— 19 — 3.1 栈 3.1.2 栈的表示和实现 … an an-1 … a2 a1 99 n n-1 n-2 1 0 S.stacksize 100 S.top S.base 顺序栈的图示 约定栈顶指针指向栈顶 当栈用顺序结构存储时， 元素的下一个位置 栈的基本操作如建空栈、进 栈、出栈等如何实现？
3.1栈 ■栈空的标记：top=base; ■入栈时，指针top增1：top=top+1 ■ 出栈时，指针top减1：top=top-1 ■栈满：top-base>=stacksize E D C top B base A 20 145
— 20 — 3.1 栈 栈空的标记：top=base； 入栈时，指针top增1：top=top+1 出栈时，指针top减1：top=top-1 栈满：top-base>=stacksize top base A B C D E