小编点评

**链表栈** 链表栈是一种动态分配的栈，其内存空间根据需要逐个分配和释放，以提高效率。 **主要特点：** * 使用 `malloc` 和 `free` 函数动态分配和释放节点内存空间。 * 在入栈和出栈操作中，通过将头指针强转来实现高效的节点插入和删除。 * 链表栈通常比顺序栈更省空间，因为它只需记录链表头指针即可实现入栈和出栈。 **实现：** ```c 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 StackNode *pFirst = ls->header.next; ls->header.next = pFirst->next; ls->size--; } // 获得栈顶元素 struct Student* TopLinkStack(LinkStack stack) { if (NULL == stack) { return NULL; } // 如果栈为空，返回 NULL if (ls->size == 0) { return NULL; } return (struct Student *)ls->header.next; } // 获得大小 int SizeLinkStack(LinkStack stack) { if (NULL == stack) { return -1; } return ls->size; } // 销毁栈 void DestroyLinkStack(LinkStack stack) { if (NULL != stack) { free(stack); } stack = NULL; } ``` **示例：** ```c // 创建链表栈 LinkStack stack = InitLinkStack(); // 将数据加入栈中 PushLinkStack(stack, &stu1); PushLinkStack(stack, &stu2); PushLinkStack(stack, &stu3); // 循环输出栈顶元素 while (SizeLinkStack(stack) > 0) { struct Student *ptr = TopLinkStack(stack); printf("Uid: %d --> Name: %s \\", ptr->uid, ptr->name); printf("当前栈大小: %d \\", SizeLinkStack(stack)); PopLinkStack(stack); } // 销毁栈 DestroyLinkStack(stack); ``` **输出：** ``` Uid: 1001 --> Name: admin 当前栈大小: 3 Uid: 1002 --> Name: guest 当前栈大小: 3 Uid: 1003 --> Name: lyshark 当前栈大小: 3 ```

正文

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

在实现上，链表栈通过使用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;
}

本文作者： 王瑞
本文链接： https://www.lyshark.com/post/a8502db9.html
版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！