java代码如何用链表实现链式栈 java代码链式栈结构的基础编写技巧

梦涛小哥_3255

发布时间：2025-08-11 23:45:01

796人浏览过

来源于php中文网

原创

链式栈的核心实现是通过单向链表在头部进行所有操作以满足lifo特性，1. 节点类包含数据和指向下一节点的引用；2. 栈类维护top指针和size计数器；3. push操作将新节点置为新的栈顶；4. pop操作移除并返回栈顶元素，需检查空栈；5. peek操作返回栈顶元素但不移除；6. 所有基本操作均为o(1)时间复杂度；7. 链式栈优势在于动态扩容，避免栈满问题，适用于元素数量不确定的场景；8. 缺点是每个节点额外占用指针内存，可能导致较高内存开销和碎片化；9. 常见错误包括未处理空栈导致nullpointerexception、top指针更新错误、size变量维护不一致及泛型使用不当；10. 实际应用包括撤销重做功能、表达式求值、浏览器历史记录、深度优先搜索和函数调用栈等，其动态性和高效操作使其在多种算法和系统机制中具有重要价值。

java代码如何用链表实现链式栈 java代码链式栈结构的基础编写技巧

在Java中，用链表实现链式栈，核心在于利用链表的动态特性来模拟栈的“后进先出”（LIFO）行为。这意味着我们不再受限于固定大小的数组，可以根据需要自由地增减元素。本质上，它是一个单向链表，所有的操作——入栈（push）、出栈（pop）、查看栈顶（peek）——都集中在链表的头部进行，因为这样效率最高，也最符合栈的逻辑。

解决方案

要构建一个链式栈，我们需要两个基本组件：一个表示栈中元素的“节点”类，以及一个管理这些节点的“栈”类。

节点（Node）类

立即学习“Java免费学习笔记（深入）”；

这是链式栈的基石。每个节点都包含两部分信息：实际存储的数据，以及一个指向下一个节点的引用。

class Node<T> {
    T data;         // 存储的数据
    Node<T> next;   // 指向下一个节点的引用

    public Node(T data) {
        this.data = data;
        this.next = null; // 新节点默认不指向任何地方
    }
}

链式栈（LinkedStack）类

这个类将负责封装栈的所有操作。我们需要一个

top

引用来始终指向栈的顶部元素，以及一个

size

变量来跟踪栈中元素的数量，这在某些场景下会很有用。

public class LinkedStack<T> {
    private Node<T> top; // 栈顶元素，所有操作都围绕它进行
    private int size;    // 栈中元素的数量

    public LinkedStack() {
        this.top = null; // 初始时栈是空的
        this.size = 0;
    }

    /**
     * 入栈操作：将元素添加到栈顶。
     * 这是一个O(1)操作，非常高效。
     */
    public void push(T item) {
        Node<T> newNode = new Node<>(item);
        newNode.next = top; // 新节点指向当前的栈顶
        top = newNode;      // 新节点成为新的栈顶
        size++;
        // 思考一下，这种操作方式，新元素总是在最前面，这正是栈的LIFO特性所需要的。
    }

    /**
     * 出栈操作：移除并返回栈顶元素。
     * 同样是O(1)操作。
     */
    public T pop() {
        if (isEmpty()) {
            // 必须处理栈空的情况，否则会遇到NullPointerException。
            // 抛出异常是比较标准的做法，告知调用者栈无法执行此操作。
            throw new IllegalStateException("Stack is empty, cannot pop.");
        }
        T data = top.data; // 获取栈顶数据
        top = top.next;    // 栈顶下移，指向下一个节点
        size--;
        return data;
    }

    /**
     * 查看栈顶元素：返回栈顶元素但不移除它。
     * O(1)操作。
     */
    public T peek() {
        if (isEmpty()) {
            // 同样需要检查栈是否为空。
            throw new IllegalStateException("Stack is empty, cannot peek.");
        }
        return top.data; // 直接返回栈顶数据
    }

    /**
     * 判断栈是否为空。
     */
    public boolean isEmpty() {
        return top == null; // 或者 return size == 0; 效果一样，但top == null更直观地反映结构状态。
    }

