一、前言栈是数据结构中最基础、最重要的线性结构之一遵循后进先出LIFO, Last In First Out的核心规则。栈的实现方式主要分为两种顺序栈和链式栈。顺序栈依托数组实现存在固定容量、扩容开销、空间浪费等问题而链式栈依托单链表实现可以动态申请内存无需提前开辟空间完美解决顺序栈的缺陷是工程中常用的栈实现方式。本文将结合完整可运行的链式栈代码从零梳理链式栈的原理、核心接口、逻辑细节及优缺点帮助大家彻底掌握链式栈。二、链式栈核心原理2.1 底层结构链式栈以单链表为底层载体为了简化入栈、出栈操作统一采用头插、头删的方式操作链表链表头部作为栈顶入栈、出栈仅需操作头节点时间复杂度为 O(1)链表尾部作为栈底永远不操作栈底节点额外维护 size 变量实时记录栈中有效元素个数快速判空、获取栈大小2.2 核心特性后进先出最后入栈的元素最先被弹出动态扩容无需预设容量元素入栈时动态开辟节点内存无空间浪费按需申请、释放内存相较于顺序栈空间利用率更高三、结构体定义LinkStack.h在讲解功能函数前先明确链式栈的结构体定义这是所有操作的基础#pragma once #include stdio.h #include stdlib.h #include assert.h #include stdbool.h // 栈存储的数据类型 typedef int STDataType; // 链式栈节点结构体 typedef struct LinkStackNode { STDataType data; // 节点存储数据 struct LinkStackNode* next; // 指向下一节点的指针 } LSNode; // 链式栈整体结构体 typedef struct LinkStack { LSNode* topHead; // 栈顶指针链表头节点 int size; // 栈内有效元素个数 } LinkStack;设计说明单独封装栈结构体而非直接使用链表头指针通过 size 变量规避遍历链表统计元素的 O(n) 开销极大提升效率。四、核心接口代码逐行解析以下为链式栈全部功能实现代码结合逻辑细节逐点解析覆盖初始化、销毁、入栈、出栈、取栈顶、判空等全部核心操作。4.1 栈初始化初始化空栈将栈顶指针置空、元素个数置0创建一个无元素的空栈。// 初始化链式栈s void LinkStackInit(LinkStack* s){ assert(s); // 断言防止传入空指针 s-topHead NULL; // 栈顶无节点置空 s-size 0; // 有效元素个数为0 }4.2 栈销毁链式栈节点均为动态内存必须手动释放避免内存泄漏。遍历所有节点逐个释放内存最后重置栈状态。// 销毁链式栈s void LinkStackDestroy(LinkStack* s) { assert(s); LSNode* cur s-topHead; // 遍历所有节点逐个释放 while (cur) { LSNode* next cur-next; // 提前保存下一节点防止断链 free(cur); cur next; } // 重置栈为空状态 s-topHead NULL; s-size 0; }关键细节必须提前保存 next 指针否则释放当前节点后无法找到下一节点造成内存泄漏。4.3 入栈操作Push将元素插入栈顶链表头插法是链式栈的核心操作时间复杂度 O(1)。// x入栈 void LinkStackPush(LinkStack* s, STDataType x) { assert(s); // 1. 申请新结点内存 LSNode* newNode (LSNode*)malloc(sizeof(LSNode)); if (NULL newNode) { // 内存申请失败容错 printf(LinkStackPush:申请节点失败); exit(-1); } newNode-data x; // 2. 头插新节点指向原栈顶 newNode-next s-topHead; // 3. 更新栈顶为新节点 s-topHead newNode; // 4. 元素个数1 s-size; }4.4 出栈操作Pop删除栈顶元素并返回该元素只能操作栈顶遵循后进先出规则。// 出栈并返回栈顶元素 STDataType LinkStackPop(LinkStack* s) { assert(s); assert(!LinkStackEmpty(s)); // 断言栈不为空防止空栈出栈报错 LSNode* delNode s-topHead; // 保存待删除的栈顶节点 STDataType topE delNode-data; // 记录栈顶元素值 s-topHead delNode-next; // 更新栈顶为下一节点 free(delNode); // 释放原栈顶节点内存 delNode NULL; // 野指针置空 s-size--; // 元素个数-1 return topE; }容错逻辑通过LinkStackEmpty判断栈是否为空杜绝空栈出栈的非法操作保证代码健壮性。4.5 获取栈顶元素仅读取栈顶数据不修改栈结构常用于栈元素比对、取值场景。// 获取栈顶元素 STDataType LinkStackTop(LinkStack* s) { assert(s); assert(!LinkStackEmpty(s)); return s-topHead-data; }4.6 辅助接口获取栈大小、判空依托维护的 size 变量直接返回结果无需遍历链表效率极高。// 获取栈中有效元素个数 int LinkStackSize(LinkStack* s) { assert(s); return s-size; } // 检测栈是否为空如果是空返回真否则返回假 bool LinkStackEmpty(LinkStack* s) { assert(s); return s-size 0; }五、链式栈优缺点总结5.1 优点无容量限制动态申请内存理论上仅受系统内存限制无需预设大小空间利用率高按需开辟、释放节点无顺序栈的预留空间浪费操作效率稳定入栈、出栈、取栈顶均为 O(1) 时间复杂度无扩容开销规避顺序栈扩容拷贝数据的性能损耗5.2 缺点内存碎片化频繁申请、释放小块节点内存容易产生内存碎片访问效率略低链式结构不支持随机访问只能遍历缓存命中率低于顺序栈存在指针开销每个节点需额外存储 next 指针占用少量额外内存六、链式栈与顺序栈对比特性顺序栈链式栈底层结构数组单链表容量限制固定容量需手动扩容动态扩容无固定限制空间利用率低存在预留空间浪费高按需分配内存访问速度快支持随机访问缓存友好较慢仅支持顺序访问适用场景元素数量波动小、追求访问速度元素数量波动大、避免空间浪费七、常见应用场景括号匹配校验算法经典题型利用栈的后进先出特性匹配左右括号函数调用栈操作系统依托栈维护函数调用层级、局部变量表达式求值、逆波兰表达式栈实现中缀、后缀表达式转换与计算浏览器后退、编辑器撤销操作通过栈记录操作历史实现回退功能八、总结链式栈是栈结构的动态实现方案核心依托单链表头插头删实现高效的入栈出栈操作完美解决了顺序栈的容量和空间浪费问题。在实际开发中若数据量不确定、波动较大优先选择链式栈若数据量稳定、追求极致访问速度则选择顺序栈。掌握链式栈的核心不仅是理解线性结构的延伸更是后续学习二叉树、图、深度优先搜索DFS等算法的基础。