7.4 C/C++ 实现链表栈

相对于顺序栈，链表栈的内存使用更加灵活，因为链表栈的内存空间是通过动态分配获得的，它不需要在创建时确定其大小，而是根据需要逐个分配节点。当需要压入一个新的元素时，只需要分配一个新的节点，并将其插入到链表的头部；当需要弹出栈顶元素时，只需要删除链表头部的节点，并释放其所占用的内存空间即可。由于链表栈的空间利用率更高，因此在实际应用中，链表栈通常比顺序栈更受欢迎。

在实现上，链表栈通过使用malloc函数动态开辟节点内存空间来实现入栈操作，在释放时使用free函数释放节点内存空间来实现出栈操作，这使得链表栈相对于顺序栈更加节约存储空间，也更加容易实现。

读者需自行创建头文件linkstack.h并拷贝如下链表栈代码实现；

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct StackNode
{
    struct StackNode *next;
};
struct LStack
{
    struct StackNode header;
    int size;
};

typedef void* LinkStack;

// 初始化
LinkStack InitLinkStack()
{
    struct LStack *stack = malloc(sizeof(struct LStack));
    if (NULL == stack)
    {
        return NULL;
    }

    stack->header.next = NULL;
    stack->size = 0;
    return stack;
}

// 入栈
void PushLinkStack(LinkStack stack, void *data)
{
    if (NULL == stack || NULL == data)
    {
        return;
    }

    // 先将头指针进行强转
    struct LStack *ls = (struct LStack *)stack;
    
    // 把节点进行强转
    struct StackNode *node = (struct StackNode *)data;

    node->next = ls->header.next;
    ls->header.next = node;
    ++(ls->size);
}

// 出栈
void PopLinkStack(LinkStack stack)
{
    if (NULL == stack)
    {
        return;
    }

    struct LStack *ls = (struct LStack *)stack;
    if (ls->size == 0)
    {
        return;
    }

    // 缓存第一个节点
    struct StackNode *pFirst = ls->header.next;
    ls->header.next = pFirst->next;
    ls->size--;
}

// 获得栈顶元素
void* TopLinkStack(LinkStack stack)
{
    if (NULL == stack)
    {
        return NULL;
    }

    struct LStack *ls = (struct LStack *)stack;
    if (ls->size == 0)
    {
        return NULL;
    }

    return ls->header.next;
}

// 获得大小
int SizeLinkStack(LinkStack stack)
{
    if (NULL == stack)
    {
        return -1;
    }
    struct LStack *ls = (struct LStack *)stack;
    return ls->size;
}

// 销毁栈
void DestroyLinkStack(LinkStack stack)
{
    if (NULL != stack)
    {
        free(stack);
    }
    stack = NULL;
    return;
}

在主函数中使用也很容易，首先同样定义一个Student结构体，然后通过InitLinkStack函数初始化一个链表栈，接着调用PushLinkStack函数向该栈中插入数据，最后通过循环的方式输出该栈中的元素，当输出结束后调用DestroyLinkStack函数对栈进行销毁释放内存。

#include "linkstack.h"

struct Student
{
    int uid;
    char name[64];
};

int main(int argc, char *argv[])
{
    // 初始化栈,默认分配空间为1024
    LinkStack stack = InitLinkStack();

    // 穿件一些测试数据
    struct Student stu1 = { 1001, "admin" };
    struct Student stu2 = { 1002, "guest" };
    struct Student stu3 = { 1003, "lyshark" };

    // 将输入加入到栈中
    PushLinkStack(stack, &stu1);
    PushLinkStack(stack, &stu2);
    PushLinkStack(stack, &stu3);

    // 循环输出栈顶元素
    while (SizeLinkStack(stack) > 0)
    {
        // 获得栈顶元素
        struct Student *ptr = (struct Student *)TopLinkStack(stack);
        printf("Uid: %d --> Name: %s \n", ptr->uid, ptr->name);
        printf("当前栈大小: %d \n", SizeLinkStack(stack));
        PopLinkStack(stack);
    }

    // 销毁栈
    DestroyLinkStack(stack);
    stack = NULL;

    system("pause");
    return 0;
}