详解Java中LinkedStack链栈的实现

前言

栈(Stack)是一种非常常见的数据结构，它的特点是先进后出，后进先出。链栈(Linked Stack)是基于链表实现的栈，它比数组实现的栈更加灵活和方便，因此广泛应用于许多问题的解决中。在本文中，我们将介绍如何实现Java中的链栈，并通过两个示例说明链栈的使用。

实现

链栈的实现中需要考虑以下几个问题：

1. 节点类的设计
2. 栈顶指针的管理
3. 入栈操作的实现
4. 出栈操作的实现

节点类的设计

节点是链栈中最基本的数据类型，它包含两个属性：一个是存储的值，另一个是指向下一个节点的指针。因此，我们可以定义一个节点类Node，代码如下：

public class Node<T> {
    public T val; // 存储的值
    public Node<T> next; // 指向下一个节点的指针

    public Node(T val) {
        this.val = val;
        this.next = null;
    }
}

其中，我们使用了泛型T来表示节点存储的值可以是任意类型。在节点的构造函数中，我们需要传递节点存储的值。

栈顶指针的管理

链栈的栈顶是链表的头部，因此我们需要一个指针变量top来记录当前的栈顶。当栈顶指针为空时，表示链栈为空。

public class LinkedStack<T> {
    private Node<T> top; // 栈顶指针

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

入栈操作的实现

链栈的入栈操作相当于在链表头部插入一个节点。我们需要将新节点的next指针指向当前的栈顶，然后更新栈顶指针即可。

public class LinkedStack<T> {
    // ...

    public void push(T val) {
        Node<T> newNode = new Node<>(val);
        newNode.next = top; // 新节点的next指针指向当前的栈顶
        top = newNode; // 更新栈顶指针
    }
}

出栈操作的实现

链栈的出栈操作相当于从链表头部删除一个节点。我们需要将当前栈顶指针指向下一个节点，并返回被删除节点的值。

public class LinkedStack<T> {
    // ...

    public T pop() {
        if (isEmpty()) { // 判断链栈是否为空
            throw new RuntimeException("Stack is empty");
        }
        Node<T> nodeToRemove = top; // 当前栈顶节点
        top = top.next; // 更新栈顶指针
        return nodeToRemove.val; // 返回被删除节点的值
    }
}

isEmpty操作的实现

链栈的isEmpty操作用于判断链栈是否为空。

public class LinkedStack<T> {
    // ...

    public boolean isEmpty() {
        return top == null;
    }
}

示例

示例1：计算字符串中括号的匹配数

假如我们有一个包含括号的字符串，如"(())"、"()"、"())("等等。我们希望能够计算出这个字符串中括号的匹配数，即左右括号相等的括号对数量。

我们可以使用链栈实现这个功能，具体代码如下：

public int matchCount(String s) {
    LinkedStack<Character> stack = new LinkedStack<>();
    int count = 0;
    for (char c : s.toCharArray()) {
        if (c == '(') {
            stack.push(c);
        } else if (c == ')') {
            if (!stack.isEmpty() && stack.pop() == '(') {
                count++;
            }
        }
    }
    return count;
}

在这个示例中，我们首先定义了一个空的链栈，然后遍历字符串中的每个字符。当遇到左括号时，我们将其入栈；当遇到右括号时，我们从栈中弹出一个元素，并判断是否与当前的右括号匹配，如果匹配，则计数器count加一。

示例2：将一个整数转化为二进制数

假如我们希望将一个十进制整数转化为二进制数，我们可以使用链栈实现这个功能，具体代码如下：

public String toBinaryString(int n) {
    LinkedStack<Integer> stack = new LinkedStack<>();
    while (n > 0) {
        stack.push(n % 2);
        n /= 2;
    }
    StringBuilder sb = new StringBuilder();
    while (!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    return sb.toString();
}

在这个示例中，我们定义了一个空的链栈，然后使用循环将整数n除以2直至商为0，并将除得的余数入栈。最后，我们将栈中的每个元素依次弹出，并拼接成二进制数字符串返回。

总结

本文介绍了Java中链栈的实现，以及两个实例说明了链栈的应用。链栈的实现比较简单，但是需要注意指针的管理和入栈、出栈的实现。在实际开发中，链栈可以用于很多问题的解决，比如匹配括号问题、表达式求值等等。