秦怀杂货店

General Store

  • 首页
  • 文章归档
  • 标签
  • 分类
  • 关于页面

  • 搜索
随便聊聊 数据结构 小游戏 数据库 Docker Springboot 系统设计 雪花算法 分布式 海量ip 最长回文子串 算法 面试题 线程池 多线程 线程 java学习 布隆过滤器 github 架构设计 docsify Git JVM LeetCode 杂货思考 设计模式 Lambda native isAssignableFrom 反射 剑指Offer mybatis SPI JDBC 编程工具 Java基础 集合

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

发表于 2022-01-10 | 分类于 Java集合 | 0 | 阅读次数 176

前言

集合源码分析系列: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操作也是线程安全的。

类定义源码:

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/java-ji-he-11vector-chao-ji-xiang-xi-yuan-ma-jie-xi

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

开源编程笔记

  • 本文作者: 秦怀杂货店
  • 本文链接: http://aphysia.cn/archives/java-ji-he-13stack-yuan-ma-fen-xi-zou-yi-bo
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 随便聊聊 # 数据结构 # 小游戏 # 数据库 # Docker # Springboot # 系统设计 # 雪花算法 # 分布式 # 海量ip # 最长回文子串 # 算法 # 面试题 # 线程池 # 多线程 # 线程 # java学习 # 布隆过滤器 # github # 架构设计 # docsify # Git # JVM # LeetCode # 杂货思考 # 设计模式 # Lambda # native # isAssignableFrom # 反射 # 剑指Offer # mybatis # SPI # JDBC # 编程工具 # Java基础 # 集合
设计模式【10】-- 顺便看看享元模式
无聊的周末用Java写个扫雷小游戏
  • 文章目录
  • 站点概览
秦怀杂货店

秦怀杂货店

纵然缓慢,驰而不息。

145 日志
19 分类
37 标签
Github E-mail
Creative Commons
0%
© 2022 秦怀杂货店
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4