Java集合-Stack

前言

Stack 是 Java 集合框架中的一个类，继承自 Vector，提供了传统的栈数据结构功能（后进先出，LIFO）。下面从源码入手，分析其实现原理、主要方法和特点。

源码分析

类的定义

Stack 类位于 java.util 包中，源码定义如下：

1
2
3
4
5
6

public class Stack<E> extends Vector<E> {
    // 构造方法
    public Stack() {
    }
    // ... 其他方法
}

Stack 继承自 Vector，而 Vector 是一个线程安全的动态数组（内部基于 Object[] 实现）。因此，Stack 本质上是一个线程安全的线性表，只是增加了栈的操作方法。

从 Java 5 开始，Stack 支持泛型，允许指定元素类型<E>。

核心方法

Stack 提供了栈的基本操作，包括 push（入栈）、pop（出栈）、peek（查看栈顶元素）、empty（判断栈是否为空）等。逐一分析这些方法的实现。

push - 入栈

1
2
3
4

public E push(E item) {
    addElement(item);
    return item;
}

push 方法直接调用父类 Vector 的 addElement 方法，将元素添加到数组末尾。addElement 方法是线程安全的。

时间复杂度：$O(1)$，扩容时为 $O(n)$。

pop - 出栈

1
2
3
4
5
6
7

public synchronized E pop() {
    E obj;
    int len = size();
    obj = peek();
    removeElementAt(len - 1);
    return obj;
}

实现：

1. 调用 peek() 获取栈顶元素（最后一个元素）。
2. 调用 removeElementAt 删除栈顶元素。
3. 返回被移除的元素。

时间复杂度：$O(n)$，因为移除末尾元素涉及数组移动。

peek - 查看栈顶元素

1
2
3
4
5
6

public synchronized E peek() {
    int len = size();
    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

返回最后一个元素（栈顶），如果栈为空则抛出 EmptyStackException。

时间复杂度：$O(1)$。

empty - 判断栈是否为空

1
2
3

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

直接调用 Vector 的 size() 方法，检查元素数量是否为0。

search - 查找元素位置

1
2
3
4
5
6
7

public synchronized int search(Object o) {
    int i = lastIndexOf(o);
    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

实现：

1. 调用Vector的lastIndexOf，从数组末尾开始查找元素。
2. 如果找到，返回元素距离栈顶的距离（从1开始计数）；未找到返回-1。

时间复杂度：$O(n)$。

后记

特点

• 线程安全：继承自 Vector，所有方法都加了 synchronized，适合多线程环境。
• 动态扩容：底层基于数组，容量不足时自动扩容。
• LIFO结构：提供了标准的栈操作。

优点

• 简单易用，适合需要线程安全的场景。
• 继承了 Vector 的所有功能，可以当作动态数组使用。

缺点

性能较低：

• pop 操作时间复杂度为 $O(n)$，相比其他栈实现（如基于链表的 Deque）效率较低。
• 线程同步开销大，多线程竞争时性能下降。

过时推荐：Java 官方更推荐使用 Deque 接口的实现（如 ArrayDeque）来替代 Stack，因为 Deque 更高效且功能更灵活。