栈的类型定义ADT Stack 数据对象：D= { a; |a, EElemSet, i=1,2,..,n, n≥0 )数据关系：R1 = { <ai-1, a, >|ai-1, a, ED, i=-2,..,n )约定a.端为栈顶，a,端为栈底基本操作：? ADT Stack
ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,.,n, n≥0 } 数据关系： R1＝{ <ai-1 , ai >| ai-1 , ai∈D, i=2,.,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： } ADT Stack 栈的类型定义
InitStack(&S)DestroyStack(&S)StackLength(S)StackEmpty(s)GetTop(S, &e)ClearStack(&S)Push(&S, e)Pop(&S, &e)StackTravers(S, visitO)
InitStack(&S) DestroyStack(&S) ClearStack(&S) StackEmpty(s) StackLength(S) GetTop(S, &e) Push(&S, e) Pop(&S, &e) StackTravers(S, visit())
栈的表示和实现3.1.2★顺序栈类似于线性表的顺序映象实现指向表尾的指针可以作为栈顶指针栈的顺序存储表示/ / -----100:#define STACK INIT SIZE10;#define STACKINCREMENTtypedef struct SElemTypee *base;SElemType *top,int stacksize: SqStack;
顺序栈 3.1.2 栈的表示和实现 类似于线性表的顺序映象实现， 指向表尾的指针可以作为栈顶指针。 //- 栈的顺序存储表示- #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack;
实现：一维数组s[M]栈空栈满topOF5AE4?DtopC2topBtopBAtopOtopAOtasebasebase出栈进栈空栈设数组维数为M栈底指针base始终top=base栈空，此时出栈，则指向栈底位置：栈顶下溢（underflow）指针top，其初值指向top=M,栈满，此时入栈，则上栈底，始终在栈顶元素的下一个位置溢(overflow)
实现：一维数组s[M] 1 top 2 3 4 5 0 进栈 A 栈满 B C D E F 设数组维数为M top=base,栈空，此时出栈，则 下溢（underflow) top=M,栈满，此时入栈，则上 溢（overflow) top top top top top 1 2 3 4 5 0 空栈 top base base top 出栈 top top 栈空 base 栈底指针base,始终 指向栈底位置；栈顶 指针top,其初值指向 栈底，始终在栈顶元 素的下一个位置 1 2 3 4 5 A 0 B top
Status InitStack (SqStack &S)构造一个空栈SS.base=(SElemType*)malloc(STACK INIT_SIZE*sizeof(SElemType))if（!S.base)exit（OVERFLOW)；//存储分配失败S.top = S.base;S.stacksize = STACK INIT SIZEreturn OK:
Status InitStack (SqStack &S) {// 构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType)); if (!S.base) exit (OVERFLOW); //存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; }