Java基于链表实现栈的方法详解

一、链表

链表是一种常见的数据结构，可以通过指针将一组不连续的内存块连接起来，形成一个链式结构。链表中的每个节点包含两部分信息，一个是数据域用于存储数据，一个是指针域用于指向下一个节点的地址。通过头节点可以找到链表的第一个节点，通过节点的指针可以找到链表的其他节点。

二、栈

栈是一种常见的数据结构，具有先进后出的特点，即后进入的数据先被访问。栈通常包含如下操作：

• push：将元素入栈；
• pop：将栈顶元素出栈；
• peek：获取栈顶元素值，但不出栈。

三、基于链表实现栈

基于链表实现栈需要定义一个节点类，包含两个成员变量，一个是存储数据的变量，另一个是指向下一个节点的指针变量。同时需要定义一个栈类，包含一个头节点指针变量，用于指向栈顶元素。

下面是Java基于链表实现栈的示例代码：

public class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
    }
}

public class Stack {
    private Node head;

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

    public void push(int data) {
        Node node = new Node(data);
        node.next = head;
        head = node;
    }

    public int pop() {
        if (head == null) {
            throw new RuntimeException("Stack is empty");
        }
        int data = head.data;
        head = head.next;
        return data;
    }

    public int peek() {
        if (head == null) {
            throw new RuntimeException("Stack is empty");
        }
        return head.data;
    }
}

在上述示例代码中，节点类Node包含两个成员变量data和next，其中data用于存储节点的值，next用于指向下一个节点的地址。栈类Stack包含一个指针变量head，用于指向栈顶元素，同时包含三个方法：

• isEmpty：判断栈是否为空；
• push：将元素入栈；
• pop：将栈顶元素出栈；
• peek：获取栈顶元素值，但不出栈。

四、示例说明

示例一

public static void main(String[] args) {
    Stack stack = new Stack();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    System.out.println(stack.pop()); //输出3
    System.out.println(stack.pop()); //输出2
    System.out.println(stack.peek()); //输出1
    System.out.println(stack.pop()); //输出1
}

上述示例代码中，首先创建一个空栈stack，然后依次将元素1、2、3入栈，接着依次进行出栈和获取栈顶元素操作，输出的结果为3、2、1、1，符合栈的先进后出特性。

示例二

public static void main(String[] args) {
    Stack stack = new Stack();
    System.out.println(stack.isEmpty()); //输出true
    stack.push(1);
    stack.push(2);
    System.out.println(stack.isEmpty()); //输出false
    stack.pop();
    stack.pop();
    System.out.println(stack.isEmpty()); //输出true
}

上述示例代码中，首先创建一个空栈stack，通过调用isEmpty方法判断栈是否为空，输出true。然后依次将元素1、2入栈，再次调用isEmpty方法判断栈是否为空，输出false。接着进行两次出栈操作，再次调用isEmpty方法判断栈是否为空，输出true，符合栈的先进后出特性和isEmpty方法的逻辑。