【大话数据结构C语言】12 链栈结构及其基本操作

根据之前的顺序栈类比，栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？

类比单链表的头指针和栈顶指针，为什么不合二为一呢？

所以想出了把栈顶放在单链表的头部

对于链栈来说，基本不存在栈满的情况

链栈的结构代码：

/* 链栈结构 */
typedef struct StackNode
{
        SElemType data;
        struct StackNode *next;
}StackNode,*LinkStackPtr;


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

链栈的进栈操作： 假设元素值是e的新结点是s,top为栈顶指针

其代码结构：

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

出栈操作： 假设变量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;
}

对比顺序栈和链栈，他们在时间复杂度上是一样的，都是O（1），空间上，顺序栈需要实现确定 一个固定的长度，可能会存在内存空间浪费的问题，但是他的优势是存取时定位方便，而链栈要求每个元素都有指针域，这同时也增加了一些内存开销，但是对于栈的长度没有限制

所以，如果栈在使用中元素变化不可预料，最好是用链栈，反之使用顺序栈会好一些

仿照顺序栈的例子用链栈实现：

#include 
#include 
typedef struct lineStack{
    int data;
    struct lineStack * next;
}lineStack;
lineStack* push(lineStack * stack,int a){
    lineStack * line=(lineStack*)malloc(sizeof(lineStack));
    line->data=a;
    line->next=stack;
    stack=line;
    return stack;
}
lineStack * pop(lineStack * stack){
    if (stack) {
        lineStack * p=stack;
        stack=stack->next;
        printf("弹栈元素：%d ",p->data);
        if (stack) {
            printf("栈顶元素：%d\n",stack->data);
        }else{
            printf("栈已空\n");
        }
        free(p);
    }else{
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}
int main() {
    lineStack * stack=NULL;
    stack=push(stack, 1);
    stack=push(stack, 2);
    stack=push(stack, 3);
    stack=push(stack, 4);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    return 0;
}