栈的链式存储结构

栈的链式存储结构，简称为链栈。

栈是栈顶来做插入和删除操作，由于单链表有头指针，而栈顶指针也是必须得，所以比较好的办法是把栈顶放在单链表的头部。因为栈顶在头部，单链表中常用的头结点也就失去了意义，通常对于链栈来说。是不需要头结点的。如下图所示：

栈的链式存储结构

对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL。

链栈的结构代码如下：

typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;

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

1.进栈操作

对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针，示意图如下：

栈的链式存储结构

代码实现如下：

int Push(LinkStack *S, SElemType e)
{
    LinkStackPtr st = (LinkStackPtr)malloc(sizeof(StackNode));
    st->data = e;
    st->next = S->top;  //把当前的栈顶元素赋值给新结点的直接后继
    S->top = st;        //将新的结点st赋值给栈顶指针
    S->count++;
    return OK;

}

2.出栈操作

链栈的出栈pop操作分为三步。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可，如下图所示：

栈的链式存储结构
代码实现如下：

int Pop(LinkStack *S, SElemType *e)
{
    LinkStackPtr p;

    *e = S->top->data;
    p = S->top;                 //将栈顶结点赋值给p
    S->top = S->top->next;      //使得栈顶指针下移一位，指向后一结点
    free(p);                    //释放结点p
    S->count--;
    
    return OK;
}

秒客网

栈的链式存储结构

相关文章