栈 (Stack)

定义与概念

栈是一种后进先出（LIFO）的线性数据结构，只允许在栈顶进行插入和删除操作。

核心特点

• LIFO原则：最后进入的元素最先出栈
• 单端操作：所有操作都在栈顶进行
• 递归支持：天然适合递归算法实现
• 有限访问：只能访问栈顶元素

主要类型

• 数组实现：基于数组的静态栈
• 链表实现：基于链表的动态栈

基本操作复杂度

操作	时间复杂度	空间复杂度
入栈	O(1)	O(1)
出栈	O(1)	O(1)
访问栈顶	O(1)	O(1)
搜索	O(n)	O(1)

应用场景

• 函数调用栈
• 表达式求值
• 括号匹配检查
• 浏览器前进后退
• 撤销操作功能