5 手写Java Stack 核心源码

九路 等级 614 0 0
标签: 源码数组Java

Stack是Java中常用的数据结构之一,Stack具有"后进先出(LIFO)"的性质。 只能在一端进行插入或者删除,即压栈与出栈

栈的实现比较简单,性质也简单。可以用一个数组来实现栈结构。

  1. 入栈的时候,只在数组尾部插入
  2. 出栈的时候,只在数组尾部删除**

我们来看一下Stack的用法 :如下

  public static void main(String[] args){

        //新建一个栈
        Stack<String> stack = new Stack<>();

        //分别向栈中添加不同的元素
        stack.push("tom");
        stack.push("jim");
        stack.push("wendy");
        stack.push("natasha");

        //分别弹栈
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());

    }

输出如下:


natasha
wendy
jim
tom

从输出可以看到,最后入栈的,最先出栈

下面我们底层用数组也来实现这样一个栈,在数组的尾部插入和删除。 也就是入栈和出栈。如下图:

5 手写Java Stack 核心源码

完整的源码如下:


public class QStack<E> {
    //数组的默认大小为10
    private static final int DEFAULT_INIT_CAPACITY = 10;

    //底层的数组
    private Object[] elements;

    //栈中的个数
    private int size;

    public QStack() {
        this(DEFAULT_INIT_CAPACITY);
    }


    public QStack(int capacity) {
        //capacity条件检查 ,这里我们直接抛出异常
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity <= 0");
        }

        if (capacity > Integer.MAX_VALUE) {
            throw new IllegalArgumentException("capacity > Integer.MAX_VALUE");
        }

        //新建一个capacity大小的数组
        elements = new Object[capacity];

        //初始个数为0
        size = 0;
    }

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

    //返回栈中的元素个数
    public int size() {
        return size;
    }

    //将一个元素压入栈中
    public E push(E e) {
        //如果栈已满,进行扩容
        if (size >= elements.length) {
            grow();
        }

        //扩容完后将元素e压入栈中
        elements[size] = e;

        //别忘了size需要加 1
        size++;

        return e;
    }

    //出栈,就是将数组最后一个元素弹出
    public E pop() {
        //如果栈为空就返回null
        if (isEmpty()) {
            return null;
        }

        //拿到栈的大小
        int len = size();

        //把数组中最后一个元素保存起来
        E e = peek();
        //个数别忘了减1
        size--;

        //将最后一个元素置null
        elements[len - 1] = null;

        //返回e
        return e;
    }

    //返回最后一个元素
    public E peek() {
        int len = size();

        if (len == 0)
            throw new RuntimeException("stack is empty");

        return (E) elements[len - 1];
    }

    //扩容
    private void grow() {
        //将之前的数组保存
        int oldCapacity = elements.length;
        Object[] old = elements;

        //新的数组大小为原来数组大小的2倍
        int newCapacity = oldCapacity * 2;
        //再新建一个大小为原来数组2倍的新数组
        elements = new Object[newCapacity];

        //把以前的老的数组中的元素都移动新数组中
        for (int i = 0; i < oldCapacity; i++) {
            elements[i] = old[i];
        }

        //释放以前的内存空间
        old = null;
    }

}

以上面可知:用数组实现栈结构,主要需要注意以下 2 点:

  1. 在数组的尾部插入和删除,也就是压栈和弹栈
  2. 由于是用数组实现栈结构,数组满的时候,需要扩容

下面我们写一段测试代码来测试,如下:


   public static void main(String[] args){
        //创建一个栈
        QStack<String> stack = new QStack<>();

        //分别向栈中压入4个不同的元素
        stack.push("tom");
        stack.push("jim");
        stack.push("wendy");
        stack.push("natasha");

        //分别弹栈
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }

打印如下:


natasha
wendy
jim
tom
收藏
评论区

相关推荐

