Stack(栈)是一种常用的数据结构，它可以用于实现许多算法和函数。在Java中，可以通过java.util.Stack类来实现栈。当需要LIFO（Last-In-First-Out）数据结构时，可以使用Stack。
一、Stack的基本操作
在Java中，Stack类是Vector的一个子类。除了由Vector提供的全部操作之外，Stack还提供了自己的push、pop、empty等方法。其中，push方法用于入栈，pop方法用于出栈，empty方法用于判断栈是否为空。下面是Stack的基本操作的代码示例。
Stack stack = new Stack();
stack.push(1); //入栈
stack.push(2);
stack.push(3);
while (!stack.empty()) { //判断栈是否为空
System.out.println(stack.pop()); //出栈
}
在以上示例代码中，声明了一个Stack对象并将元素1、2、3入栈，然后通过while循环不断将栈顶元素出栈并打印，直到栈为空。
二、Stack的应用1：括号匹配
括号匹配是栈最常见的应用之一。对于一个字符串，如果其中的括号全部是匹配的，那么就可以认为它是一个合法的表达式。可以使用Stack来检查一个字符串中的括号是否匹配。
public static boolean isMatch(String s) {
Stack stack = new Stack();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' && !stack.isEmpty() && stack.peek() == '(') {
stack.pop();
} else if (c == ']' && !stack.isEmpty() && stack.peek() == '[') {
stack.pop();
} else if (c == '}' && !stack.isEmpty() && stack.peek() == '{') {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}
在以上示例代码中，isMatch方法使用Stack来判断字符串s中的括号是否匹配。遇到左括号就入栈，遇到右括号就判断它和栈顶元素是否匹配。如果匹配，则将栈顶元素出栈；如果不匹配，则说明括号不匹配，返回false。最后，如果栈为空，则说明括号全部匹配，返回true。
三、Stack的应用2：逆波兰表达式求解
逆波兰表达式（Reverse Polish Notation，简称RPN）也称后缀表达式。它将运算符写在操作数（即数字）的后面，使得整个表达式没有括号，从而避免了表达式的歧义。可以用Stack来求解逆波兰表达式。
public static int evalRPN(String[] tokens) {
Stack stack = new Stack();
for (String token : tokens) {
if (token.equals("+")) {
int b = stack.pop();
int a = stack.pop();
stack.push(a + b);
} else if (token.equals("-")) {
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
} else if (token.equals("*")) {
int b = stack.pop();
int a = stack.pop();
stack.push(a * b);
} else if (token.equals("/")) {
int b = stack.pop();
int a = stack.pop();
stack.push(a / b);
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
在以上示例代码中，evalRPN方法使用Stack来求解逆波兰表达式。对于一个操作符，从栈顶依次弹出两个操作数进行计算，并将计算结果压入栈中。对于一个操作数，直接将它压入栈中。最后，栈中只剩下一个元素，即为表达式的值。
四、总结
Stack是Java中常用的数据结构之一，它可以用于实现许多算法和函数。本文介绍了Stack的基本操作，以及两个应用：括号匹配和逆波兰表达式求解。希望读者通过本文的学习，可以更深入地理解Stack的使用。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/256593.html
微信扫一扫 
支付宝扫一扫 