栈

栈是一种遵循后进先出（Last In First Out, LIFO）原则的数据结构。就像一摞盘子，你总是先拿最上面的盘子，最后放上去的盘子最先被拿走。在栈中，元素的添加和移除都发生在同一端，称为栈顶。

• push：将一个元素放到栈顶，相当于在盘子摞上放一个新盘子。
• pop：移除并返回栈顶元素，相当于拿走最上面的盘子。
• peek（或 top）：返回栈顶元素但不移除，相当于看一眼最上面的盘子而不动它。

• 浏览器后退：每次访问新页面，当前页面被 push 进栈；点击后退时，pop 出上一页面。
• 撤销操作：编辑器中的每一步操作被 push 进栈，撤销时 pop 出最近的操作并回退。
• 括号匹配：遍历表达式，遇到左括号 push，遇到右括号 pop 并检查是否匹配。
• 函数调用栈：程序调用函数时，将返回地址和局部变量 push 进栈；函数返回时 pop 出，恢复调用者状态。

栈可以用数组或链表实现。数组实现时，用一个变量记录栈顶索引，push 和 pop 只在数组尾部操作，简单高效。链表实现时，用头节点作为栈顶，push 和 pop 都在头部进行，无需移动大量元素。数组实现更节省空间（无需存储指针），但需要预先分配容量或动态扩容；链表实现灵活，但每个节点额外存储指针。