Java栈结构实现与代码教程

一分耕耘，一分收获！既然都打开这篇《Java实现栈结构详解及代码示例》，就坚持看下去，学下去吧！本文主要会给大家讲到等等知识点，如果大家对本文有好的建议或者看到有不足之处，非常欢迎大家积极提出！在后续文章我会继续更新文章相关的内容，希望对大家都有所帮助！

Java实现栈通常有两种方式：基于数组和基于链表。1. 基于数组的栈实现简单，访问速度快，但容量固定，可能栈溢出；2. 基于链表的栈容量可动态扩展，不会溢出，但实现较复杂，访问速度稍慢。两者分别适用于容量已知且性能要求高或容量不确定的场景。此外，Java自带的Stack类因继承Vector存在同步开销、容量固定及设计原则问题，建议自定义实现。栈在函数调用、表达式求值、浏览器导航、编辑器撤销重做、深度优先搜索等场景中广泛应用。对于并发访问，可通过synchronized、ReentrantLock或使用ConcurrentLinkedDeque来解决。栈是LIFO结构，而队列是FIFO结构，二者操作位置不同，适用于不同需求。

Java实现栈，本质上是利用数组或者链表模拟栈的后进先出（LIFO）特性。关键在于维护一个指向栈顶的指针，并实现push（入栈）和pop（出栈）操作。

解决方案：

Java中实现栈，通常有两种方式：基于数组和基于链表。

1. 基于数组的栈：

这种方式的优点是实现简单，访问速度快。缺点是容量固定，可能存在栈溢出的问题。

public class ArrayStack {
    private T[] stack;
    private int top;
    private int capacity;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.stack = (T[]) new Object[capacity]; // 注意类型转换
        this.top = -1; // 初始化栈顶指针
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == capacity - 1;
    }

    public void push(T data) {
        if (isFull()) {
            throw new RuntimeException("Stack is full");
        }
        stack[++top] = data;
    }

    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top--];
    }

    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top];
    }

    public int size() {
        return top + 1;
    }

    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack<>(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("Top element: " + stack.peek()); // Output: 3
        System.out.println("Popped element: " + stack.pop()); // Output: 3
        System.out.println("Current size: " + stack.size()); // Output: 2
    }
}

注意点：

• 数组的类型转换 (T[]) new Object[capacity] 是必要的，因为Java泛型在运行时会被擦除。
• 需要处理栈满和栈空的异常情况。

2. 基于链表的栈：

这种方式的优点是容量可以动态扩展，不会出现栈溢出的问题。缺点是实现相对复杂，访问速度稍慢。

public class LinkedStack {
    private static class Node {
        T data;
        Node next;

        Node(T data) {
            this.data = data;
        }
    }

    private Node top;
    private int size;

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

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

    public void push(T data) {
        Node newNode = new Node<>(data);
        newNode.next = top;
        top = newNode;
        size++;
    }

    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        T data = top.data;
        top = top.next;
        size--;
        return data;
    }

    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.data;
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        LinkedStack stack = new LinkedStack<>();
        stack.push("A");
        stack.push("B");
        stack.push("C");

        System.out.println("Top element: " + stack.peek()); // Output: C
        System.out.println("Popped element: " + stack.pop()); // Output: C
        System.out.println("Current size: " + stack.size()); // Output: 2
    }
}

注意点：

• 使用了内部类 Node 来表示链表的节点。
• push操作在链表头部插入新节点，pop操作移除链表头部的节点。

自定义栈结构，其实就是自己实现一个栈，而不是直接使用Java提供的Stack类。

Java自带的Stack类有什么问题？

Java的Stack类继承自Vector，而Vector是线程安全的，这意味着Stack的很多方法都进行了同步，这在单线程环境下会造成性能损耗。此外，Vector底层使用数组实现，也存在容量固定的问题。更重要的是，从设计角度来看，Stack的设计并不符合单一职责原则。它既包含了栈的逻辑，又包含了Vector的特性。

栈的应用场景有哪些？

栈在计算机科学中应用广泛，例如：

• 函数调用栈： 存储函数调用的信息，用于实现递归和函数返回。
• 表达式求值： 将中缀表达式转换为后缀表达式，并进行求值。
• 浏览器的前进/后退功能： 使用两个栈分别存储前进和后退的页面。
• 编辑器中的撤销/重做功能： 使用栈存储操作历史。
• 深度优先搜索（DFS）： 在图的遍历中使用栈来存储待访问的节点。

如何选择基于数组还是链表的栈实现？

选择哪种实现方式取决于具体的需求。如果事先知道栈的容量大小，并且对性能要求较高，那么基于数组的栈可能更适合。如果栈的容量大小不确定，或者需要频繁进行扩容操作，那么基于链表的栈可能更合适。实际上，很多情况下，使用链表实现的栈更为灵活。

如何处理栈的并发访问问题？

如果多个线程需要同时访问栈，那么需要考虑线程安全问题。可以使用synchronized关键字或者ReentrantLock等机制来保证线程安全。当然，也可以使用线程安全的ConcurrentLinkedDeque来代替手写的栈结构，它在并发环境下有更好的性能。

栈和队列的区别是什么？

栈是后进先出（LIFO）的数据结构，而队列是先进先出（FIFO）的数据结构。栈只允许在栈顶进行插入和删除操作，而队列允许在队尾进行插入操作，在队头进行删除操作。它们是两种不同的数据结构，适用于不同的场景。

本篇关于《Java栈结构实现与代码教程》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！