进栈示例 tacksize e top C C base base→ ase- 空栈 a进栈 b进栈 进栈进栈溢出 6 第3章 2021/2/20
第3章 2021/2/20 6 进栈示例 base base base base base stacksize
退栈示例 e top-e d|top→d [a tse → k退栈 e退栈 d退栈 a退栈 空栈 7 第3章 2021/2/20
第3章 2021/2/20 7 退栈示例 base base base base base
几点说明: 栈空条件:s.top=s.base此时不能出栈 栈满条件:s.top-s.base>=s. stacksize 进栈操作:*stop++=e;或*s.top=e;s:top+ 退栈操作:c=*-stop;或stop-;c=*stop; 当栈满时再做进栈运算必定产生空间溢出, 简称“上溢”; 当栈空时再做退栈运算也将产生溢出,简 称“下溢 8 第3章 2021/2/20
第3章 2021/2/20 8 几点说明： ⚫ 栈空条件：s. top =s. base 此时不能出栈 ⚫ 栈满条件：s.top-s.base>=s.stacksize ⚫ 进栈操作：*s.top++=e; 或*s.top=e; s.top++; ⚫ 退栈操作：e=*--s.top； 或s.top--； e=*s.top； ⚫ 当栈满时再做进栈运算必定产生空间溢出， 简称“上溢”; ⚫ 当栈空时再做退栈运算也将产生溢出，简 称“下溢
基本操作的实现 栈的初始化操作p47 Status InitStack(SqStack &S) 取栈顶元素p4 Status GetTop(Sqstack s, sElem Type &e) 进栈操作p47 Status Push(sqStack &s, selem Type e) 退栈操作p47 Status Pop(sqstack &s, selem Type &e) 9 第3章 2021/2/20
第3章 2021/2/20 9 基本操作的实现 ⚫ 栈的初始化操作 p47 Status InitStack(SqStack &S) ⚫ 取栈顶元素 p47 Status GetTop(SqStack S, SElemType &e) ⚫ 进栈操作 p47 Status Push(SqStack &S, SElemType e) ⚫ 退栈操作 p47 Status Pop(SqStack &S, SElemType &e)
栈的初始化操作p47 Status InitStack(SqStack &s)i S base=(SElem Type )malloc(staCK INIT size sizeof(elem Type)) if(!S base)return(OVERFLOW) S top=S base S. stacksize= STACK INIT SIZE return OK 第3章 2021/2/20
第3章 2021/2/20 10 栈的初始化操作 p47 Status InitStack (SqStack &S) { S.base = (SElemType )malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (!S.base) return (OVERFLOW); S.top=S.base; S.stacksize = STACK_INIT_SIZE; return OK; }