通用链栈的两种实现方式（C语言）

一、通过业务结点构建关联

1、头文件linkstack.h

#include <stdio.h>

typedef struct Node
{
    struct Node* next;
}Node;

typedef struct StackNode  //业务结点
{
    Node node;
    void* data;
}StackNode;

typedef struct LinkStack
{
    int length;
    StackNode* top;
}LinkStack;

void InitStack(LinkStack*);  //初始化栈
int StackEmpty(LinkStack*);   //判断栈是否为空
int StackLength(LinkStack*);   //返回栈的大小
void GetTop(LinkStack*, void**);   //获取栈顶元素值
void PushStack(LinkStack*, void*);   //入栈
void PopStack(LinkStack*, void**);   //出栈
void ClearStack(LinkStack*);    //清空栈

2、相关操作函数linkstack.c

#include "linkstack2.h"
#include <stdlib.h>

void InitStack(LinkStack* st)
{
    st->length = 0;
    st->top = NULL;
}

int StackEmpty(LinkStack* st)
{
    if(st->length == 0)
        return 1;

    return 0;
}

int StackLength(LinkStack* st)
{
    return st->length;
}

void GetTop(LinkStack* st, void** e)
{
    if(st->length == 0)
    {
        printf("空栈！\n");
        return;
    }

    *e = st->top->data;

}

void PushStack(LinkStack* st, void* e)
{
    StackNode* pNew = (StackNode*)malloc(sizeof(StackNode));
    pNew->data = e;
    pNew->node.next = &st->top->node;
    st->top = pNew;
    st->length++;
}

void PopStack(LinkStack* st, void** e)
{
    StackNode* pDel = st->top;
    *e = pDel->data;
    st->top = (StackNode*)pDel->node.next;

    free(pDel);
    st->length--;
}

void ClearStack(LinkStack* st)
{
    if(st->length == 0)
    {
        printf("空栈！\n");
        return;
    }
    while(st->length)
    {
        void* tmp;
        PopStack(st, &tmp);
    }

}

3、主函数main.c

#include <stdio.h>
#include <stdlib.h>
#include "linkstack2.h"

typedef struct stu
{
    int id;
    int age;
}student;

int main()
{
    LinkStack st;
    InitStack(&st);

    student s[10];
    int i = 0;
    for(i = 0; i < sizeof(s) / sizeof(student); i++)
    {
        s[i].id = i;
        s[i].age = i + 20;
        PushStack(&st, &s[i]);
    }

    printf("当前栈的大小为：%d\n", st.length);

    for(i = 0; i < 5; i++)
    {
        student* tmp;
        GetTop(&st, (void**)&tmp);
        printf("当前栈顶元素的值为：id = %d, age = %d\n", tmp->id, tmp->age);
        PopStack(&st, (void**)&tmp);
        printf("当前出栈元素的值为：id = %d, age = %d\n", tmp->id, tmp->age);
        printf("\n");
    }

    printf("当前栈的大小为：%d\n", st.length);

    ClearStack(&st);
    printf("当前栈的大小为：%d\n", st.length);

    return 0;
}

二、通过在存放数据的结构体中加入结点建立关联

1、头文件linkstack2.h

#include <stdio.h>

typedef struct Node
{
    struct Node* next;
}Node;

typedef struct LinkStack
{
    int length;
    Node* top;  //栈顶指针，永远指向第一个数据结点
}LinkStack;


void InitStack(LinkStack*);
int StackEmpty(LinkStack*);
int StackLength(LinkStack*);
void GetTop(LinkStack*, Node**);
void PopStack(LinkStack*, Node**);
void PushStack(LinkStack*, Node*);
void ClearStack(LinkStack*);

2、相关操作函数linkstack2.c

#include "linkstack.h"

void InitStack(LinkStack* st)
{
    st->length = 0;
    st->top = NULL;
}

int StackEmpty(LinkStack* st)
{
    if(st->length == 0)
        return 1;

    return 0;
}

int StackLength(LinkStack* st)
{
    return st->length;
}

void GetTop(LinkStack* st, Node** e)
{
    if(st->length == 0)
    {
        printf("空栈！\n");
        return;
    }

    *e = st->top;
}

void PopStack(LinkStack* st, Node** e)
{
    if(st->length == 0)
    {
        printf("空栈！\n");
        return;
    }

    Node* pDel = st->top;
    *e = pDel;
    st->top = pDel->next;
    st->length--;
}

void PushStack(LinkStack* st, Node* e)
{
    Node* pNew = e;
    pNew->next = st->top;
    st->top = pNew;
    st->length++;
}

void ClearStack(LinkStack* st)
{
    Node* tmp;
    while(st->length)
    {
        PopStack(st, &tmp);
    }
}

3、主函数main.c

#include <stdio.h>
#include <stdlib.h>
#include "linkstack.h"

typedef struct stu
{
    Node P;
    int id;
    int age;
}Student;
int main()
{
    Student s[10];
    LinkStack st;

    InitStack(&st);
    int i = 0;
    for(i = 0; i < (sizeof(s) / sizeof(s[0])); i++)
    {
        s[i].id = i;
        s[i].age = i + 20;
    }

    for(i = 0; i < 10; i++)
    {
        PushStack(&st, &s[i].P);
    }

    for(i = 0; i < 5; i++)
    {
        Node* tmp;
        GetTop(&st, &tmp);
        Student* tmp1 = (Student*) tmp;
        printf("当前栈顶元素值为：id = %d, age = %d\n", tmp1->id, tmp1->age);

        PopStack(&st, &tmp);
        tmp1 = (Student*) tmp;
        printf("出栈元素值为：id = %d, age = %d\n", tmp1->id, tmp1->age);
        printf("\n");
    }

    printf("当前栈的大小为：%d\n", st.length);

    ClearStack(&st);
    printf("当前栈的大小为：%d\n", st.length);


    return 0;
}