乐趣区

关于java:java集合13-Stack源码分析走一波

前言

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

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

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

Stack 介绍

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

以下是栈的个性演示:

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

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

类定义源码:

public
class 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 办法

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

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

总结

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

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

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

剑指 Offer 全副题解 PDF

开源编程笔记

退出移动版