前言栈是数据结构中基础且核心的线性结构凭借后进先出LIFO的特性被广泛应用于函数调用、表达式求值、括号匹配等场景更是算法面试中的高频考点。本文结合工程实际用 C 语言实现一套动态顺序栈系统讲解初始化、入栈出栈、扩容销毁等关键操作同时梳理面试核心考点帮你从原理到代码彻底吃透栈结构。一、栈的基础认知栈Stack是一种遵循后进先出Last In First Out, LIFO原则的线性数据结构仅允许在栈顶Top一端进行插入和删除操作另一端为栈底Bottom。可以将栈类比为一叠盘子新增盘子只能放置在最上方入栈 push 取盘子只能从最上方拿走出栈 pop 无法直接操作中间或底部的盘子核心操作定义表格二、栈的结构体设计本文采用动态顺序栈实现通过结构体封装栈的核心状态data 动态数组指针用于存储栈元素top 栈顶指针初始值为 0 表示下一个可入栈的位置capacity 栈的最大容量初始值为 0 代表初始未分配存储空间三、栈的核心操作实现初始化栈创建空栈初始化栈顶指针与容量不预先分配数组空间。2. 判断栈是否为空栈空的判定条件为栈顶指针 top 等于 0 。3. 判断栈是否已满当 capacity 为 0 时表示无固定容量限制栈永远不满否则判断 top 是否达到容量上限。4. 入栈操作push将元素添加至栈顶若栈满或初始无容量则自动扩容容量按 2 倍递增。5. 出栈操作pop移除并返回栈顶元素若栈空则返回失败。6. 获取栈顶元素查看栈顶元素但不修改栈结构。7. 遍历栈从栈顶到栈底依次输出所有元素。8. 销毁栈释放动态数组内存重置栈顶指针与容量。四、入栈与出栈核心逻辑解析入栈流程检查栈是否已满若未满则继续执行若初始无容量或容量不足触发动态扩容初始容量 4后续 2 倍递增将元素存入 data[top] 然后 top 自增 1时间复杂度均摊 O(1)扩容为低频操作平均后仍为常数时间出栈流程检查栈是否为空若为空则返回失败top 自减 1指向原栈顶元素返回 data[top] 的值时间复杂度O(1)设计优势top0 直观表示下一个可入栈位置避免数组越界capacity0 初始状态标记配合动态扩容实现灵活存储自动扩容解决固定容量栈的空间限制问题更贴近工程实践五、完整测试代码运行输出示例六、栈的经典应用场景函数调用栈保存函数返回地址与局部变量实现函数嵌套调用括号匹配验证判断 (){}[] 等括号是否合法闭合表达式求值将中缀表达式转换为后缀表达式逆波兰表达式后计算浏览器前进后退用两个栈分别记录前进与后退的历史记录编辑器撤销功能用栈记录操作历史实现状态回滚深度优先搜索DFS用栈模拟递归实现图/树的遍历七、面试高频考点栈专题面试常问基础题栈和队列的区别是什么栈后进先出 LIFO只在栈顶操作队列先进先出 FIFO队尾入队、队头出队。顺序栈和链式栈优缺点对比顺序栈访问快、实现简单但容量固定、可能浪费空间链式栈动态扩容、无溢出风险但需要额外指针开销。入栈、出栈的时间复杂度为什么是 O(1)只操作栈顶指针不涉及数据移动与栈内元素个数无关。手撕算法高频题有效的括号LeetCode 20最小栈LeetCode 155用栈实现队列LeetCode 232柱状图中最大的矩形LeetCode 84逆波兰表达式求值LeetCode 150面试加分回答点动态顺序栈扩容策略初始 4每次翻倍均摊复杂度 O(1)。栈在操作系统中的应用函数调用栈、栈溢出、局部变量分配。递归本质系统自动维护了一个调用栈手动用栈可以改非递归。八、总结栈是后进先出LIFO的线性数据结构仅允许在栈顶操作本文实现的动态顺序栈通过 top0 与 capacity0 的初始设计兼顾简洁性与扩展性核心操作入栈、出栈、取栈顶均为常数时间复杂度遍历与销毁为线性时间复杂度动态扩容机制解决了固定容量栈的空间浪费与溢出问题更适合实际工程场景栈是笔试面试必考内容从基础原理到算法应用都需要熟练掌握是数据结构学习的核心基础九、结束语本文从原理到代码完整实现了动态顺序栈希望能帮助大家扎实掌握栈这一重要数据结构。如果对你有帮助欢迎点赞、收藏、转发支持一下。后续我会继续更新队列、链表、树等数据结构与算法内容干货持续输出我们下期见