Gradle技术之四 - Gradle的Task详解
1 Gradle的Task详解 1 Task定义和配置 2 Task的执行 3 Task的依赖和执行顺序 4 Task类型 5 Task结合gradle的生命周期 6 Task实战 1.1 Task定义和配置 1.1.1 查看所有的task java ./gradlew tasks 输出 Task :tasks
5 手写Java Stack 核心源码
Stack是Java中常用的数据结构之一,Stack具有"后进先出(LIFO)"的性质。 只能在一端进行插入或者删除,即压栈与出栈 栈的实现比较简单,性质也简单。可以用一个数组来实现栈结构。 1. 入栈的时候,只在数组尾部插入 2. 出栈的时候,只在数组尾部删除 我们来看一下Stack的用法 :如下 public static void mai
Java中遍历HashMap的5种方式
本教程将为你展示Java中HashMap的几种典型遍历方式。 如果你使用Java8,由于该版本JDK支持lambda表达式,可以采用第5种方式来遍历。 如果你想使用泛型,可以参考方法3。如果你使用旧版JDK不支持泛型可以参考方法4。 1、 通过ForEach循环进行遍历 import java.io.IOException; import jav
Android经典面试题,也可以提升综合能力
基础问题相关 1、接口的意义百度 2、抽象类的意义百度 3、内部类的作用乐视 4、Java 虚拟机的特性百度乐视 5、哪些情况下的对象会被垃圾回收机制处理掉美团小米 6、进程和线程的区别猎豹美团 7、java中和equals和hashCode的区别乐视 8、HashMap的实现原理美团 9、stringst
Groovy初探
开始之前 了解本教程的主要内容,以及如何从中获得最大收获。 关于本教程 如果现在有人要开始完全重写 Java,那么 Groovy 就像是 Java 2.0。Groovy 并没有取代 Java,而是作为 Java 的补充,它提供了更简单、更灵活的语法,可以在运行时动态地进行类型检查。您可以使用 Groovy 随意编写 Java 应用程序,连接 Java
IO编程实例——使用缓冲流实现文件的拷贝
数据源:"C:\\Users\\你是小朱老师呀\\Desktop\\test.txt"数据的目的地: "C:\\Users\\你是小朱老师呀\\Desktop\\XSC\\test.txt"实现步骤:1.创建源文件与目标文件2.创建节点流3.创建缓冲流4.读取、写入5.释放 package person.xsc.praticeIII;import java.
Java开发面试高频考点学习笔记(每日更新)
Java开发面试高频考点学习笔记(每日更新) 1.深拷贝和浅拷贝 2.接口和抽象类的区别 3.java的内存是怎么分配的 4.java中的泛型是什么?类型擦除是什么? 5.Java中的反射是什么 6.序列化与反序列化 7.Object有哪些方法? 8.JVM内存模型 9.类加载机制 10.对象的创建和对象的布局 11.Java的四种引用
2021年度最全面JVM虚拟机,类加载过程与类加载器
前言类装载器子系统是JVM中非常重要的部分,是学习JVM绕不开的一关。一般来说,Java 类的虚拟机使用 Java 方式如下:Java 源程序(.java 文件)在经过 Java 编译器编译之后就被转换成 Java 字节代码(.class 文件)。类加载器负责读取 Java 字节代码,并转换成 java.lang.Class类的一个实例。每个这样的实例用来表
秋招已经开始准备了!【Java面试题】最新Java开发岗面试知识笔记
在最近两个月不断的面试中,我分类总结了 Java 开发岗位面试中的一些知识点。主要包括以下几个部分: 1. Java 基础知识点 2. Java 常见集合 3. 高并发编程(JUC 包) 4. JVM 内存管理 5. Java 8 知识点 6. 网络协议相关 7. 数据库相关 8. MVC 框架相关 9. 大数据相关 10. Linux 命令相关面试,
2021年度最全面JVM虚拟机,类加载过程与类加载器
前言类装载器子系统是JVM中非常重要的部分,是学习JVM绕不开的一关。一般来说,Java 类的虚拟机使用 Java 方式如下:Java 源程序(.java 文件)在经过 Java 编译器编译之后就被转换成 Java 字节代码(.class 文件)。类加载器负责读取 Java 字节代码,并转换成 java.lang.Class类的一个实例。每个这样的实例用来表
2021年Java常见面试题目,100%好评!
专题1:JavaOOP 1、什么是B/S架构?什么是C/S架构 2、Java都有哪些开发平台? 3、什么是JDK?什么是JRE? 4、Java语言有哪些特点 5、面向对象和面向过程的区别 6、什么是数据结构? 7、Java的数据结构有哪些? 8、什么是OOP? 9、类与对象的关系? 10、Java中有几种数据类型
首发10万字Java开发实战文档,涨姿势了!
Java基础1Java语言的三大特性2.Java语言主要特性3\. JDK和JRE有什么区别4.Java基本数据类型及其封装类5.如果main方法被声明为private会怎样?6.说明 下public static void main(String argsQ])这段声明里每个关键字的作用7.与equals的区别8.Object有哪些公用方法9.为什么Jav
五面阿里巴巴拿offer后定级P6:分享Java面经及答案总结
一面(电话)说说对JVM的理解treemap和hashmap有什么区别?Java多线程的的5大状态图流转mysql主键和唯一索引的区别说说最近的项目如何实现session共享,用redis如何实现缓存击穿的概念和解决方案说说微服务,微服务之间如何管理二面(现场)java nio常?用的三个类java里面的同步锁了解吗?Countdownlauch和Cylic
腾讯T3团队整理,持续更新中
Java基础1.JAVA 中的几种数据类型是什么,各自占用多少字节。2.String 类能被继承吗,为什么。3\. 两个对象的 hashCode() 相同,则 equals() 也一定为 true,对吗?4\. String 属于基础的数据类型吗?5.Java 中操作字符串都有哪些类?它们之间有什么区别?6.Java 中 IO 流分为几种?7.BIO、NIO
踩坑了!熬夜整理小米Android面试题
一、Java初中级面试题1.容器(HashMap、HashSet、LinkedList,HashSet等)2.内存模型3.JVM、Davilk、ART 三者的原理和区别4.垃圾回收机制5.类加载方案6.说说你对Java 反射的理解7.说说你对动态代理的理解8.什么是线程池,如何使用?为什么要使用线程池?9.在多线程运行过程中,解决安全性问题?10.设计模式(