Java数据结构与算法之栈(动力节点Java学院整理)

Java数据结构与算法之栈攻略

什么是栈？

栈是一种线性结构，属于“先进后出”（Last In First Out，LIFO）的数据结构。它只允许在栈顶进行插入和删除操作。

栈的实现

栈的实现有两种方式：

1. 基于数组实现的顺序栈（ArrayStack）
2. 基于链表实现的链式栈（LinkedStack）

1. 基于数组实现的顺序栈

顺序栈的实现需要一个固定大小的数组用于存储数据，同时需要指向栈顶的指针。

public class ArrayStack {
    private int[] data;
    private int top;

    public ArrayStack(int size) {
        this.data = new int[size];
        this.top = -1;
    }

    public boolean push(int num) {
        if (top == data.length - 1) {
            return false;
        }
        data[++top] = num;
        return true;
    }

    public int pop() {
        if (top == -1) {
            return -1;
        }
        return data[top--];
    }
}

2. 基于链表实现的链式栈

链式栈的实现需要一个单向链表，同时需要一个指向栈顶的指针。

public class LinkedNode {
    public int val;
    public LinkedNode next;

    public LinkedNode(int val) {
        this.val = val;
    }
}

public class LinkedStack {
    private LinkedNode top;

    public LinkedStack() {
        this.top = null;
    }

    public boolean push(int num) {
        LinkedNode node = new LinkedNode(num);
        node.next = top;
        top = node;
        return true;
    }

    public int pop() {
        if (top == null) {
            return -1;
        }
        int val = top.val;
        top = top.next;
        return val;
    }
}

栈的应用

栈的应用十分广泛，包括常见的函数调用、表达式求值等。下面分别说明。

函数调用

在计算机程序中，每个函数都有它自己的栈帧（Stack Frame），栈帧包括了函数的参数、局部变量、返回地址等。当一个函数被调用时，它的栈帧就被压入栈中，当函数返回时，这个栈帧就被弹出。这一过程严格按照“先进后出”的原则执行，保证了函数调用的正确性。

表达式求值

表达式求值可以用栈来实现。算法步骤如下：

1. 从左到右扫描表达式。
2. 遇到数字时，直接入栈。
3. 遇到运算符时，弹出栈顶两个元素进行计算，并将结果入栈。
4. 最终，栈中只有一个元素，即表达式的值。

例如，对于表达式“3+4*5-6”，其求值过程如下：

元素	操作
3	入栈
4	入栈
5	入栈
*	弹出2个元素（5、4），计算4*5=20，并将20入栈
+	弹出2个元素（20、3），计算3+20=23，并将23入栈
6	入栈
-	弹出2个元素（6、23），计算23-6=17，并将17入栈

最终，栈中只有一个元素17，即表达式“3+4*5-6”的值为17。

示例

1. 判断括号是否匹配

下面是判断括号是否匹配的示例代码：

public boolean isMatch(String str) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        if (ch == '(') {
            stack.push(ch);
        } else if (ch == ')') {
            if (stack.isEmpty()) {
                return false;
            }
            stack.pop();
        }
    }
    return stack.isEmpty();
}

2. 中缀表达式转后缀表达式

下面是将中缀表达式转化为后缀表达式的示例代码：

public String infixToPostfix(String str) {
    StringBuilder sb = new StringBuilder();
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        if (ch >= '0' && ch <= '9') {
            sb.append(ch);
        } else if (ch == '+' || ch == '-') {
            while (!stack.isEmpty() && stack.peek() != '(') {
                sb.append(stack.pop());
            }
            stack.push(ch);
        } else if (ch == '*' || ch == '/') {
            while (!stack.isEmpty() && (stack.peek() == '*' || stack.peek() == '/')) {
                sb.append(stack.pop());
            }
            stack.push(ch);
        } else if (ch == '(') {
            stack.push(ch);
        } else if (ch == ')') {
            while (stack.peek() != '(') {
                sb.append(stack.pop());
            }
            stack.pop();
        }
    }
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    return sb.toString();
}

总结

本文介绍了栈的相关内容，包括栈的定义、实现、应用以及示例代码。栈在实际开发中非常常用，希望读者能够掌握本文介绍的内容，提高自己的编程能力。