5 手写Java Stack 核心源码

九路
• 阅读 1546

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
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Easter79 Easter79
3年前
stack顺序存储结构
《偶刚开始学习数据结构,欢迎拍砖111》栈是只能通过访问它的一段来实现数据存储的一种线性数据结构,换句话来说就是先进后出的原则,FILO,与队列刚好相反哈,现在只说stack。栈包括以下几种基本运算(1)初始化(2)判断是否为空(3)push(4)pop(5)top其他的则根据这几种基本操作进行组合,即可实现。栈的实现同样
似梦清欢 似梦清欢
1年前
栈和队列
栈原理栈(stack)又名堆栈,是一种只能在表尾进行插入和删除操作的线性表。能够进行操作的这一端被称为栈顶,相对地,把另一端称为栈底。:::warning栈内元素操作时先进后出,类似于电梯上下成员,最后进去的人最先出
Stella981 Stella981
3年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Wesley13 Wesley13
3年前
Java 数据结构
简要本文主要介绍数据结构以及在Java中有哪些直接可用的数据结构(不涉及并发编程使用场景)。常见的数据结构下面直接介绍的常见的数据结构:数组(Array)、栈(Stack)、队列(Queue)、链表(LinkedList)、树(Tree)、堆(Heap)、散列表(Hash)、图(Graph)数组(Array)
Wesley13 Wesley13
3年前
Java 9 被无情抛弃,Java 8 直接升级到 Java 10!!
!(https://oscimg.oschina.net/oscnet/3e08a942dd884e9ab82b63a1f3c4aada.jpg"未命名文件.jpg")Java技术栈不可错过的Java 技术公众号!(https://oscimg.oschina.net/oscnet/00fcff52518e
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这