栈是后进先出的数据结构，Java中推荐使用Deque接口的ArrayDeque实现，不推荐使用Stack类；常用操作包括push、pop、peek、isEmpty等，广泛应用于括号匹配、表达式求值、DFS等问题。
栈，简单来说，就是一种后进先出（LIFO，Last In First Out）的数据结构。想象一下叠盘子，最后放上去的盘子总是最先被拿走。那么，在Java中，我们如何用代码来实现这个“叠盘子”的过程呢？
解决方案：
Java中实现栈，主要有两种方式：一种是使用Java集合框架提供的
java.util.Stack类（虽然官方不推荐使用，因为它继承自
Vector，而
Vector在多线程环境下效率较低），另一种是使用
java.util.Deque接口及其实现类，例如
ArrayDeque或
LinkedList。后者通常被认为是更现代和高效的选择。
下面分别给出两种实现方式的代码示例：
立即学习“Java免费学习笔记（深入）”；
1. 使用 java.util.Stack
(不推荐):
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack stack = new Stack<>();
// 入栈
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("栈顶元素: " + stack.peek()); // 输出: 30
// 出栈
System.out.println("出栈元素: " + stack.pop()); // 输出: 30
System.out.println("出栈元素: " + stack.pop()); // 输出: 20
System.out.println("栈是否为空: " + stack.isEmpty()); // 输出: false
}
} 2. 使用 java.util.Deque
(推荐):
import java.util.Deque;
import java.util.ArrayDeque;
public class DequeStackExample {
public static void main(String[] args) {
Deque stack = new ArrayDeque<>();
// 入栈 (相当于 push)
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("栈顶元素: " + stack.peek()); // 输出: 30
// 出栈 (相当于 pop)
System.out.println("出栈元素: " + stack.pop()); // 输出: 30
System.out.println("出栈元素: " + stack.pop()); // 输出: 20
System.out.println("栈是否为空: " + stack.isEmpty()); // 输出: false
}
} ArrayDeque是一个基于数组实现的双端队列，在作为栈使用时，性能通常优于
LinkedList。
栈溢出（Stack Overflow）是什么，如何避免？
栈溢出通常发生在递归调用过深，导致栈空间耗尽时。每个方法调用都会在栈上分配一块空间来存储局部变量、参数和返回地址。如果递归调用没有终止条件，或者终止条件不正确，就会导致栈空间不断增长，最终溢出。
避免栈溢出的方法主要有：
- 优化递归算法： 检查递归算法的终止条件是否正确，确保递归能够正常结束。尽量使用迭代代替递归，尤其是在处理大数据量时。
-
增加栈空间： 在某些情况下，可以通过JVM参数
-Xss
来增加栈空间的大小。但这并不是一个根本的解决方案，只能暂时缓解问题。 - 尾递归优化： 某些编译器可以对尾递归进行优化，将其转换为迭代执行，从而避免栈溢出。但Java编译器通常不进行尾递归优化。
除了
push和
pop，栈还有哪些常用操作？
除了基本的
push（入栈）和
pop（出栈）操作外，栈还有以下常用操作：
-
peek()
： 查看栈顶元素，但不移除它。就像只是看看最上面的盘子是什么，并不拿走它。 -
isEmpty()
： 检查栈是否为空。 -
size()
： 返回栈中元素的个数。 -
search(Object o)
： （java.util.Stack
特有）查找元素在栈中的位置，返回距离栈顶的距离。注意，这个方法在Deque
中没有直接对应的实现。如果使用Deque
，需要自己实现类似的功能。
如何使用栈解决实际问题？
栈在很多算法和数据结构问题中都有着重要的应用。以下是一些常见的例子：
- 括号匹配： 检查字符串中的括号是否正确匹配。遇到左括号入栈，遇到右括号出栈，如果出栈的左括号与右括号不匹配，则说明括号不匹配。
- 表达式求值： 将中缀表达式转换为后缀表达式（逆波兰表达式），然后使用栈进行求值。
- 浏览器的前进后退功能： 使用两个栈分别存储前进和后退的页面，实现浏览器的前进后退功能。
- 深度优先搜索（DFS）： 在图的深度优先搜索算法中，可以使用栈来存储待访问的节点。
- 函数调用栈： 编译器使用栈来管理函数调用和返回。
例如，一个简单的括号匹配的例子：
import java.util.Deque;
import java.util.ArrayDeque;
public class BracketMatching {
public static boolean isValid(String s) {
Deque stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) {
return false; // 缺少左括号
}
char top = stack.pop();
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
return false; // 括号不匹配
}
}
}
return stack.isEmpty(); // 检查是否有未匹配的左括号
}
public static void main(String[] args) {
String s1 = "(){}[]";
String s2 = "([)]";
System.out.println(s1 + " is valid: " + isValid(s1)); // 输出: true
System.out.println(s2 + " is valid: " + isValid(s2)); // 输出: false
}
} 理解栈的原理和应用，能帮助我们更好地解决各种编程问题。 虽然看起来简单，但栈的巧妙运用，常常能带来意想不到的解决方案。
