- 由于之前 对ArrayList和LinkedList的分析,所以在看Vector和Stack的源码实现就会非常简单
- 观察上图,我们可以看到本文要说的
Stack和Vector是父子关系,我们依旧从源码入手,期望能够对你有帮助,如果本文有理解不对的地方,请及时指正,谢谢您
Vector
- 我们知道Vector的实现和ArrayList一样,都是底层以数组的方式存储的,但是不同的Vector是线程安全的,这一点我们可以从源码中看出来
定义
@since 1.0
public class Vector<E>
extends AbstractList<E>
implements List<E>, 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<? extends E> 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<? extends E> 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出栈,我们来看一下实现
定义
public
class Stack<E> extends Vector<E> {...}属性
//由于父类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了
- 我们看一张类图
-
Queue代表队列的抽象,而Deque是其一个子类,其进一步扩充了Queue的方法,Deque就既可以实现栈又可以实现队列了,我们分别看一下其中的方法定义
Queue: boolean add(E e); boolean offer(E e); E remove(); E poll(); E element(); E peek(); -
上面一些方法的作用和区别如下,摘自 CSDN
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的具体实现类来完成栈和队列的操作,我们在这使用的是
ArrayDequepublic static void main(String[] args) throws Exception { Deque<String> 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<String> 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<Integer> 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<Integer> 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将几个包装成线程安全集合.
