欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

栈的链式存储结构及实现

程序员文章站 2022-06-05 13:42:31
...

栈的链式存储结构,简称为链栈,如图所示:

栈的链式存储结构及实现

对于链栈来说,基本不存在栈满的情况,除非内存以没有存储空间。

链栈的结构代码如下:

typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;

}StackNode, *LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

链栈的操作和普通的单链表类似,仅在插入和删除操作上不同。

对于链栈的的进栈push操作,代码如下:

/*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S, SElemType e)
{
    LinkStackPtr s = (LinkStackPtr)malloc(sizeof(Node));
    s->data =e;
    s->next = S->top;  //首先把当前的栈顶指针赋给 新结点的直接后继
    S->top = s;        //然后将新的结点s赋给栈顶指针
    S->count++;
    return OK;
}

至于链栈的出栈pop操作,也是三个步骤。假设变量p用来存储要删除的栈顶结点,将栈顶指针下移一位,最后释放p即可。

/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */

Status Pop(LinkStack *S, SElemType *e)
{
    LinkStackPtr p;
    if(StackEmpty( *S))
        return ERROR;
    *e = S->top->data;
    p = S->top;            //将栈顶结点赋值给p
    S->top = S->top->next;  //栈顶指针下移一位,指向后一结点
    free(p);               //释放p
    S->count--;
    return OK;
}

如果栈在使用过程中元素变化不可预料,可能会有很多个,可能又比较少,那么推荐使用链栈;反之,如果变化范围可控,那么使用顺序栈会好一些。