Java集合篇之逐渐被遗忘的Stack，手写一个栈你会吗？

2024 年 03 月 17 日

69 次浏览

2443字数

在Java集合框架中，Stack类是一个后入先出(LIFO)的堆栈，但在现代的Java开发中，这个类往往被 Deque接口的实现类（如 LinkedList或 ArrayDeque）所替代。不过，手写一个栈结构不仅是对数据结构理解的一种体现，也是检验编程能力的一个很好的例子。

为了实现一个基础的栈，我们可以使用数组或链表作为内部存储结构。以下是使用数组实现的一个简单的栈结构，考虑到易懂和实用性，我会展示一个简易版本的栈实现，它将支持基本的操作：压栈（push）、弹栈（pop）、查看栈顶元素（peek）和检查栈是否为空（isEmpty）。首先，我们定义栈的数据结构如下：

public class CustomStack<E> {
    private Object[] array;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;

    public CustomStack() {
        array = new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public E peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return (E) array[size - 1];
    }

    public E pop() {
        E element = peek();
        array[--size] = null; // 防止内存泄漏
        return element;
    }

    public void push(E item) {
        ensureCapacity();
        array[size++] = item;
    }

    private void ensureCapacity() {
        if (size >= array.length) {
            int newSize = array.length * 2;
            array = Arrays.copyOf(array, newSize);
        }
    }

    // 更多实用方法（例如返回栈的大小，遍历等）可以根据需要增加
}

在这个 CustomStack类中，我们使用了泛型来提供类型安全，并且内部使用了一个 Object类型的数组来存储栈中的元素。数组的初始化大小为 DEFAULT_CAPACITY，这是我们预设的一个值，在数组容量不够时，通过 ensureCapacity方法进行扩容。

push方法将元素压入栈，并在必要时增加数组的大小。pop方法从栈中移除顶部元素并返回这个元素，该方法在执行之前会调用 peek方法来确保栈不为空，并获取栈顶元素。

这种简单的栈实现在功能上可能与 java.util.Stack类类似，但它避免了继承自 Vector类的 java.util.Stack带来的线程同步开销。在多线程环境下，我们需要关注线程安全的问题，java.util.Stack是线程同步的，如果不需要这个特性，使用我们自己的 CustomStack会更高效。

如果需要使用链表来手写栈，则可以创建一个节点类来代表链表的节点，然后在栈类中使用这些节点来存储信息。链表实现的栈可以避免数组实现时的数组扩容操作，从而提高操作的效率。

总之，虽然在日常开发中，java.util.Stack正逐渐被其他类如 Deque接口的实现所取代，但手写一个栈（无论是基于数组还是链表）都是一次很好的编程练习，它可以帮助开发者更加深入地理解栈这种数据结构的工作原理和各种操作。