Stack源码分析

Stack类图

Stack是java.util包下List接口下的一个集合子类，是一个栈，线程安全的。底层是通过继承Vector实现的。

• AbstractList抽象类：List的抽象父类，实现一些List通用的方法。
• Cloneable接口：实现对象拷贝必须要实现的接口。
• Serializable接口：实现序列化必须要实现的接口。
• RandomAccess接口：用于定义数组实现随机访问的算法，ArrayList和Vector都实现了该接口。

Stack类属性

Stack内部只定义了一个序列化ID，其余属性都是继承自Vector。

Vector源码分析链接：https://blog.csdn.net/qq_42191317/article/details/96752763

Stack常用API

public Stack() {
    }
           

构造方法：空参，什么也没有处理，实例化的时候，父类的构造器也会实例化。

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

        return item;
    }

    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }
           

push方法：入栈一个元素，调用Vector的add方法实现，往数组末尾增加一个元素，时间复杂度O(1)

public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
           

peek方法：查看当前栈顶元素，即数组的头部元素，调用Vector的elementAt方法，根据下标访问，时间复杂度O(1)

public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }
           

pop方法：出栈一个元素，调用Vector的removeElementAt方法，根据下标删除元素，由于栈后进先出的特性，每次删除的都是末尾元素，时间复杂度O(1)

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

empty方法：判空方法，判断数组当前元素个数是否为0

public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
           

search方法：搜索某个元素是否存在，存在返回下标，不存在返回-1，如果存在多个，返回最后压入的那个

总结

• Stack是一个栈结构，继承自Vector，线程安全的。
• 入栈、出栈时间复杂度都是O(1)，查找某个元素时间复杂度O(n)。