源码阅读之Java栈的实现

简介: 栈是 Last-In-First-Out (后进先出)的线性表。对栈的操作主要有两个:入栈(push)和出栈(pop)。因此它也是一种操作受限的线性表。尽管如此,它在计算机中应用非常广泛,是一种非常基础的数据结构。

0x00 栈

栈是 Last-In-First-Out (后进先出)的线性表。对栈的操作主要有两个:入栈(push)和出栈(pop)。因此它也是一种操作受限的线性表。尽管如此,它在计算机中应用非常广泛,是一种非常基础的数据结构。

0x01 源码

从源码中可以看出栈也是一种非常简单的数据结构。栈的源码非常简洁,只有100多行代码。

public class Stack<E> extends Vector<E> {
     
    public Stack() {
    }

    //入栈操作
    public E push(E item) {
        addElement(item);

        return item;
    }

    //出栈操作
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    //查看栈元素,不会删除
    public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }

    //检查是否为空栈
    public boolean empty() {
        return size() == 0;
    }

    //查找元素,如果找到则返回从栈顶开始计数的位置,否则返回-1
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

它继承于 Vector 类,这个跟前面讲的 ArrayList 是一样的,只不过 Vector 类方法是同步的,因此 Stack 也是线程安全的。

push

入栈

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

    return item;
}

虽然此方法没有声明 synchronized,但内部调用一个 addElement 来实现入栈操作。这个操作方法是在父类中实现的,它被声明为线程安全的,因此它也是线程安全的。

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

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//扩容方法
//这里跟 ArrayList 扩容算法有点不一样,ArrayList 一次是扩容为原来的1.5倍,Vector 默认扩容为原来的1倍
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

虽然 push 方法没有声明 synchronizedaddElement 方法中有。在这个方法里

  • 首先把 modCount 加 1,记录一次对数据结构的操作。
  • 然后检查数组容量是否足够,不够则扩容。
  • 最后把元素对象添加到数组末尾。

需要注意的是Vector的扩容策略是默认一次扩容为原来的1倍,这与ArrayList 一次扩容原来的1.5倍不同

pop

出栈

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

pop 方法被声明为 synchronized ,是线程安全的方法。它通过 peek 方法获取到栈顶元素对象,然后调用父类的 removeElementAt 方法把栈顶元素删除。

peek

查看栈顶元素

public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

这个方法也是线程安全的。可以看出如果栈的大小为0时,执行 peek 方法会抛出 EmptyStackException 异常。

search

在栈中搜索元素

public synchronized int search(Object o) {
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

继续查看父类代码

public synchronized int lastIndexOf(Object o) {
    return lastIndexOf(o, elementCount-1);
}

public synchronized int lastIndexOf(Object o, int index) {
    if (index >= elementCount)
        throw new IndexOutOfBoundsException(index + " >= "+ elementCount);

    if (o == null) {//如果查找的元素是空的则遍历找到最接近栈的空元素
        for (int i = index; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = index; i >= 0; i--)
            if (o.equals(elementData[i]))//通过equals方法来判断两个元素是否相同
                return i;
    }
    return -1;
}

在栈中查询一个元素需要遍历,时间复杂度为O(n)。

0x02 总结

栈是一种LIFO的数据结构,它基于 Vector 来实现,所有的方法都是线程安全的。入栈和出栈操作的时间复杂度为O(1),查找元素的时间复杂度为O(n)。

目录
相关文章
|
3天前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
16 2
|
8天前
|
人工智能 监控 数据可视化
Java智慧工地信息管理平台源码 智慧工地信息化解决方案SaaS源码 支持二次开发
智慧工地系统是依托物联网、互联网、AI、可视化建立的大数据管理平台,是一种全新的管理模式,能够实现劳务管理、安全施工、绿色施工的智能化和互联网化。围绕施工现场管理的人、机、料、法、环五大维度,以及施工过程管理的进度、质量、安全三大体系为基础应用,实现全面高效的工程管理需求,满足工地多角色、多视角的有效监管,实现工程建设管理的降本增效,为监管平台提供数据支撑。
24 3
|
13天前
|
运维 自然语言处理 供应链
Java云HIS医院管理系统源码 病案管理、医保业务、门诊、住院、电子病历编辑器
通过门诊的申请,或者直接住院登记,通过”护士工作站“分配患者,完成后,进入医生患者列表,医生对应开具”长期医嘱“和”临时医嘱“,并在电子病历中,记录病情。病人出院时,停止长期医嘱,开具出院医嘱。进入出院审核,审核医嘱与住院通过后,病人结清缴费,完成出院。
43 3
|
18天前
|
JavaScript Java 项目管理
Java毕设学习 基于SpringBoot + Vue 的医院管理系统 持续给大家寻找Java毕设学习项目(附源码)
基于SpringBoot + Vue的医院管理系统,涵盖医院、患者、挂号、药物、检查、病床、排班管理和数据分析等功能。开发工具为IDEA和HBuilder X,环境需配置jdk8、Node.js14、MySQL8。文末提供源码下载链接。
|
21天前
|
存储 算法 Java
🧠Java零基础 - Java栈(Stack)详解
【10月更文挑战第17天】本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
16 2
|
21天前
|
移动开发 前端开发 JavaScript
java家政系统成品源码的关键特点和技术应用
家政系统成品源码是已开发完成的家政服务管理软件,支持用户注册、登录、管理个人资料,家政人员信息管理,服务项目分类,订单与预约管理,支付集成,评价与反馈,地图定位等功能。适用于各种规模的家政服务公司,采用uniapp、SpringBoot、MySQL等技术栈,确保高效管理和优质用户体验。
|
1月前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
30 2
|
1月前
|
存储 前端开发 Java
Java后端如何进行文件上传和下载 —— 本地版(文末配绝对能用的源码,超详细,超好用,一看就懂,博主在线解答) 文件如何预览和下载?(超简单教程)
本文详细介绍了在Java后端进行文件上传和下载的实现方法,包括文件上传保存到本地的完整流程、文件下载的代码实现,以及如何处理文件预览、下载大小限制和运行失败的问题,并提供了完整的代码示例。
446 1
|
算法 Java
栈和队列【数据结构与算法Java】
栈和队列【数据结构与算法Java】
46 0
|
算法 Java
用栈实现队列(java数据结构与算法)
用栈实现队列(java数据结构与算法)
124 0