Java Vector和Stack

Java

最原始的列表结构

Vector

Vector是抽象列表子列，从接口上看具备随机访问列表特性
内部除了底层数组，当前数据量，还有变量维护扩容增长量

Vector.java
1
2
3
4
5
6
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    protected Object[] elementData;
    protected int elementCount;
    protected int capacityIncrement;
    //...
}

容量如果不指定就是10，扩容增长是0即使用默认机制

Vector.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    //...
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}

public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector() {
    this(10);
}

增长的前提是保障容量，可能涉及扩容

Vector.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

private void ensureCapacityHelper(int minCapacity) {
    //需要的容量超过了现有,需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    //如果未指定增长值，就扩容二倍
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
    //扩容后还不够，就直接扩到需求量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //数据复制
    elementData = Arrays.copyOf(elementData, newCapacity);
}

所有操作都被同步保护

Vector.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}
public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

即使只读获取变量值也同步，因为变量值并无volatile修饰，保障可见性

Vector.java
1
2
3
4
5
6
public synchronized int size() {
    return elementCount;
}
public synchronized int capacity() {
    return elementData.length;
}

Stack

Stack直接继承自Vector,实现上非常简单，利用最后一个元素作为栈顶

Stack.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Stack<E> extends Vector<E> {
    public Stack() {
    }

    //只有一行，无需再加同步
    public E push(E item) {
        addElement(item);
        return item;
    }

    //删除最后元素
    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);
    }

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

版权声明

This site by Linest is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由Linest创作并维护的博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文永久链接：http://linest.github.io/2018/03/01/java-vector-stack/