栈是后进先出的数据结构，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<Integer> 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<Integer> 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<Character> 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 } }
理解栈的原理和应用，能帮助我们更好地解决各种编程问题。 虽然看起来简单，但栈的巧妙运用，常常能带来意想不到的解决方案。
评论（已关闭）
评论已关闭