栈

栈是一种线性存储结构，但是只能从栈顶添加或者入栈push和移除或出栈pop数据。栈具有先进后出FILO或后进先出LIFO的特点。

栈是一种抽象的数据结构，可以用数组或者链表来实现栈。例如，[1,2,3,4,5] 使用栈来存储的示意图。

栈的应用

内存管理

在方法调用时，方法内的局部变量、方法返回地址等数据保存在一个叫栈的内存区域，这部分区域存储结构就是上面说的栈。比如Java方法调用时，方法体内的局部变量就保存在JVM栈中，每个方法对应栈中的一个节点，称为栈帧，当方法调用时入栈，调用结束时出栈，释放该部分内存。

表达式计算和语法解析

在表达式的计算中，我们经常会提到前缀表达式，中缀表达式还有后缀表达式，这些表达式的转换还有计算会用到栈。另外很多编程语言的编译器在解析源代码时也会用到栈来处理语法规则。

解决回溯问题

比如栈在深度优先搜索算法中的使用。

跟栈相关的题目，比较经典的有二叉树的迭代遍历，有效的括号，先从简单的开始。

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

主要思路是，遍历字符串，遇到左括弧就加入到栈中，遇到右括弧，则看看离它最近的左括弧是不是跟它匹配，最近的左括弧在栈顶，所以跟栈顶元素匹配，匹配上则出栈，否则匹配失败。

二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[2,1]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

二叉树的遍历最简单还是用递归的方式，但是我们也可以用栈来模拟递归的逻辑。