链栈
个人认为,简单形容栈就是只有一个头能进出。first in last out相信不是很难理解的问题,在这里主要讲一讲链栈。
首先链栈同样是栈,当然也是filo的。
链栈是指采用链接存储的结构实现的栈。事实上链栈和链表的样子很像。
其中data为数据,next为下一个数据的指针
class LinkStack { datatype data; LinkStack *next; }
LinkStack就是就是这样的数据类型。LinkStack t,*S=&t;。然后使用S->data描述该点元素的值,S->next来描述该节点逻辑后继值的存储地址。
由于链栈不存在栈满的情况,所以不需要像正常的顺序栈一样判断是否栈满。对链栈的操作同样有以下几类:置空栈,判空栈,判满栈,取栈顶元素,入栈,出栈。
链栈置空算法
LinkStack * SetStack() { LinkStack *LS; LS=NULL; return LS; }
链栈判断空算法
int StackEmpty(LinkStack *LS)//空时返回1,不空返回0 { if(LS==NULL) return 1; else return 0; }
链栈取顶算法
datatype GetTop(LinkStack *LS) { if(LS!=NULL) return LS->data; else cout<<"栈空"; }
链栈入栈算法
在栈顶插入值为x的元素存放在一个新创建的LinkStack的data中。原本的LS与新创建的LinkStack的next相等。然后LS与原来的首元素断开,与x连接。如图:
LinkStack *Push(LinkStack *LS,datatype x) { LinkStack *p; p=(LinkStack *)malloc(sizeof(LinkStack)) p->data=x; p->next=LS; LS=p; return LS; }
链栈出栈算法
首先将创建一个新的LinkStack *pop,不需要分配内存空间。直接将pop指向出栈data,LS指向pop的next空间。然后断开LS原本指向pop中data。
LinkStack *POP(LinkStack *LS) { LinkStack *poptem; poptem=LS; LS=poptem->next; free(poptem); return LS; }