C语言数据结构篇——栈的链式存储

 作者名：Demo不是emo 

主页面链接：主页传送门创作初心：对于计算机的学习者来说，初期的学习无疑是最迷茫和难以坚持的，中后期主要是经验和能力的提高，我也刚接触计算机1年，也在不断的探索，在CSDN写博客主要是为了分享自己的学习历程，学习方法，总结的经验等等，希望能帮助到大家座右铭：不要让时代的悲哀成为你的悲哀专研方向：网络安全，数据结构

每日emo：我喜欢的人，身上有光，光而不耀，与光同尘

    

目录

初识栈

栈的链式存储的头结点和数据节点的定义

栈的创建 

栈的各种操作 

判断栈为空

获取栈顶元素 

弹出栈顶元素 

压栈 （入栈）

栈的销毁 

栈中元素的输出 

完整代码 

初识栈

在上一节我们讲了栈的顺序存储的实现，跟顺序表基本是一个道理，这节我们来讲一下栈的链式存储。栈的链式存储，其实本质还是链表，不过是多了一些栈特有的限制（栈的特有限制和理解大家可以查看我的上一篇博客，点此链接可以直接进入：C语言数据结构篇——栈的顺序存储_Grande joie的博客-CSDN博客）。所以，有一定的链表基础，理解好栈的特点，那么实现栈的链式存储就不是很难了，下面我给大家分享一下我理解的栈的链式存储，希望对你能有所帮助。

栈的链式存储的头结点和数据节点的定义

栈链式存储的头结点和数据节点定义方法和链表的头结点以及数据节点的定义方法是一样的。头结点用于保存整个栈顶的信息，其中包括两个元素，一个是整个栈的大小，另一个就是指向第一个数据节点的指针，这样就可以通过头结点访问整个栈的同时记录整个栈的大小，如下，一个头结点就定义好了；数据节点的结构体就更不用说了，同样分为数据域和指针域，指针域保存的指针用来指向下一个数据节点（当然，这只是我自己的一种写法，并不唯一）

#include
#include
#include//下方获取随机数的time需要的工具箱
#define INFINITY 99999
typedef struct node//数据节点结构体
{
    int val;//数据
    struct node* next;//指针
}pnode;
typedef struct seqstack//头结点结构体
{
    int size;//记录栈的大小
    pnode* top;//指向栈顶元素
}stack;//别名方便使用

栈的创建 

如上，头结点和数据节点就定义好了，接下来就是创建一个初始化的栈并返回创建好的，直接上代码：

stack*  initstack()//创建栈
{

    stack* istack=(stack*)malloc(sizeof(stack));//为创建的头结点分配空间
    if(istack!=NULL)//创建失败
    {
        istack->top=NULL;
        istack->size=0;
    }
    return istack;//返回创建好的头结点的地址
}

栈的各种操作 

栈的定义，创建都已经完成，下面就是进行栈的各种操作：

判断栈为空

这就是我用头结点的写法实现栈的原因之一，栈的头结点记录栈的大小，而栈的大小为0或者头结点中本来应该指向第一数据节点的指针指向了空时，栈就为空了，是不是简单了许多，具体代码如下：

int isempty(stack* istack)//判断栈为空
{
    if(istack->top==NULL)
    {
        return 1;//栈为空
    }
    return 0;//栈不为空
}

获取栈顶元素 

因为我们头结点中有指向栈的第一个数据节点，所以我们只需要简单的判断一下栈是否为空之后，不为空的话将栈的第一个数据节点结构体的数据域返回即可， 需要注意的是当链表为空返回时并不能返回常见的整型数字，因为有可能会跟第一个数据节点的数据域重合，出现不必要的错误。具体的代码就是下面这样了啦。

int seqstack_top(stack* istack)//获取栈顶元素
{
    if(isempty(istack)==0)//
    {
        return istack->top->val;
    }
    return INFINITY;//返回无穷大，不能返回-1，有可能栈的顶端元素就是-1
}

弹出栈顶元素 

 弹出栈顶元素也称为出栈，很多人会将它和获取栈顶元素混淆，其实他们最大的差别就是获取栈的元素并不会该变栈，而弹出栈的元素就会（细品）

