转载

Java常用数据结构之Stack&Vector

继续Java常用数据结构分析之路，这次的主角是 Stack 和 Vector 。Vector已经不推荐使用了，可以用ArrayList和LinkedList替代，它的主要特色是线程安全，代价自然就是效率。Stack则是拥有 先进后出 的特性，在特定的环境下能很好的工作。这两个类相较于List和Map的使用频率要少，但还是需要理解其内部原理的。

类继承关系

先来看Stack：

public class Stack<E> extends Vector<E>
复制代码

原来Stack继承了Vector，那再看Vector：

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
复制代码

又是熟悉的感觉：

继承AbstractList抽象类，算是List模板的扩展；
实现List接口，Vector属于List的一种；
实现RandomAccess接口，一个空接口，用来标记可以随机访问元素；
实现Cloneable接口，可以被克隆；
实现Serializable接口，可以被序列化；

总的来说，Stack和Vector其实都是List的一种实现，可以进行随机访问，子类中实现自己的特征逻辑。

Vector源码分析

重要属性

// 用来存储元素，该数组的大小就是Vector的容量大小，说明支持null
protected Object[] elementData;

// 当前已存储元素的数量
protected int elementCount;

// 当容量不够时，Vector扩充的大小
protected int capacityIncrement;

// Vector的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
复制代码

Vector使用数组来存储元素，有意思的是开发人员可以自己控制每次扩容的大小。

构造函数

public Vector() {
        this(10); // 默认容量10
    }
    
public Vector(int initialCapacity) {
        this(initialCapacity, 0); // 默认扩容增量设置为0表示双倍扩展
    }
    
// 可以设置扩容时增量大小
public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
复制代码

使用无参构造函数创建Vector时，默认大小是10，且每次扩容时容量变成原来的两倍。

重用方法

先来看扩容方法：

private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length; // 因为已经满了，所以是旧容量
        // 如果扩充容量值小于等于0，则直接扩充为原来的两倍
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        // minCapacity一般是oldCapacity+1，即执行add操作扩容
        if (newCapacity - minCapacity <= 0) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
复制代码

当执行add操作时，就有可能进行扩容，来看看add方法：

public synchronized boolean add(E e) {
        modCount++; // 记录修改次数
        add(e, elementData, elementCount);
        return true;
    }
    
private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow(); // 扩容
        elementData[s] = e; // 增加新元素
        elementCount = s + 1; // 元素数量加1
    }
    
private Object[] grow() {
        return grow(elementCount + 1); // 扩充的最小容量是原数据量加1
    }
    
private Object[] grow(int minCapacity) {
        // 调用newCapacity获取新容量，同时进行数组复制
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }
复制代码

注意到 add(E e) 方法增加了 synchronized 关键字，说明是线程安全的。其实，Vector大部分公开方法都有 synchronized 关键字，所以说Vector是线程安全的。

Vector中除了 add(E e) 还可以使用 addElement(E obj) 和 insertElementAt(E obj, int index) 来添加元素，内部实现大同小异。

有扩容，理论上也要有缩容，然而Vector没有自动缩容逻辑，但提供了一个方法：

public synchronized void trimToSize() {
        modCount++;
        int oldCapacity = elementData.length;
        if (elementCount < oldCapacity) {
            elementData = Arrays.copyOf(elementData, elementCount);
        }
    }
复制代码

trimToSize 方法可以将Vector的容量调整到元素数量大小。

说到Vector的容量，其实Vector是支持自定义设置大小的，使用 setSize(int newSize) 即可。

public synchronized void setSize(int newSize) {
        modCount++;
        if (newSize > elementData.length)
            grow(newSize);
        final Object[] es = elementData;
        for (int to = elementCount, i = newSize; i < to; i++)
            es[i] = null; // 不够则补null，多了则剪去
        elementCount = newSize;
    }
复制代码

如果设置的大小大于当前存储的元素数量，则补null值；如果小于现有元素数量，则会剪去多余元素。

遍历方法

对应Vector，可以使用三种方法进行遍历：

使用 iterator() 或者 listIterator() 方法；
使用 elements() 方法；
使用 forEach(Consumer<? super E> action) 方法；

第一种方法中，使用iterator时，不可以对Vector进行add和remove操作；第二种方法中，使用elements时，可以使用add操作，但不可以使用remove操作；第三种方法，可以使用lambda表达式。

Vector的主要源码分析就这么多，还有一些导航方法，如 indexOf 、 lastElement 等实现逻辑都很简单。

Stack源码分析

Stack类继承了Vector，也是使用数组进行元素存储，其源码很少，就提供了几个公有方法，下面直接分析这些方法。

push方法

public E push(E item) {
        // 直接调用Vector的addElement方法，将元素添加到数组尾部
        addElement(item);
        return item;
    }
复制代码

pop和peek方法

// 返回栈顶元素，并且在数组中删除该元素
public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek(); // 获取顶部元素
        removeElementAt(len - 1); // 去除
        return obj;
    }
    
public synchronized E peek() {
        int     len = size();
        if (len == 0) // 空异常
            throw new EmptyStackException();
        return elementAt(len - 1); // 随机访问数组中最后一个元素
    }
复制代码

search方法

// 返回离栈顶最近的指定元素到栈顶的距离
// 从1开始
public synchronized int search(Object o) {
        int i = lastIndexOf(o); // 指定元素在数组中最后出现的位置
        if (i >= 0) { // 获取差量
            return size() - i;
        }
        return -1;
    }
复制代码

举个例子：

基础Stack：7 2 11 -6 5 8 66，执行下面的代码：

// 7 2 11 -6 5 8 66
        // 基本位置为1
        System.out.println("search操作，11距离顶部的距离：" + stack.search(11));
        System.out.println("search 7：" + stack.search(7));
        System.out.println("search 66：" + stack.search(66));
        stack.push(0);
        stack.push(0);
        stack.push(0);
        stack.push(9);
        stack.push(33); // 7 2 11 -6 5 8 66 0 0 0 9 33 
        stack.forEach(integer -> {
            System.out.print(integer + " ");
        });
        System.out.println();
        System.out.println("search 离顶部最近的0：" + stack.search(0));
复制代码