堆栈：后进先出，编程必备工具

咱们每天都能遇到类似堆栈的场景——比如厨房里叠放的盘子，总是最后放上去的会被最先拿走。这种「后进先出」的特性，正是堆栈（Stack）这种数据结构的核心。作为程序员必备的基础工具，它就像编程世界里的「临时记事本」，默默记录着程序运行的关键信息。

什么是堆栈？

想象你在玩叠积木游戏，每次只能把新积木放在最顶端，取走时也必须从最上面开始拿。堆栈就是遵循这种规则的数据容器，专业术语叫做LIFO（Last In First Out）结构。它有两大招牌动作：push（把数据放上栈顶）和pop（移除栈顶数据）。

堆栈的特征标签

• 只能从同一端（栈顶）存取数据
• 每次操作都直接影响栈顶元素
• 不需要知道中间元素就能完成基本操作

创建堆栈的两种方式

就像盖房子可以用砖块或木材，创建堆栈也有经典方法：

用数组当「集装箱」

这个方法适合已知最大容量的场景。比如我们要做个能存10个数字的堆栈：

• 定义固定长度的数组
• 设置指针跟踪栈顶位置
• 初始时栈顶指针指向-1表示空栈

用链表当「珍珠项链」

需要动态调整大小时，链表实现更灵活。每个节点包含：

• 数据存储区
• 指向下一个节点的指针
• 通过修改指针实现元素的增删

堆栈的五大基本操作

就像智能手机的home键，堆栈的操作按钮也很简洁：

• Push：像在超市排队，新来的顾客站到队伍末尾
• Pop：就像取走最上面的一本书，取完后下一本自动成为栈顶
• Peek/Top：悄悄看一眼栈顶元素但不拿走
• isEmpty：检查储物箱是否已空
• isFull（数组实现特有）：确认储物箱是否塞满

操作时间复杂度对比

堆栈在现实世界的投影

你可能没注意到，这些常见功能背后都有堆栈的身影：

• 浏览器后退按钮：记录访问历史的堆栈
• 文档撤销功能：操作记录的逆向回退
• 递归函数调用：维护方法执行环境的调用栈
• 算术表达式计算：处理括号匹配的利器

使用堆栈的注意事项

• 数组实现要预防栈溢出——就像往装满水的杯子继续倒水
• 操作空栈时记得做空栈检查，避免出现「从空盘子堆取盘子」的尴尬
• 链表实现要注意内存管理，特别是pop操作后的空间释放

经典教材推荐

想深入了解堆栈的应用，《算法导论》（Cormen著）第七章有精彩解析，书中用面包店托盘比喻堆栈的操作过程，读起来特别有画面感。

当我们在IDE里调试递归函数时，观察调用栈的变化就像在看一场精心编排的舞台剧。每个方法的入场退场都严格遵循着堆栈的规则，这种井然有序的美感，正是计算机科学迷人之处。