专栏首页后端Coderjava进阶|Stack源码解析和理解

java进阶|Stack源码解析和理解

Stack这个数据结构还是比较容易理解的,满足LIFO,即先进后出,看下它的结构图,然后分析一下源码进行理解一下。

咦,Stack栈继承Vector类,然后复用了其中的方法,就实现了栈这种push(),pop()方法的使用,优秀。

看下栈Stack的类结构,确实是继承了Vector这个类。

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

首先看下,如何创建一个栈Stack,默认提供了一个无参构造函数。

    /**     * Creates an empty Stack.     */    public Stack() {//构建一个空参    }

将数据元素放入栈中,其实是放入了动态数组中,底层调用了Vector类的方法。

 public E push(E item) {        addElement(item);
        return item; } 步骤一:public synchronized void addElement(E obj) {//这个讲解见Vector源码分析        modCount++;        ensureCapacityHelper(elementCount + 1);        elementData[elementCount++] = obj; } 

我们看下如何在不弹出栈中元素数据的情况下,如何获取栈顶元素。可以使用peek()方法。

public synchronized E peek() {        int     len = size();//获取当前栈中元素个数
        if (len == 0)            throw new EmptyStackException();        return elementAt(len - 1);    } 步骤一:public synchronized E elementAt(int index) {        if (index >= elementCount) {            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);        }
        return elementData(index);//获取指定索引位置的元素    }

看下Stack中弹出栈顶元素pop()方法,size减一。

public synchronized E pop() {        E       obj;        int     len = size();
        obj = peek();        removeElementAt(len - 1);//这里是移除指定位置的元素方法
        return obj;    } 步骤一: 删除指定位置元素为null,使用gc进行null值数据的垃圾收集,但是垃圾收集时间不确定 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()和pop()方法的区别。

获取栈Stack中元素个数的方法:size()。

public synchronized int size() {        return elementCount;//复用了vector容器获取size方法。    }

判断栈Stack是否为空的方法:isEmpty()。

public synchronized boolean isEmpty() {        return elementCount == 0;//也是复用了vector元素个数与0的对比。    }

判断指定元素是否在栈Stack中存在search()方法。

public synchronized int search(Object o) {        int i = lastIndexOf(o);//获取指定元素的下标位置,由于栈是先进后出的结构,所以这里使用了lastIndexOf()
        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]))                    return i;        }        return -1;    }

以上就是对栈Stack这种LIFO结构的源码进行解析和理解,到这里就结束了,关于源码走读的示例程序,这里自己也简单的提供一下。

package com.wpw.springbootjuc.java8.map;
import lombok.extern.slf4j.Slf4j;
import java.util.Stack;
/** * 栈源码走读 * * @author wpw */@Slf4jpublic class StackTest {    public static void main(String[] args) {        Stack<Integer> stack = new Stack<>();        stack.push(1);        stack.push(2);        stack.push(3);        log.info("循环输出栈中的元素");        stack.stream().forEachOrdered(item -> System.out.print(item + "\t"));        System.out.println();        log.info("Stack中peek()方法的测试");        Integer item = stack.peek();        System.out.println("item = " + item);        log.info("获取栈中元素个数:[{}]", stack.size());        System.out.println();        log.info("Stack中pop()方法的测试");        Integer itemPop = stack.pop();        System.out.println("itemPop = " + itemPop);        log.info("获取栈中元素个数:[{}]", stack.size());        System.out.println();        log.info("判断Stack是否为空:{}", stack.isEmpty());        log.info("查找指定元素是否在Stack中存在:[{}]", stack.search(3));    }}

理解Vector源码是进一步理解栈这种结构的前面铺垫,关于Vector源码解析的文章可以参考历史文章。这里贴下Stack的结构方法。

本文分享自微信公众号 - WwpwW(gh_245290c1861a),作者:后端Coder

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode70|最小K个数

    排序在整个工作中还是比较的常用的一种场景,排序的目的是为了更加高效的检索自己需要的数据,对于数据库优化,为什么要加索引,难道不是为了更加高效的检索自己需要的数据...

    后端Coder
  • LeetCode134|插入区间

    给出一个无重叠的 ,按照区间起始端点排序的区间列表。在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

    后端Coder
  • java进阶|Vector源码分析和理解

    这一篇文章算是从java基础性文章结束到进阶的一个过渡,虽然自己从未使用过Vector这样的容器进行数据的增删改查操作,但还是按照一贯的思路进行分析一...

    后端Coder
  • 关于栈的简单应用的小例子

    栈是一种只允许在一端进行插入和删除操作的线性表。在栈中,进行操作的一端叫做栈顶,相应地,另一端称为栈底。

    Reborn Lee
  • 栈的基本操作就是出栈和入栈,这两个的时间复杂度都是O(1) 数据结构 typedef struct Stack{ int data[MAXSIZE]; ...

    用户1154259
  • C++中的stack类、QT中的QStack类

    C++中的stack 实现一种先进后出的数据结构,是一个模板类. 头文件 #include<stack> 用法(以int型为例): stack <int> s;...

    张诺谦
  • 顺丰科技算法笔试题解:学术交流(并查集)

    由于题目是让求出需要翻译机的个数,一共有m个人,并且每个人可能一种语言都不会,也有可能会多种语言!因此,一个很通用的思路我们将可以互相交流的放到一个集合中,最终...

    算法工程师之路
  • 全国计算机二级C语言考试知识点及2009样题

    用C语言编写的程序称为C语言源程序,源程序文件的后缀名为“.c”。源程序经编译后生成后缀名为“.obj”的目标文件,再把目标文件与各种库函数连接起来,生成“....

    用户6755376
  • F-Stack Q&A 第二期

    Q1:请问再视频领域,媒体服务器,使用F-Stack是否合适? A1:F-Stack在纯推流的模式上是支持且合适的,如果有转码服务等计算密集型服务,需要等我们支...

    F-Stack
  • 每天一道剑指offer-包含min函数的栈

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里

扫码关注云+社区

领取腾讯云代金券