前言

汇合源码剖析系列：Java汇合源码剖析

后面曾经把Vector,ArrayList,LinkedList剖析完了，原本是想开始Map这一块，然而看了上面这个接口设计框架图：整个接口框架关系如下（来自百度百科）：

原来还有一个漏网之鱼，Stack栈的是挂在Vector下，后面咱们曾经剖析过Vector了，那么顺便把Stack剖析一遍。再不写就2022年了：

Stack介绍

栈是一种数据结构，并不是Java特有的，在Java外面体现是Stack类。它的实质是先进后出，就像是一个桶，只能一直的放在下面，取出来的时候，也只能一直的取出最下面的数据。要想取出底层的数据，只有等到下面的数据都取出来，能力做到。当然，如果有这种需要，咱们个别会应用双向队列。

以下是栈的个性演示：

Stack在Java中是继承于Vector，这里说的是1.8版本，共用了Vector底层的数据结构，底层都是应用数组实现的，具备以下的特点：

先进后出（`FILO）
继承于Vector,同样基于数组实现
因为应用的简直都是Vector，Vector的操作都是线程平安的，那么Stack操作也是线程平安的。

类定义源码：

publicclass Stack<E> extends Vector<E> {}

成员变量只有一个序列化的变量：

    private static final long serialVersionUID = 1224463164541339165L;

办法解读

Stack没有太多本人的办法，简直都是继承于Vector，咱们能够看看它本人拓展的 5 个办法：

E push(E item): 压栈
synchronized E pop(): 出栈
synchronized E peek():获取栈顶元素
boolean empty():判断栈是不是为空
int search(Object o): 搜寻某个对象在栈中的索引地位

push 办法

在底层实际上调用的是addElement()办法，这是Vector的办法：

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

在后面咱们曾经剖析过Vecor的源码，感兴趣能够参考：http://aphysia.cn/archives/ja...

addElement是线程平安的，在底层实际上就是往数组前面增加了一个元素，然而它帮咱们保障了容量，如果容量有余，会触发主动扩容机制。

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

pop 办法

底层是先调用peek()办法，获取到栈顶元素，再调用removeElementAt（）办法移除掉栈顶元素，实现出栈成果。

    public synchronized E pop() {        E       obj;        int     len = size();        obj = peek();        removeElementAt(len - 1);        return obj;    }

removeElementAt(int index)也是Vector的办法，synchronized润饰，也是线程平安的，因为移除的是数组最初的元素，所以在这里不会触发元素复制，也就是System.arraycopy(elementData, index + 1, elementData, index, j);:

    public synchronized void removeElementAt(int index) {        modCount++;        if (index >= elementCount) {            throw new ArrayIndexOutOfBoundsException(index + " >= " +                                                     elementCount);        }        else if (index < 0) {            throw new ArrayIndexOutOfBoundsException(index);        }        int j = elementCount - index - 1;        if (j > 0) {            System.arraycopy(elementData, index + 1, elementData, index, j);        }        elementCount--;        elementData[elementCount] = null; /* to let gc do its work */    }

peek 办法

获取栈顶元素，先获取数组的大小，而后再调用Vector的E elementAt(int index)获取该索引的元素：

    public synchronized E peek() {        int     len = size();        if (len == 0)            throw new EmptyStackException();        return elementAt(len - 1);    }

E elementAt(int index)的源码如下,外面逻辑比较简单，只有数组越界的判断：

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

empty 办法

次要是用来判空，判断元素栈外面有没有元素，次要调用的是size()办法：

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

这个size()办法其实也是Vector的办法，返回的其实也是一个类变量，元素的个数：

    public synchronized int size() {        return elementCount;    }

search办法

这个办法次要用来查问某个元素的索引，如果外面存在多个，那么将会返回最初一个元素的索引：

   public synchronized int search(Object o) {        int i = lastIndexOf(o);        if (i >= 0) {            return size() - i;        }        return -1;    }

应用synchronized润饰，也是线程平安的，为什么须要这个办法呢？

咱们晓得栈是先进先出的，如果须要查找一个元素在其中的地位，那么须要一个个取出来再判断，那就太麻烦了，而底层应用数组进行存储，能够间接利用这个个性，就能够疾速查找到该元素的索引地位。

至此，回头一看，你是否会感到纳闷，`Stack外面没有任何的数据，然而却一直的在操作数据，这得益于Vector的数据结构：

        // 底层数组    protected Object[] elementData;    // 元素数量    protected int elementCount;

底层应用数组，保留了元素的个数，那么操作元素其实只是一直往数组中插入元素，或者取出最初一个元素即可。

总结

stack 因为继承了Vector，因而也是线程平安的，底层是应用数组保留数据，大多数API都是应用Vector来保留。它最重要的属性是先进先出。至于数组扩容，沿用了Vector中的扩容逻辑。

如果让咱们本人实现，底层不肯定应用数组，应用链表也是能实现雷同的性能的，只是在整个汇合源码体系中，共有雷同的局部，是不错的抉择。

【作者简介】：
秦怀，公众号【秦怀杂货店】作者，集体网站：http://aphysia.cn，技术之路不在一时，山高水长，纵使迟缓，驰而不息。

剑指Offer全副题解PDF

开源编程笔记