Java实现链栈的示例代码

Java链栈是一种特殊的栈，底层是使用单向链表实现的，相比较数组实现栈的方式，链栈可以无需考虑容量的问题，能够动态地适应数据结构的需求。下面详细讲解Java实现链栈的示例代码的完整攻略。

1. 实现链栈的基本步骤

Java实现链栈的基本步骤如下：

1. 定义链栈的节点类
2. 定义链栈类，包含入栈、出栈、查看栈顶数据等方法
3. 在链栈类中，定义一个栈顶节点对象，然后在入栈、出栈等方法中对栈顶节点进行操作。

2. 链栈的节点类定义

链栈的节点类定义如下：

public class LinkNode<T> {  // 泛型类型动态传递

    public T data;   // 存放数据

    public LinkNode<T> next;     // 指向节点的下一个节点

    public LinkNode(T data) {    // 构造方法，用于创建节点
        this.data = data;        // 初始化数据
        this.next = null;        // 新节点没有后继节点，所以初始化为null
    }
}

因为链栈底层是单向链表，所以定义节点类时需要包含下一个节点的指针和数据。

3. 链栈类定义

链栈类的定义如下：

public class LinkStack<T> {

    private LinkNode<T> top;    // 栈顶指针

    public LinkStack() {
        top = null;
    }

    /**
     * 入栈
     * @param data 数据
     */
    public void push(T data) {
        LinkNode<T> node = new LinkNode<T>(data);
        node.next = top;
        top = node;
    }

    /**
     * 出栈
     * @return 返回出栈元素
     */
    public T pop() {
        if (isEmpty()) {
            return null;
        }
        T data = top.data;
        top = top.next;
        return data;
    }

    /**
     * 查看栈顶数据
     * @return 返回栈顶元素
     */
    public T peek() {
        if (isEmpty()) {
            return null;
        }
        return top.data;
    }

    /**
     * 判断栈是否为空
     * @return true为空，false不为空
     */
    public boolean isEmpty() {
        return top == null;
    }
}

通过节点类中的next指针，可以将节点串起来组成单向链表，然后在链栈类中，定义一个栈顶指针对象top，表示链栈的栈顶节点。在入栈操作时，新建一个节点对象，并将该节点对象的next指针指向top，然后将top指向该节点。在出栈操作时，先判断链栈是否为空，不为空则将栈顶节点出栈，并将top指针下移。

4. 示例说明

下面通过两个示例说明如何使用Java实现链栈：

示例1：将字符串中的字符逆序压入栈中

public static void reverseString(String str) {
    LinkStack<Character> stack = new LinkStack<>();
    for (int i = 0; i < str.length(); i++) {
        stack.push(str.charAt(i));
    }
    while (!stack.isEmpty()) {
        System.out.print(stack.pop());
    }
}

首先创建一个LinkStack对象stack，然后从左往右遍历字符串中的字符，将每个字符压入栈中。然后通过调用pop()方法，将栈中的字符依次出栈，即可达到逆序的效果。该示例中使用到了栈的特性：先进后出。

示例2：使用链栈解决表达式求值问题

public static int calculate(String str) {
    LinkStack<Integer> numbers = new LinkStack<>();  // 存放操作数的栈
    LinkStack<Character> operators = new LinkStack<>();  // 存放运算符的栈
    int length = str.length();
    for (int i = 0; i < length; i++) {
        char c = str.charAt(i);
        if (Character.isDigit(c)) {
            int number = c - '0';
            while (i + 1 < length && Character.isDigit(str.charAt(i + 1))) {
                // 如果下一个字符是数字，则构成多位数
                number = number * 10 + (str.charAt(i + 1) - '0');
                i++;
            }
            numbers.push(number);
        } else if (c == '+' || c == '-') {
            while (!operators.isEmpty()) {
                int a = numbers.pop();
                int b = numbers.pop();
                char op = operators.pop();
                if (op == '+') {
                    numbers.push(b + a);
                } else if (op == '-') {
                    numbers.push(b - a);
                }
            }
            operators.push(c);
        }
    }
    while (!operators.isEmpty()) {
        int a = numbers.pop();
        int b = numbers.pop();
        char op = operators.pop();
        if (op == '+') {
            numbers.push(b + a);
        } else if (op == '-') {
            numbers.push(b - a);
        }
    }
    return numbers.pop();
}

该示例中使用到了两个链栈：一个存放操作数的栈numbers，和一个存放运算符的栈operators。该示例实现了简单的四则运算，仅考虑加减运算，通过对比运算符优先级，调用相应的方法进行计算。该示例中同样使用到了栈的特性：后进先出。

以上两个示例说明了链栈在实际问题中的应用，可以根据实际需求灵活使用链栈。