栈(Stack)

定义

栈是一种遵循后进先出（LIFO，Last In First Out）原则的线性数据结构。只能在一端（栈顶）进行插入（压栈 push）和删除（弹栈 pop）操作。

工作方式

可以把栈想象成一摞盘子，最后放上去的盘子最先被取走。栈通常用数组或链表实现：数组实现维护一个栈顶下标，链表实现在头部增删。常见操作还包括 peek（查看栈顶而不弹出）和 isEmpty（判空）。函数调用时系统用调用栈保存返回地址与局部变量，递归本质上就是栈的应用。

复杂度

• 压栈 push：O(1)
• 弹栈 pop：O(1)
• 查看栈顶 peek：O(1)
• 空间复杂度：O(n)

应用场景

• 函数调用与递归的调用栈
• 表达式求值与括号匹配
• 浏览器前进后退、编辑器撤销
• 深度优先搜索的迭代实现