由于之前的分析,所以在看Vector和Stack的源码实现就会非常简单

markdown_img_paste_2019012411263659

观察上图,我们可以看到本文要说的Stack和Vector是父子关系,我们依旧从源码入手,期望能够对你有帮助,如果本文有理解不对的地方,请及时指正,谢谢您

Vector

我们知道Vector的实现和ArrayList一样,都是底层以数组的方式存储的,但是不同的Vector是线程安全的,这一点我们可以从源码中看出来

定义

@since 1.0public class Vector
    
         extends AbstractList
     
          implements List
      
       , RandomAccess, Cloneable, java.io.Serializable{...}

属性

//保存元素的数组protected Object[] elementData;//容量增量,就是数组按多少速度扩容,这里是2倍protected int capacityIncrement;//元素个数protected int elementCount;//最大容量,跟ArrayList一样的private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

对于属性列出了这几个,我们看到一些ArrayList中出现的属性值,可能是由于出现的过早的原因,其中的属性变量名定义的并不是很直观,比如elementCount在ArrayList中称为size

对于其中的方法实现的源码我就不列的很详细了,我看了一下,其实现基本都是在方法上加上了sync关键字

初始化

public Vector() {    this(10);}public Vector(int initialCapacity) {    this(initialCapacity, 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;}public Vector(Collection
     c) {    elementData = c.toArray();    elementCount = elementData.length;    if (elementData.getClass() != Object[].class)        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);}

如上实现较简单,我们从中可以看到,对于Vector的增量和初始化容量我们都可以进行自定义

add

跟之前的ArrayList的实现基本一致,所以就不再赘述

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;}

public void add(int index, E element) {    insertElementAt(element, index);}public synchronized void insertElementAt(E obj, int index) {    if (index > elementCount) {        throw new ArrayIndexOutOfBoundsException(index                                                 + " > " + elementCount);    }    modCount++;    final int s = elementCount;    Object[] elementData = this.elementData;    if (s == elementData.length)        elementData = grow();    //核心方法arrycopy,将要插入的位置挪出来    System.arraycopy(elementData, index,                     elementData, index + 1,                     s - index);    elementData[index] = obj;    elementCount = s + 1;}

//逻辑跟ArrayList中的完全一致,不再赘述public synchronized boolean addAll(int index, Collection
       c) {    if (index < 0 || index > elementCount)        throw new ArrayIndexOutOfBoundsException(index);    Object[] a = c.toArray();    modCount++;    int numNew = a.length;    if (numNew == 0)        return false;    Object[] elementData = this.elementData;    final int s = elementCount;    if (numNew > elementData.length - s)        elementData = grow(s + numNew);    int numMoved = s - index;    if (numMoved > 0)        System.arraycopy(elementData, index,                         elementData, index + numNew,                         numMoved);    System.arraycopy(a, 0, elementData, index, numNew);    elementCount = s + numNew;    return true;}

对于上面代码我们基本都分析过了在ArrayList中,所以下面的方法我不打算都贴出来了,直贴一个实现相较复杂的实现,我们已经贴出增加的方法,下面我们凑齐CRUD

remove

