进栈示例 tp→ktp-□ edcba tp→a 加OP→空栈 →a进栈 b进栈 k进栈 Z进栈溢出 退栈示例 to p edcb top-d to p dcba 退栈 e退栈 d退栈top→a退栈tp→空栈 北京邮电大学自动化学院 11
北京邮电大学自动化学院 11 进栈示例 退栈示例
栈的顺序存储表示 o#define STACK INIT SIZE 100: o#define STACKINC REMENT 10 ● typedef Struct ● SElemType*base;∥在栈构造之前和销毁之后, base的值为NULL。 ● SElemType“top; o int stacksize; SqStack; 北京邮电大学自动化学院
北京邮电大学自动化学院 12 栈的顺序存储表示 ⚫ #define STACK_INIT_SIZE 100; ⚫ #define STACKINCREMENT 10; ⚫ typedef Struct{ ⚫ SElemType *base;//在栈构造之前和销毁之后， base的值为NULL。 ⚫ SElemType *top; ⚫ int stacksize; }SqStack;
基本操作的函数原型说明 ● Status Initstack( SqStack&s);H构造一个空栈 ● Status DestroyStack(SqStack&s):/销毁栈 ● Status clearStack( SqStack&s);把S置为空栈 ● Status StackEmpty( SqStack s);∥ ● Status StackLengh( SqStack s);∥ ● Status GetTop( SqStack s, SElemType&e);∥l o Status push(Sqstack &s, SElemType e); /l ● Status Pop( Sqstack&s, SElem Type&e);∥ 北京邮电大学自动化学院 13
北京邮电大学自动化学院 13 ⚫ Status InitStack (SqStack &s);//构造一个空栈 基本操作的函数原型说明 ⚫ Status DestroyStack (SqStack &s);//销毁栈 ⚫ Status ClearStack (SqStack &s);//把S置为空栈 ⚫ Status StackEmpty (SqStack s);// ⚫ Status StackLengh (SqStack s);// ⚫ Status GetTop (SqStack s,SElemType &e);// ⚫ Status push (SqStack &s,SElemType e);// ⚫ Status Pop (SqStack &s,SElemType &e);//
基本操作的算法描述 ● Status Initstack( SqStack&s)构造一个空栈 o S base=(sElem Type *)malloc (Stack_init size*sizeof (ELlem Type ●if(! S,base)exit( OVERFLOW);∥存储分配失败 ●Stop= s base; os. stacksize=STACK INIT SIzE. ● return oK IInitstack 北京邮电大学自动化学院 14
北京邮电大学自动化学院 14 基本操作的算法描述 ⚫ Status InitStack (SqStack &s){//构造一个空栈 ⚫ S.base=（SElemType *）malloc （Stack_init_size *sizeof（ELlemType））; ⚫ if (!S.base) exit (OVERFLOW);//存储分配失败 ⚫ S.top=S.base; ⚫ S.stacksize=STACK_INIT_SIZE; ⚫ return OK; ⚫ }InitStack
基本操作的算法描述 Status GetTop(SqStack &s, SElemtype &e) ●若栈不空,则用e返回S的栈顶元素,并返回OK; 否则返回 ERROR o If(Stop==S base) return ERROR; ●e=*(stop-1) ● return OK JGetTop 北京邮电大学自动化学院
北京邮电大学自动化学院 15 基本操作的算法描述 ⚫ Status GetTop (SqStack &s,SElemtype &e){ ⚫若栈不空，则用e 返回S的栈顶元素，并返回OK； 否则返回ERROR ⚫ If (S.top==S.base) return ERROR; ⚫ e=*(S.top-1); ⚫ return OK; ⚫ }GetTop