数据结构（链栈——c语言实现）

链式栈（Linked Stack）是一种基于链表数据结构实现的栈。它利用链表节点的指针来存储元素，并通过指针的链接关系来维护栈的后进先出（LIFO, Last In First Out）特性。

链式栈的优点

动态大小：
链式栈的大小可以动态调整，不需要在创建时指定栈的最大容量。当栈满时，只需创建一个新的节点并将其链接到栈顶即可。
内存效率高：
链式栈只在需要时分配内存，不需要像数组那样预先分配一大块连续的内存空间。因此，它更适合于内存分配困难的嵌入式系统或内存碎片较多的环境。
避免内存浪费：
链式栈在元素弹出（pop）时，可以释放已使用节点的内存，避免内存浪费。而数组实现的栈在栈收缩时通常不能立即释放未使用的内存。
操作灵活性：
链式栈在栈顶和栈底的插入和删除操作都相对高效，因为这些操作只涉及指针的修改，不需要移动大量数据。
易于实现复杂操作：
由于链式栈的节点是独立的，可以很容易地实现一些复杂的栈操作，如栈的合并、分割、复制等。
无需初始化大量空间：
在实际应用中，栈的大小往往难以预估。链式栈可以根据需要动态增长，而不需要在初始化时分配过多的空间。
减少栈溢出风险：

在一些应用场景中，栈的大小可能会非常大，数组实现的栈可能会遇到栈溢出的问题。链式栈由于动态分配内存，可以有效减少这种风险。

链栈

链式栈的实现和链表类似，都是用指针来保存下一个节点的地址，在这里也是约定头节点不存数据；因为栈只能在一端进行操作，因此我们以头结点的位置来进行压栈和弹栈操作。

#ifndef _LINKSTACK_H
#define _LINKSTACK_H#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef char Type;
typedef struct link{Type data; struct link *rear;  //存储下一个节点地址
}lstack;//创建栈
lstack *create_lstack();
//判空 空为0非空为1
int empty_lstack(lstack *l);
//求长度
int length_lstack(lstack *l);
//压栈
void push_lstack(lstack *l,Type data);
//弹栈
Type pop_lstack(lstack *l);
//取栈顶元素
Type get_lstack(lstack *l);
//初始化
void init_lstack(lstack *l);
//回收
void free_lstack(lstack **l);#endif

在创建结构体的时候，结构体名也是不能省略，因为我们在结构体里面需要使用结构体 *类型的指针来指向下一个节点；结构体成员就两个，一个是用来保存数据的变量data，另外一个是结构体指针，相当于链。

#include "linkstack.h"//创建栈
lstack *create_lstack()
{lstack *l = (lstack *)malloc(sizeof(lstack));if(NULL == l){perror("create lstack malloc");return NULL;}l->rear = NULL;return l;
}
//判空 空为0非空为1
int empty_lstack(lstack *l)
{if(NULL == l){puts("lstack is NULL");return -1;}if(l->rear){return 1;}else{puts("stack is empty");return 0;}
}
//求长度
int length_lstack(lstack *l)
{if(NULL == l){puts("lstack is NULL");return -1;}int n = 0;while(l->rear){n++;l = l->rear;}return n;
}
//压栈
void push_lstack(lstack *l,Type data)
{if(NULL == l){puts("lstack is NULL");return;}lstack *s = (lstack *)malloc(sizeof(lstack));s->data = data;s->rear = l->rear;l->rear = s;
}
//弹栈
Type pop_lstack(lstack *l)
{if(empty_lstack(l) == 1){lstack *s = l->rear;l->rear = s->rear;Type d = s->data;free(s);return d;}
}
//取栈顶元素
Type get_lstack(lstack *l)
{if(empty_lstack(l) == 1){return l->rear->data;}
}
//初始化
void init_lstack(lstack *l)
{if(NULL == l){puts("lstack is NULL");return;}while(l->rear){lstack *s = l->rear;l->rear = s->rear;free(s);}
}
//回收
void free_lstack(lstack **l)
{if(NULL == l){puts("lstack is NULL");return;}init_lstack(*l);free(*l);*l = NULL;
}

创建栈： lstack *create_lstack()

创建同样是在堆区开辟空间，开辟空间之后判断开辟是否成功，成功之后让里面的指针rear指向NULL，头节点不存数据，因此不需要给data赋值，最后返回这个开辟空间的地址。

判空： int empty_lstack(lstack *l)

既然我们操作的是头节点，因此判空只需要判断头节点的下一个是否为空就能知道栈是否为空，空栈函数返回0，非空函数返回1。

求长度：int length_lstack(lstack *l)

求长度其实就和遍历一样，使用一个循环来遍历这个栈，然后用一个变量来计数，最后返回这个计数的值即可。

压栈：void push_lstack(lstack *l,Type data)

压栈其实就和链表的头插一样，先创建节点，创建完成之后给data赋值，然后让新节点的rear指向头节点的下一个，最后让头节点的rear指向新节点即可。

弹栈：Type pop_lstack(lstack *l)

弹栈操作和压栈正好相反，我们先使用一个指针来接收要删除的节点，然后把原来头节点与这个节点之间的链断开，接着让头结点的rear指向要删除节点的下一个，最后将空间释放即可；在这里弹栈我们不止要把这个元素弹出来，我们还需要使用一个变量来接收弹出来的这个元素，让它作为弹栈函数的返回值。

获取栈顶元素：Type get_lstack(lstack *l)

获取栈顶元素也就是将头节点的下一个节点里面的data的值作为函数的返回值直接反出来即可。

初始化：void init_lstack(lstack *l)

链栈的初始化与链表是一样的，首先循环遍历，在每次循环时定义一个指针接收节点，将节点空间释放掉；将除了头节点以外的节点都释放掉，这就是链式栈的初始化。

回收：void free_lstack(lstack **l)

链式栈的回收函数传参同样是传二级指针，这里需要拿到链式栈头节点的指针地址，现将链式栈初始化，最后再把头节点空间释放掉，最后让指向头结点的指针指向NULL即可。

测试（主函数）

#include "linkstack.h"
int main(int agrc,char *agrv[])
{lstack *s = create_lstack();empty_lstack(s);puts("压栈，压入a");push_lstack(s,'a');puts("压栈，压入b");push_lstack(s,'b');puts("压栈，压入A");push_lstack(s,65);printf("此时链栈的长度为：%d\n",length_lstack(s));printf("取此时栈顶元素为：%c\n",get_lstack(s));puts("弹栈");pop_lstack(s);//puts("弹栈");//pop_lstack(s);printf("取此时栈顶元素为：%c\n",get_lstack(s));printf("此时链栈的长度为：%d\n",length_lstack(s));puts("初始化栈链");init_lstack(s);printf("此时链栈的长度为：%d\n",length_lstack(s));free_lstack(&s);printf("s=%p\n",s);return 0;
}