3 压栈（元素进栈） Status Push (SqStack &S,SElemType e) {∥插入元素e为新的栈顶元素 if(S.top-S.base>=S.stacksize)栈满，追加存储空间 S.base=(SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElem Type)); if(!S.base)exit(OVERFLOW); ∥存储分配失败 S.top=S.base+S.stacksize; S.stacksize +=STACKINCREMENT; } *(S.top++)=e; ∥插入新的元素 return OK; }//Push
3 压栈(元素进栈) Status Push (SqStack &S, SElemType e) { // 插入元素e 为新的栈顶元素 if(S.top-S.base>=S.stacksize){ //栈满，追加存储空间 S.base=(SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElem Type)); if(!S.base) exit(OVERFLOW); // 存储分配失败 S.top=S.base+S.stacksize; S.stacksize +=STACKINCREMENT; } *(S.top++) = e; // 插入新的元素 return OK; } //Push
4弹栈（元素出栈） Status Pop (Stack &S,ElemType &e) {∥栈不空，删除S的栈顶元素，用e返回其值，并返回 OK;否则返回ERROR if(S.top =S.base)return ERROR; 空栈 e =*(--S.top); 返回非空栈中栈顶元素 return OK; }l/Pop
4 弹栈(元素出栈) Status Pop (Stack &S, ElemType &e) { // 栈不空，删除S的栈顶元素，用e返回其值，并返回 OK；否则返回 ERROR if (S.top == S.base) return ERROR; //空栈 e = *(--S.top); //返回非空栈中栈顶元素 return OK; } //Pop
3.1.2.2栈的链式存储表示 栈的链式存储结构称为链栈，是运算受限的单链表。其插 入和删除操作只能在表头位置上进行。因此，链栈没有必 要像单链表那样附加头结点，栈顶指针top就是链表的头指 针。 top top 链栈的结点类型说明如下： a 空栈 typedef struct Stack Node a3 ElemType data; a2 struct Stack Node *next }Stack Node a1△ 非空栈
栈的链式存储结构称为链栈，是运算受限的单链表。其插 入和删除操作只能在表头位置上进行。因此，链栈没有必 要像单链表那样附加头结点，栈顶指针top就是链表的头指 针。 3.1.2.2 栈的链式存储表示 空栈 top ⋀ 非空栈 top a4 a3 a1 ⋀ a2 链栈的结点类型说明如下： typedef struct Stack_Node { ElemType data ; struct Stack_Node *next ; } Stack_Node ;
入栈算法 p top 栈底 p→ 出栈算法 t 栈底 top-☐x
入栈算法 …... ^ 栈底 top top x p 出栈算法 top …... ^ 栈底 top q
顺序栈和链栈的比较： 空间性能： >顺序栈：有元素个数的限制和空间浪费的问题。 >链栈：没有栈满的问题，只有当内存没有可用 空间时才会出现栈满，但是每个元素都需要一个 指针域，从而产生了结构性开销。 >总之，当栈的使用过程中元素个数变化较大时， 用链栈是适宜的，反之，应该采用顺序栈
空间性能： ➢顺序栈：有元素个数的限制和空间浪费的问题。 ➢链栈：没有栈满的问题，只有当内存没有可用 空间时才会出现栈满，但是每个元素都需要一个 指针域，从而产生了结构性开销。 ➢总之，当栈的使用过程中元素个数变化较大时， 用链栈是适宜的，反之，应该采用顺序栈。 顺序栈和链栈的比较：