    /**
     * 返回栈中元素的数量。
     */
    public int size() {
        return size;
    }

    // 可以在这里添加一个简单的main方法进行测试
    public static void main(String[] args) {
        LinkedStack<String> myStack = new LinkedStack<>();
        System.out.println("Is stack empty? " + myStack.isEmpty()); // true

        myStack.push("Apple");
        myStack.push("Banana");
        myStack.push("Cherry");

        System.out.println("Stack size: " + myStack.size()); // 3
        System.out.println("Top element: " + myStack.peek()); // Cherry

        System.out.println("Popped: " + myStack.pop()); // Cherry
        System.out.println("Stack size after pop: " + myStack.size()); // 2
        System.out.println("New top element: " + myStack.peek()); // Banana

        myStack.push("Date");
        System.out.println("Top element after push: " + myStack.peek()); // Date

        while (!myStack.isEmpty()) {
            System.out.println("Popping: " + myStack.pop());
        }
        System.out.println("Is stack empty now? " + myStack.isEmpty()); // true

        try {
            myStack.pop(); // This should throw an exception
        } catch (IllegalStateException e) {
            System.out.println("Caught expected error: " + e.getMessage());
        }
    }
}

链式栈与数组栈：何时选择链式实现？

在选择栈的底层实现时，我们通常会在链式栈和基于数组的栈（比如Java的

ArrayDeque

或

Stack

类内部）之间做权衡。链式栈最显著的优势在于其动态扩容的能力。它不需要预先设定容量，理论上只要内存允许，就可以无限地添加元素。这意味着你永远不会遇到“栈满”导致的操作失败，这对于那些元素数量难以预测的应用场景来说，简直是福音。

另一方面，数组栈在特定情况下可能会更快，尤其是在访问元素时（因为数组是连续内存），但它最大的痛点在于固定容量。一旦达到容量上限，就需要进行扩容操作，这通常涉及到创建一个更大的新数组并将所有旧元素复制过去，这个过程的开销是O(N)级别的，虽然不常发生，但一旦发生，会带来性能上的瞬时抖动。

链式栈的每个操作（push、pop、peek）都是O(1)的，因为它只涉及对

top

引用和几个指针的修改，与栈中元素的总数无关。不过，链式栈的缺点在于内存开销。每个节点除了存储数据本身，还需要额外存储一个指向下一个节点的引用。这意味着每个元素会比数组栈多占用一些内存（通常是8字节或更多，取决于系统架构），这在存储大量小对象时可能会累积成可观的开销。而且，链式存储可能导致内存碎片化，尽管现代JVM的垃圾回收器在这方面做得很好，但这也是其与数组连续内存特性不同之处。因此，如果你对内存使用非常敏感，或者栈的规模相对固定且不大，数组栈可能更优；而如果追求极致的动态性，或者栈的深度变化莫测，链式栈的优势就凸显出来了。

实现链式栈时常见的错误与陷阱有哪些？

在编写链式栈时，一些常见的错误和陷阱可能会导致程序行为异常，甚至崩溃。

1. 空栈操作未处理（NullPointerException）

这是最常见也最危险的错误。当你尝试从一个空栈中

pop()

或

peek()

时，

top

引用将是

null

。如果此时不进行检查直接访问

top.data

或

top.next

，就会立即抛出

NullPointerException

。正确的做法是在这些方法开始时，先用

if (isEmpty())

进行判断，并根据业务需求选择返回

null

、抛出

IllegalStateException

或其他自定义异常。在我的示例代码中，我选择了抛出

IllegalStateException

，这是一种明确告知调用者操作不合法的强硬方式。

top

引用更新错误

push

和

pop

操作的核心就是正确地更新

top

引用。

在
```
push
```
时，新节点应该指向当前的
```
top
```
，然后新节点才成为新的
```
top
```
。顺序错了，链就断了。
在
```
pop
```
时，
```
top
```
应该指向
```
top.next
```
。如果忘记了这一步，或者错误地指向了其他地方，就会导致栈的逻辑混乱，可能出现无限循环或者数据丢失。