行到水穷处，坐看栈起时——动态内存的链式之美

引言在数据结构的浩瀚海洋中“栈”Stack作为一种后进先出LIFO, Last In First Out的线性表其重要性不言而喻。此前我们深入探讨过顺序栈的实现与优劣也剖析过单链表、双向链表以及循环链表的 intricacies复杂性。今天我们将这两大基石结合聚焦于一种既具备栈的逻辑特性又拥有链表动态内存优势的数据结构——链栈Linked Stack。一、链栈的认识1.1什么是链栈链栈本质上是一个只允许在表头进行插入和删除的单链表。我们用一个头指针top来标识栈顶(单链表的头节点)入栈push等价于在链表头部插入一个新节点头插出栈pop等价于删除头节点头删。由于操作仅限于头部时间复杂度均为 O(1)。1.2节点与管理结构体的设计指针的艺术链栈节点的设计与链表无异结构体中包括数据域存放数据指针域存放下一个节点的地址//每一个节点的结构体 typedef struct StackNode { ElemType data; //数据域 struct StackNode* next; //指针域 }StackNode, * PstackNode;管理链栈的结构体为了便于管理我们定义一个包含“栈顶指针”和“当前元素个数”的结构体这比单纯使用一个全局头指针更具封装性。​ //管理每一个节点的结构体 typedef struct LinkStack { StackNode* top; //栈顶指针管理链表 (保存链表的头部) size_t cursize; //当前容量 }LinkStack, * PLinkStack; ​补充结构体指针的重命名①先定义结构体再为它的指针类型起别名//先定义一个结构体 struct Student { int id; char name[10]; }; //该结构体的指针为struct Student* //使用重命名的关键字typedef 给指针重命名 typedef struct Student* PStudent; PStudent ps; //使用时可直接用PStudent 代替 struct Student*②在定义结构体时直接重命名最常用//直接给结构体指针重命名 typedef struct Student { int id; char name[10]; } * PStudent; //注意这里的 *直接为指针类型起别名 //或者同时为结构体和指针起别名 typedef struct Student { int id; char name[10]; } Student, * PStudent; //使用 Student s; // 等价于 struct Student s; PStudent ps; // 等价于 struct Student* ps;③匿名结构体的指针重命名typedef struct { int x; int y; } *PointPtr; PointPtr p; // 直接使用1.3链栈示意图这里简单显示了链栈的样子以及出栈及入栈的情形帮助读者理解。二、核心函数的实现C语言购买节点初始化获取元素个数判空入栈打印出栈并获取栈顶元素获取栈顶元素清空销毁2.1购买节点、初始化PstackNode BuyNode(ElemType val) //购买节点void InitLinkStack(PLinkStack ps) //初始化购买节点在进行数据入栈时肯定要重新申请一个节点空间将数据存入节点在将节点进行插入。所以我们将这一重复的步骤包装成函数便于使用初始化对链栈进行初始化//1.购买新节点 PstackNode BuyNode(ElemType val) { PstackNode p (PstackNode)malloc(sizeof(StackNode)); //申请一个节点大小的空间 if (p NULL)return NULL; p-data val; //存入数据 p-next NULL; //先置空指针 return p; } //2.初始化(带头节点) void InitLinkStack(PLinkStack ps) { assert(ps ! NULL); PstackNode p BuyNode(0); //头节点 if (p NULL)return; ps-cursize 0; //链栈容量置为0 ps-top p; //栈顶指针始终指向头节点的地址 }2.2获取元素个数、判空size_t Get_Size(const PLinkStack ps) //获取元素个数bool IsEmpty(const PLinkStack ps) //判空获取元素个数直接返回链栈中的有效元素个数即可return ps-cursize.判空链栈的元素个数为0即为空return ps-cursize 0​ //1.获取元素的个数 size_t Get_Size(const PLinkStack ps) { assert(ps ! NULL); return ps-cursize; } //2.判空 bool IsEmpty(const PLinkStack ps) { assert(ps ! NULL); return ps-cursize 0; } ​2.3入栈、打印bool Push(PLinkStack ps, ElemType val) //入栈void PrintStack(const PLinkStack ps) //打印入栈 链栈的入栈操作等同于单链表的头插法。这是最高效的操作无需遍历链表头插法这里便不过多赘述了打印重新定义一个节点指针从第一个有效节点开始循环遍历每一个节点p p-next输出其中的数据//1.入栈 bool Push(PLinkStack ps, ElemType val) { assert(ps ! NULL); PstackNode p BuyNode(val); //购买新节点 if (p NULL)return false; p-next ps-top-next; //头插让p的指针域保存头节点的指针域 // NULL或者是原第一个有效节点的地址 ps-top-next p; //让头节点的指针域指向p连接完成 ps-cursize; //容量加一 return true; } //2.打印 void PrintStack(const PLinkStack ps) { assert(ps ! NULL); for (PstackNode p ps-top-next; p ! NULL; p p-next) { //p从第一个有效节点开始 printf(%hhd , p-data); //循环终止条件p!NULL } printf(\n); }函数测试2.4出栈并获取栈顶元素、获取栈顶元素bool Pop(PLinkStack ps, ElemType* pval) //出栈并获取栈顶元素bool GetTop(PLinkStack ps, ElemType* pval) //获取栈顶元素出栈并获取栈顶元素传入一个数据类型的指针ElemType * pval用来接收栈顶元素之后释放节点空间即可不要忘记将链栈的容量进行减一。获取栈顶元素直接用元素指针接收值即可//1.出栈并获取栈顶元素 bool Pop(PLinkStack ps, ElemType* pval) { assert(ps ! NULL); if (IsEmpty(ps))return false; //判空若为空无需出栈 PstackNode p ps-top-next; //先用p保存要出栈的节点的地址 ps-top-next p-next; //头节点连接后续节点 *pval p-data; //解应用指针用来接收栈顶元素 free(p); p NULL; ps-cursize--; //容量减一 return true; } //2.获取栈顶元素 bool GetTop(PLinkStack ps, ElemType* pval) { assert(ps ! NULL); if (IsEmpty(ps))return false; //判空 *pval ps-top-next-data; //直接接收值即可 return true; }函数测试2.5清空、销毁void ClearStack(PLinkStack ps) //清空void DestroyStack(PLinkStack ps) //销毁清空循环释放所有的有效节点即可销毁释放所有节点包括头节点//1.清空 void ClearStack(PLinkStack ps) { assert(ps ! NULL); if (IsEmpty(ps))return; PstackNode p ps-top-next; //p从第一个有效节点开始(头删) while (p ! NULL) { //p!NULL 则一直删除 ps-top-next p-next; //先连接后续节点 free(p); p ps-top-next; //重置p为第一个有效节点 } ps-cursize 0; //容量置0 } //2.销毁 void DestroyStack(PLinkStack ps) { assert(ps ! NULL); ClearStack(ps); //调用清空函数释放所有的有效节点 free(ps-top); //释放头节点 ps-top NULL; ps-cursize 0; //容量置空0 }三、结语链栈之韵代码留痕当最后一个节点在内存中安然归位当出栈的指针划过逻辑的轨迹我们与链栈的对话暂告段落。从结构体指针的精巧设计到入栈出栈的代码实现从 malloc 的节点诞生到 free 的资源轮回——每个细节都藏着编程的韵律秩序与自由的平衡抽象与具象的交融。链栈如诗以指针为笔、内存为纸书写“后进先出”的优雅代码似舞用函数作步、逻辑为韵演绎数据结构的生命力。这些冰冷的语法实则是人类智慧对“存储与运算”最浪漫的诠释。愿这篇博客不仅是技术的书签更是一扇窗让你看见代码背后的诗意理解数据结构是思维的体操、逻辑的艺术。未来面对链栈或其他挑战时愿你带着敬畏与热爱在0与1的宇宙里继续书写属于自己的“指针之诗”