如何将7.4 CC++链表栈改写为长尾？

本文共计958个文字，预计阅读时间需要4分钟。

关于顺序栈和链表栈的内存使用，链表栈更为灵活。链表栈的内存空间是动态分配的，不需要在创建时确定大小，而是根据需要逐个分配节点。当需要压入新元素时，链表栈会根据当前需求动态分配内存。

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

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

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