链栈

链栈

  个人认为,简单形容栈就是只有一个头能进出。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;
}
上一篇:链栈


下一篇:C语言数据结构链栈(创建、入栈、出栈、取栈顶元素、遍历链栈中的元素)