java数据结构栈的应用头歌答案(数据结构在java中的应用)

什么是Java数据结构栈？

Java数据结构栈（Stack）是一种先进后出（Last In First Out，LIFO）的线性数据结构。它可以通过两个主要的操作：push和pop来实现元素的添加和删除。栈的应用广泛，如表达式求值、函数调用、DFS深度优先搜索等。在Java中，栈可以通过Stack类来实现。

栈的应用：括号匹配问题

括号匹配问题是一个常见的问题，栈可以很好地解决它。当一个字符串中存在括号时，我们可以用栈来判断括号是否匹配。具体方法是首先遍历字符串，如果遇到左括号就入栈，如果遇到右括号就判断当前栈顶元素是否为相应的左括号，如果是则弹出栈顶元素，继续扫描下一个字符，否则括号不匹配。如果最后栈为空，说明括号匹配成功。

例如，对于字符串【(())】，我们可以通过如下Java代码进行括号匹配：

Stack<Character> stack = new Stack<>();
String str = "(()))";
for(int i=0;i<str.length();i++){
    char c = str.charAt(i);
    if(c == '('){
        stack.push(c);
    }else if(c == ')'){
        if(stack.isEmpty() || stack.pop() != '('){
            System.out.println("括号不匹配");
            return;
        }
    }
}
if(stack.isEmpty()){
    System.out.println("括号匹配成功");
}else{
    System.out.println("括号不匹配");
}

栈的应用：表达式求值

栈还可以用来求解数值表达式。当我们面对中缀表达式时，需要先转为后缀表达式，然后再求解后缀表达式。具体方法是利用栈来存储运算符和操作数，从左到右扫描表达式中的每个元素：如果是操作数就入栈，如果是运算符就弹出栈顶两个元素进行计算，并将计算结果入栈，直到最后栈中只剩下一个元素，即为表达式的值。

例如，对于表达式【3 * (4 + 5) / 6】，我们可以通过如下Java代码进行求值：

Stack<Integer> stack = new Stack<>();
String str = "3*(4+5)/6";
for(int i=0;i<str.length();i++){
    char c = str.charAt(i);
    if(Character.isDigit(c)){
        stack.push(c - '0');
    }else if(c == '('){
        stack.push(-1);
    }else if(c == ')'){
        while(stack.peek() != -1){
            int num2 = stack.pop();
            int num1 = stack.pop();
            char operator = stack.pop().charValue();
            int result = compute(num1, num2, operator);
            stack.push(result);
        }
        stack.pop();
    }else if(c == '+' || c == '-' || c == '*' || c == '/'){
        //优先级比栈顶运算符低，则弹出栈顶计算，并将结果入栈
        while(!stack.isEmpty() && priority(c) <= priority(stack.peek().charValue())){
            int num2 = stack.pop();
            int num1 = stack.pop();
            char operator = stack.pop().charValue();
            int result = compute(num1, num2, operator);
            stack.push(result);
        }
        stack.push(c);
    }
}
while(!stack.isEmpty()){
    int num2 = stack.pop();
    int num1 = stack.pop();
    char operator = stack.pop().charValue();
    int result = compute(num1, num2, operator);
    stack.push(result);
}
System.out.println(stack.pop()); //打印结果

public static int priority(char operator){
    switch (operator) {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    default:
        return 0;
    }
}

public static int compute(int num1, int num2, char operator){
    switch (operator) {
    case '+':
        return num1 + num2;
    case '-':
        return num1 - num2;
    case '*':
        return num1 * num2;
    case '/':
        return num1 / num2;
    default:
        return 0;
    }
}