java集合【13】——— Stack源码分析走一波

前言

集合源码分析系列:Java集合源码分析

前面已经把Vector,ArrayList,LinkedList分析完了,本来是想开始Map这一块,但是看了下面这个接口设计框架图:整个接口框架关系如下(来自百度百科):

原来还有一个漏网之鱼,Stack栈的是挂在Vector下,前面我们已经分析过Vector了,那么顺便把Stack分析一遍。再不写就2022年了:

java集合【13】——— Stack源码分析走一波_第1张图片

Stack介绍

栈是一种数据结构,并不是Java特有的,在Java里面体现是Stack类。它的本质是先进后出,就像是一个桶,只能不断的放在上面,取出来的时候,也只能不断的取出最上面的数据。要想取出底层的数据,只有等到上面的数据都取出来,才能做到。当然,如果有这种需求,我们一般会使用双向队列。

以下是栈的特性演示:

java集合【13】——— Stack源码分析走一波_第2张图片

StackJava中是继承于Vector,这里说的是1.8版本,共用了Vector底层的数据结构,底层都是使用数组实现的,具有以下的特点:

  • 先进后出(`FILO
  • 继承于Vector,同样基于数组实现
  • 由于使用的几乎都是VectorVector的操作都是线程安全的,那么Stack操作也是线程安全的。

类定义源码:

public
class Stack extends Vector {
}

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

    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 方法

获取栈顶元素,先获取数组的大小,然后再调用VectorE 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;

底层使用数组,保存了元素的个数,那么操作元素其实只是不断往数组中插入元素,或者取出最后一个元素即可。

java集合【13】——— Stack源码分析走一波_第3张图片

总结

stack 由于继承了Vector,因此也是线程安全的,底层是使用数组保存数据,大多数API都是使用Vector来保存。它最重要的属性是先进先出。至于数组扩容,沿用了Vector中的扩容逻辑。

如果让我们自己实现,底层不一定使用数组,使用链表也是能实现相同的功能的,只是在整个集合源码体系中,共有相同的部分,是不错的选择。

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

剑指Offer全部题解PDF

开源编程笔记

你可能感兴趣的