清华大学：《数据结构》课程电子教案（PPT课件讲稿）第3章 栈和队列

取栈顶元素p47 Status GetTop(SqStack S, sElem Type &e) if(S top==S base) return ERROR e=*(.top-1) return oK 第3章 2021/2/20

第3章 2021/2/20 11 取栈顶元素 p47 Status GetTop(SqStack S, SElemType &e) { if (S.top == S.base) return ERROR; e = *(S.top-1); return OK; }

进栈操作p47 Status Push(sqstack &s, sElem Type e if(S top-S base>=S. stacksize) i Sbase=(SElem Type*)realloc(S base, (S stacksize+STACKINCREMENT) *sizeof(Elem Type) if(!S base) return(OVERFLOW) S top S base +S. stacksize S. stacksize + STACKINCrEMeNt *S top++=e, *S top=e; S top=S top+1 return OK 第3章 2021/2/20

第3章 2021/2/20 12 进栈操作 p47 Status Push(SqStack &S, SElemType e) { if (S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT) *sizeof(ElemType)); if (!S.base) return (OVERFLOW); S.top = S.base +S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; /* *S.top = e; S.top = S.top+1; return OK; }

退栈操作p47 Status Pop(Sqstack &s, selem Type &e) if(s top==Sbase) return ERROR 8--S. top; /*S top=S top; -1; e=S top return OK 第3章 2021/2/20

第3章 2021/2/20 13 退栈操作 p47 Status Pop(SqStack &S, SElemType &e) { if (S.top == S.base) return ERROR; e=*--S.top; /* S.top= S.top;-1; e=*S.top; return OK; }

2)链栈—栈的链式存储结构 不带头结点的单链表,其插入和删除操 作仅限制在表头位置上进行。链表的头 指针即栈顶指针 类型定义: typedef struct SNodei SElem Type data struct snode *next )SNode, *Link Stack Linkstack s 第3章 2021/2/20

第3章 2021/2/20 14 2）链栈——栈的链式存储结构 ▪ 不带头结点的单链表，其插入和删除操 作仅限制在表头位置上进行。链表的头 指针即栈顶指针。 ▪ 类型定义： typedef struct SNode{ SElemType data; struct SNode *next; }SNode, *LinkStack; LinkStack s;

●链栈示意图p47图3.3 tp→ ∧ ●栈空条件:s=NULL ●栈满条件:无/无 Free Memory可申请 第3章 2021/2/20

第3章 2021/2/20 15 ⚫ 链栈示意图 p47 图3.3 ⚫ 栈空条件： s=NULL ⚫ 栈满条件： 无 / 无Free Memory可申请