堆栈（Stack）知识点汇总
编程小白的完全指南 – 通俗易懂的堆栈数据结构详解
堆栈可视化
什么是堆栈？
堆栈是一种后进先出（LIFO）的数据结构。想象一摞盘子：
生活类比：盘子架子
🍽️ 你洗干净的盘子会放在一摞盘子的最上面（入栈）。
🍽️ 当你要用一个盘子时，会从最上面取走（出栈）。
🍽️ 你无法直接取走中间或底部的盘子，只能操作最顶部的那个。
在编程中，堆栈用于存储数据，有两个关键操作：
- 入栈(Push)：把新元素放在栈顶
- 出栈(Pop)：移除栈顶元素
堆栈的核心操作
| 操作名称 | 作用 | 类比解释 |
|---|---|---|
| Push(入栈) | 向栈顶添加一个新元素 | 往一摞盘子上放一个新盘子 |
| Pop(出栈) | 移除栈顶元素并返回它 | 从一摞盘子顶部取走一个盘子 |
| Peek/Top(查看栈顶) | 查看栈顶元素但不移除 | 看一眼最上面的盘子，但不取走 |
| isEmpty(判空) | 检查栈是否为空 | 检查是否还有盘子 |
| Size(大小) | 返回栈中元素数量 | 数一摞盘子有多少个 |
为什么要使用堆栈？
1. 函数调用栈
当程序调用函数时，系统使用堆栈：
- 每次调用函数，将其”入栈”
- 函数执行完毕，将其”出栈”
- 这样就能追踪函数的调用顺序
2. 撤销(Undo)功能
编辑器的撤销功能：
- 每次操作都被”入栈”
- 撤销时”出栈”最近的操作
3. 括号匹配检查
检查代码中的括号是否匹配：
- 遇到左括号(如 ‘(‘、'[‘)时入栈
- 遇到右括号时出栈并检查是否匹配
4. 浏览器历史记录
浏览器的后退按钮：
- 访问新页面时”入栈”
- 点击后退时”出栈”返回到前一个页面
堆栈的实现方式
1. 基于数组实现
使用数组存储元素，并维护一个栈顶指针
优点：实现简单，访问速度快
缺点：大小固定（可以扩容但效率低）
2. 基于链表实现
使用链表存储元素，只需操作头节点
优点：大小灵活，动态增长
缺点：需要额外内存存储指针
时间复杂度分析
入栈(Push)
O(1)
常数时间完成
出栈(Pop)
O(1)
常数时间完成
查看栈顶(Peek)
O(1)
常数时间完成
总结：堆栈的所有核心操作都非常高效！