int seqstack_pop(stack* istack)//弹出栈顶元素
{
    if(isempty(istack)==0)//栈不为空
    {
        int account=istack->top->val;获取栈顶元素
        istack->top=istack->top->next;头结点的指针指向第二个数据节点
        return account;
    }
    return INFINITY;//同理，不常用的数字即可
}

压栈 （入栈）

有出栈，自然也有入栈，入栈相比于出栈来说更复杂一点，但其实和链表的头插基本是一样的操作，不同的是头插后头结点的变化，具体的看下面的代码就可以了； 

void seqstack_push(stack* istack,int x)//压栈(入栈)
{
   pnode* temp;要入栈的数据节点
   temp=(pnode*)malloc(sizeof(pnode));//为数据节点分配内存
   temp->val=x;//填充数据域
   temp->next=istack->top;//入栈的数据节点的指针域指向第一个数据节点
   istack->top=temp;//头结点的指针指向入栈的数据节点
   istack->size++;//记录栈的大小
   return;
}

栈的销毁 

 无论是栈的头结点或者是数据节点，他们的内存都是分配来的，所以销毁栈只需要释放他们内存就好了，这里直接看代码就好了

void seqstack_destory(stack* istack)//销毁栈
{
    if(isempty(istack)==0)
    {
        free(istack);释放了头结点的就无法找到数据节点，所以销毁头结点即可
    }
}

栈中元素的输出 

 因为栈定义之后可能面临多次的调用和打印输出，所以我们也可以封装一个遍历打印栈的函数方便后续使用，具体代码如下：

void seqstack_print(stack* istack)
{
    pnode* temp=istack->top;用来遍历数据节点
    for(int i=1;isize;i++)
    {
        printf("%d ",temp->val);
        temp=temp->next;
        if(i%5==0)//这步只是为了美观
        {
            printf("\n");
        }
    }
    printf("\n");
}

完整代码 

栈的基本操作也差不多完成了，我们用这些封装好的函数来写一个完整的程序吧，这里的注释可能就不是这么明白了，建议从前面看一下。代码如下：

#include
#include
#include
#define INFINITY 99999
typedef struct node
{
    int val;//数据
    struct node* next;//指针
}pnode;
typedef struct seqstack
{
    int size;//记录栈的大小
    pnode* top;//指向栈顶元素
}stack;
stack*  initstack()//创建栈
{

    stack* istack=(stack*)malloc(sizeof(stack));
    if(istack!=NULL)
    {
        istack->top=NULL;
        istack->size=0;
    }
    return istack;
}
int isempty(stack* istack)//判断栈为空
{
    if(istack->top==NULL)
    {
        return 1;//栈为空
    }
    return 0;//栈不为空
}
int seqstack_top(stack* istack)//获取栈顶元素
{
    if(isempty(istack)==0)//
    {
        return istack->top->val;
    }
    return INFINITY;//返回无穷大，不能返回-1，有可能栈的顶端元素就是-1
}
int seqstack_pop(stack* istack)//弹出栈顶元素
{
    if(isempty(istack)==0)//栈不为空
    {
        int account=istack->top->val;
        istack->top=istack->top->next;
        return account;
    }
    return INFINITY;
}
void seqstack_push(stack* istack,int x)//压栈(入栈)
{
   pnode* temp;
   temp=(pnode*)malloc(sizeof(pnode));
   temp->val=x;
   temp->next=istack->top;
   istack->top=temp;
   istack->size++;
   return;
}
void seqstack_destory(stack* istack)//销毁栈
{
    if(isempty(istack)==0)
    {
        free(istack);
    }
}
void seqstack_print(stack* istack)
{
    pnode* temp=istack->top;
    for(int i=1;isize;i++)
    {
        printf("%d ",temp->val);
        temp=temp->next;
        if(i%5==0)
        {
            printf("\n");
        }
    }
    printf("\n");
}
int main()
{
    srand((unsigned)time(0));//以时间为种子获得随机数
    stack* istack=initstack();
    printf("请输入初始栈的容量\n");
    int m;
    scanf("%d",&m);
    for(int i=0;i