5 手写Java Stack 核心源码

九路 等级 1011 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
收藏
评论区

相关推荐

5 手写Java Stack 核心源码
Stack是Java中常用的数据结构之一,Stack具有"后进先出(LIFO)"的性质。 只能在一端进行插入或者删除,即压栈与出栈 栈的实现比较简单,性质也简单。可以用一个数组来实现栈结构。 1. 入栈的时候,只在数组尾部插入 2. 出栈的时候,只在数组尾部删除 我们来看一下Stack的用法 :如下 public static void mai
1、简单排查java应用CPU飙高的线程问题
### **1\. 获取要查看的进程的ID** > ps aux | grep xxx ### **2\. 查看此进程下的线程信息** > * top -H -p <pid> > * top -p <pid>      按shift+h > * top -Hp <pid>        ### **3\. 查看栈信息** > jstac
JAVA中的栈和堆【转】
 原文链接 https://www.cnblogs.com/ibelieve618/p/6380328.html JAVA在程序运行时,在内存中划分5片空间进行数据的存储。分别是:1:寄存器。2:本地方法区。3:方法区。4:栈。5:堆。 基本,栈stack和堆heap这两个概念很重要,不了解清楚,后面就不用学了。 以下是这几天栈和堆的学习记录和心得。得
Java8内存模型
<div class="htmledit\_views"> <h1><a name="t0"></a>一、JVM内存模型</h1> <p></p> <p><span style="font-family:'宋体';">内存空间</span>(Runtime Data Area)中可以按照是否线程共享分为两块,线程共享的是方法区(Method Area)和堆
Java中的集合
Java Collections Framework是Java编程语言的核心部分之一。集合几乎用于任何编程语言中。大多数编程语言都支持各种类型的集合,例如List, Set, Queue, Stack等。 ### 1.什么是Java Collections Framework? 集合就像容器一样,将多个项目组合在一个单元中。例如,一罐巧克力,一组名称等。
Java收入不再最低,Python被TypeScript击败,开发者调查报告出炉
  机器之心报道   **参与:魔王、杜伟** > Stack Overflow 2020 年度全球开发者调查报告出炉。报告显示,JavaScript 连续八年成为最常用的编程语言,而在最受开发者喜爱的编程语言榜单中,Python 排名第三,较去年下降一位,被 TypeScript 超越。另一值得关注的结果是,Java 语言的薪酬收入不再是最低了。
Java线程Dump分析工具
jstack用于打印出给定的java进程ID或core file或远程调试服务的Java堆栈信息,如果是在64位机器上,需要指定选项"-J-d64",Windows的jstack使用方式只支持以下的这种方式: jstack [-l][F] pid 如果java程序崩溃生成core文件,jstack工具可以用来获得core文件的java
Java集合详解1:一文读懂ArrayList,Vector与Stack使用方法和实现原理
本文非常详尽地介绍了Java中的三个集合类 ArrayList,Vector与Stack 《Java集合详解系列》是我在完成夯实Java基础篇的系列博客后准备开始写的新系列。 这些文章将整理到我在GitHub上的《Java面试指南》仓库,更多精彩内容请到我的仓库里查看 > [https://github.com/h2pl/Java-Tutorial](
Java面试170题
1、面向对象的特征有哪些方面? 2、访问修饰符public,private,protected,以及不写(默认)时的区别? 3、String 是最基本的数据类型吗? 4、float f=3.4;是否正确? 5、short s1 = 1; s1 = s1 + 1;有错吗?short s1 = 1; s1 += 1;有错吗? 6、Java有没有goto
Java面试之容器
#### 18\. Java 容器都有哪些? Java 容器分为 Collection 和 Map 两大类,其下又有很多子类,如下所示: * Collection * List * ArrayList * LinkedList * Vector * Stack * Set * Has
Java,JavaScript和ABAP通过代码取得当前代码的调用栈Callstack
Java ==== StackTraceElement stack[] = Thread.currentThread().getStackTrace(); System.out.println("Callstack test"); for(int i = 0; i < stack.length; i++
thirft with php(一)
###About thrift --------------- The Apache Thrift software framework, for scalable cross-language services development, combines a software stack with a code generation engine to
160道Java技术面试题
1、面向对象的特征有哪些方面? 2、访问修饰符public,private,protected,以及不写(默认)时的区别? 3、String 是最基本的数据类型吗? 4、float f=3.4;是否正确? 5、short s1 = 1; s1 = s1 + 1;有错吗?short s1 = 1; s1 += 1;有错吗? 6、Java有没
160道Java技术面试题
1、面向对象的特征有哪些方面? 2、访问修饰符public,private,protected,以及不写(默认)时的区别? 3、String 是最基本的数据类型吗? 4、float f=3.4;是否正确? 5、short s1 = 1; s1 = s1 + 1;有错吗?short s1 = 1; s1 += 1;有错吗? 6、Java有没
JVM内存模型和类加载机制
### JVM内存模型 Java代码是运行在Java虚拟机(JVM)上的,Java虚拟机通过解释执行(解释器)或编译执行(编译器)来完成。 Java内存模型分为5个部分:方法区(Method Area),Java堆(Heap),Java栈(VM Stack),本地方法栈(Native Method Stack),程序计数器(PC 寄存器) ![](ht