public boolean remove(Object o) {    return removeElement(o);}public synchronized boolean removeElement(Object obj) {    modCount++;    //indexOf方法就跟之前介绍的node方法一致,根据元素找出其位置    int i = indexOf(obj);    if (i >= 0) {        removeElementAt(i);        return true;    }    return false;}public synchronized void removeElementAt(int index) {  //检查索引    if (index >= elementCount) {        throw new ArrayIndexOutOfBoundsException(index + " >= " +                                                 elementCount);    }    else if (index < 0) {        throw new ArrayIndexOutOfBoundsException(index);    }    //j 就是要删除元素的位置    int j = elementCount - index - 1;    if (j > 0) {        System.arraycopy(elementData, index + 1, elementData, index, j);    }    modCount++;    elementCount--;    elementData[elementCount] = null; /* to let gc do its work */}

set

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

get

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

上面实现没得可说的了,很简单,从中我们可以看出,Vector和ArrayList的实现之差一个sync,所以Vector是线程安全的,但是由于是线程安全的,所以Vector要比ArrayList要慢,因为锁竞争的原因,并且Vector的实现也不好,因为一个操作只能是一个线程进行操作,这样当竞争高的时候会慢的要死.

Stack

从最上面的类图中可以看到Stack是基于Vector实现的,是其子类,Stack是用于模拟栈这种数据结构,是指后进先出LIFO的容器,最后push进栈的元素,将最先被pop出栈,我们来看一下实现

定义

publicclass Stack
    
      extends Vector
     
       {...}

属性

//由于父类Vector中的属性都是protected修饰,所以本类的属性就是使用了继承下来的Vector类中的属性

初始化

public Stack() {}

push

自身的方法比较少,但是有些方法是直接调用了父类的默认实现,以提高代码的复用性,我们可以都来看一下

Stack:public E push(E item) {    addElement(item);    return item;}Vector:public synchronized void addElement(E obj) {    modCount++;    add(obj, elementData, elementCount);}

add的实现就是从数组头开始一直加嘛,所以Stack就是这样的,依次往数组中添加

pop

public synchronized E pop() {    E obj;    //Vector:size    int len = size();    //Stack:peek    obj = peek();    //Vector:removeElementAt之前有贴实现的源代码    removeElementAt(len - 1);    return obj;}

peek

public synchronized E peek() {    Vector:size    int len = size();    if (len == 0)        throw new EmptyStackException();    Vector:elemenAt方法是将len-1位置上的数据返回但是不删除    return elementAt(len - 1);}

search

public synchronized int search(Object o) {    //Vector:lastIndexOf,从0开始一直往后循环搜索,遇到第一个相等的返回相同元素的index    int i = lastIndexOf(o);    if (i >= 0) {        return size() - i;    }    //代表不存在    return -1;}

这就是一些核心的方法了,实现起来还是很简单的,所以我就没有很大篇幅的一句句注释,但是需要注意的是,Stack的出入栈都是Object的,那么Stack是一种栈结构,我们除了使用Stack,也可以考虑ArrayDeque

ArrayDeque底层是基于数组实现的,所以其性能也是很好的

队列和栈

说到了上面的Stack实现类,那么我们就应该再去了解一下,看看List中有哪些实现类可以直接拿过来当做队列或者栈使用,我们之前介绍的LinkedList就可以,我们已经分析过了,所以我们这就不再详细说LinkedList了

我们看一张类图

markdown_img_paste_20190128153123956

Queue代表队列的抽象,而Deque是其一个子类,其进一步扩充了Queue的方法,Deque就既可以实现栈又可以实现队列了,我们分别看一下其中的方法定义
```
Queue:boolean add(E e);boolean offer(E e);E remove();E poll();E element();E peek();
```

上面一些方法的作用和区别如下,摘自

add()和offer()都是向队列中添加一个元素。一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空，调用remove() 的行为与 Collection 接口的版本相似会抛出异常，但是新的 poll() 方法在用空集合调用时只是返回 null。因此新的方法更适合容易出现异常条件的情况。element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

然后是Deque的方法

void push(E e);E pop();void addFirst(E e);...

方法较多,但是我们从push和pop已经看出,Deque接口已经为我们定义了栈的操作,所以我们可以使用Deque的具体实现类来完成栈和队列的操作,我们在这使用的是ArrayDeque

public static void main(String[] args) throws Exception {    Deque
      
        queue = new ArrayDeque<>();    queue.offer("A");    queue.offer("B");    queue.offer("C");    System.out.println(queue.poll());    System.out.println(queue.poll());    System.out.println(queue.poll());    //ABC    Deque
       
         stack = new ArrayDeque<>();    stack.push("A");    stack.push("B");    stack.push("C");    System.out.println(stack.pop());    System.out.println(stack.pop());    System.out.println(stack.pop());    //CBA}

在这我先不仔细分析ArrayDeque类,打算再单独写一下这个类,现在我们只要知道他可以作为栈或者队列就可以了

还有一种队列,是有序队列,如PriorityQueue,下面是他的实现方法,既然是保证了元素的有序,那么添加进入的元素肯定是实现Comparable接口的,这里所说的有序不是加入顺序,而是排列顺序,所以这个类就可以定制排序了,下面只是介绍一下使用方法,具体的分析我会跟ArrayDeque一起写出来的.
```
PriorityQueue
      
        queue = new PriorityQueue<>();queue.add(1);queue.add(10);queue.add(3);queue.add(7);//[1, 7, 3, 10]System.out.println(queue);int size = queue.size();for (int i = 0; i < size; i++) {    //1 3 7 10    System.out.println(queue.poll());}
      
```

然后是定制排序

Comparator
      
        comparator = (x,y) -> - Integer.compare(x,y);

将上面对象传入构造参数中就可以实现数值的从大到小输出

各种线性表的性能分析

Java提供的List就是一个线性表接口,而ArrayList,LinkedList又是线性表的两种典型实现:基于数组的线性表和基于链的线性表.Queue代表了队列,Deque代表了双端队列,既可以作为队列使用,又可以当做栈使用

LinkedList集合不仅提供了List的功能,还提供了双端队列,栈的功能

一般来说,由于数组以一块连续内存区来保存所有的数组元素,所以数组在随机访问时性能最好,所有的内部以数组作为底层实现的集合在随机访问时性能都比较好.而内部以链表作为底层实现的集合在执行插入,删除操作时有较好的性能.但总体来说,ArrayList的性能比LinkedList的性能要好.因此大部分时候都应该考虑使用ArrayList.

使用List集合的一些建议
- 如果需要遍历List集合,对于ArrayList,Vector集合,应该是用随机访问方法get来遍历集合元素,这样性能更好.对于LinkedList集合,则应该采用迭代器Iterator来遍历集合元素.
- 如果需要经常执行插入,删除操作来改变含大量数据的List集合的大小,则可考虑使用LinkedList集合,使用ArrayList,Vector集合可能需要经常分配内部数组的大小.效果可能较差.
- 如果有多个线程需要访问List集合中的元素,需要考虑使用Collections将几个包装成线程安全集合.