`
frank-liu
  • 浏览: 1682598 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

java stack的详细实现分析

 
阅读更多

简介

    我们最常用的数据结构之一大概就是stack了。在实际的程序执行,方法调用的过程中都离不开stack。那么,在一个成熟的类库里面,它的实现是怎么样的呢?也许平时我们实践的时候也会尝试着去写一个stack的实现玩玩。这里,我们就仔细的分析一下jdk里的详细实现。

Stack

    如果我们去查jdk的文档,我们会发现stack是在java.util这个包里。它对应的一个大致的类关系图如下:

    通过继承Vector类,Stack类可以很容易的实现他本身的功能。因为大部分的功能在Vector里面已经提供支持了。

Stack里面主要实现的有一下几个方法:

方法名 返回类型 说明
empty boolean 判断stack是否为空。
peek E 返回栈顶端的元素。
pop E 弹出栈顶的元素
push E 将元素压入栈
search int 返回最靠近顶端的目标元素到顶端的距离。

    因为前面我们已经提到过,通过继承Vector,很大一部分功能的实现就由Vector涵盖了。Vector的详细实现我们会在后面分析。它实现了很多的辅助方法,给Stack的实现带来很大的便利。现在,我们按照自己的思路来分析每个方法的具体步骤,再和具体实现代码对比。

empty

    从我们的思路来说,如果要判断stack是否为空,就需要有一个变量来计算当前栈的长度,如果该变量为0,则表示该栈为空。或者说我们有一个指向栈顶的变量,如果它开始的时候是设置为空的,我们可以认为栈为空。这部分的实现代码也很简单:

public boolean empty() {
    return size() == 0;
}

 如果更进一步分析的话,是因为Vector已经实现了size()方法。在Vector里面有一个变量elementCount来表示容器里元素的个数。如果为0,则表示容器空。这部分在Vector里面的实现如下:

public synchronized int size() {
    return elementCount;
}

 

peek

    peek是指的返回栈顶端的元素,我们对栈本身不做任何的改动。如果栈里有元素的话,我们就返回最顶端的那个。而该元素的索引为栈的长度。如果栈为空的话,则要抛出异常:

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

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

 这个elementAt方法也是Vector里面的一个实现。在Vector里面,实际上是用一个elementData的Object数组来存储元素的。所以要找到顶端的元素无非就是访问栈最上面的那个索引。它的详细实现如下:

public synchronized E elementAt(int index) {
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
    }

    return elementData(index);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

pop

    pop方法就是将栈顶的元素弹出来,如果栈里有元素,就取最顶端的那个,否则就要抛出异常:

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

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

    return obj;
}

    在这里,判断是否可以取栈顶元素在peek方法里实现了,也将如果栈为空则抛异常的部分包含在peek方法里面。这里有必要注意的一个细节就是,在通过peek()取到顶端的元素之后,我们需要用removeElementAt()方法将最顶端的元素移除。我们平时可能不太会留意到这一点。为什么要移除呢?我们反正有一个elementCount来记录栈的长度,不管它不是也可以吗?

    实际上,这么做在程序运行的时候会有一个潜在的内存泄露的问题。因为在java里面,如果我们普通定义的类型属于强引用类型。比如这里vector就底层用的Object[]这个数组强类型来保存数据。强类型在jvm中做gc的时候,只要程序中有引用到它,它是不会被回收的。这就意味着在这里,只要我们一直在用着stack,那么stack里面所有关联的元素就都别想释放了。这样运行时间一长就会导致内存泄露的问题。那么,为了解决这个问题,这里就是用的removeElementAt()方法。

 

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 */
}

     这个方法实现的思路也比较简单。就是用待删除元素的后面元素依次覆盖前面一个元素。这样,就相当于将数组的实际元素长度给缩短了。因为这里这个移除元素的方法是定义在vector中间,它所面对的是一个更加普遍的情况,我们移除的元素不一定就是数组尾部的,所以才需要从后面依次覆盖。如果只是单纯对于一个栈的实现来说,我们完全可以直接将要删除的元素置为null就可以了。

push

    push的操作也比较直观。我们只要将要入栈的元素放到数组的末尾,再将数组长度加1就可以了。

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

    return item;
}

    这里,addElement方法将后面的细节都封装了起来。如果我们更加深入的去考虑这个问题的话,我们会发现几个需要考虑的点。1. 首先,数组不会是无穷大的 ,所以不可能无限制的让你添加元素下去。当我们数组长度到达一个最大值的时候,我们不能再添加了,就需要抛出异常来。2. 如果当前的数组已经满了,实际上需要扩展数组的长度。常见的手法就是新建一个当前数组长度两倍的数组,再将当前数组的元素给拷贝过去。前面讨论的这两点,都让vector把这份心给操了。我们就本着八卦到底的精神看看它到底是怎么干的吧:

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);
}

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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

     看到这部分代码的时候,我不由得暗暗叹了口气。真的是拔了萝卜带出泥。本来想看看stack的细节实现,结果这些细节把vector都深深的出卖了。在vector中间有几个计数的变量,elementCount表示里面元素的个数,elementData是保存元素的数组。所以一般情况下数组不一定是满的,会存在着elementCount <= elementData.length这样的情况。这也就是为什么ensureCapacityHelper方法里要判断一下当新增加一个元素导致元素的数量超过数组长度了,我们要做一番调整。这个大的调整就在grow方法里展现了。

    grow方法和我们所描述的方法有点不一样。他不一样的一点在于我们可以用一个capacityIncrement来指示调整数组长度的时候到底增加多少。默认的情况下相当于数组长度翻倍,如果设置了这个变量就增加这个变量指定的这么多。

search

    search这部分就相当于找到一个最靠近栈顶端的匹配元素,然后返回这个元素到栈顶的距离。

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

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

    对应在vector里面的实现也相对容易理解:

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;
}

    这个lastIndexOf的实现无非是从数组的末端往前遍历,如果找到这个对象就返回。如果到头了,还找不到对象呢?...不好意思,谁让你找不到对象的?活该你光棍,那就返回个-1吧。

Vector

    在前面对stack的讨论和分析中,我们几乎也把vector这部分主要的功能以及实现给涵盖了。vector和相关类以及接口的关系类图如下: 

    因为Java没有内置对List类型的支持,所以Vector内部的实现是采用一个object的array。其定义如下:

protected Object[] elementData;

    这里从某种角度来说可以说是java里对泛型支持的不足,因为内部保存数据的是Object[],在存取数据的时候如果不注意的话会出现存取数据类型不一致的错误。所以在以下的某些个方法里需要加上@SuppressWarnings("unchecked")的声明。

@SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

    我们前面讨论的那些数组的增长,删除元素,查找元素以及修改等功能就占据了vector的大部分。如果有兴趣看vector的源代码的话,会发现里面主要就是这些功能的实现再加上一个迭代器功能。总共的代码不是很多,1200多行,这里就不再赘述了。 

    可以说,vector它本身就是一个可以动态增长的数组。和我们常用的ArrayList很像。和ArrayList的不同在于它对元素的访问都用synchronized修饰,也就是说它是线程安全的。在多线程的环境下,我们可以使用它。

总结

    看前面这些代码,不但理顺了栈和vector的具体实现,还可以从中发现一些其他的东西。比如说,栈最大的长度取决于vector里面数组能有多长。这里vector里面最大能取到Integer.MAX_VALUE。 以前写c程序的代码时经常感叹,要是有那种可以自动增长的数组类型就好了。当然,c99后面确实提供了这个福利。在java里面,比较典型这一部分就由vector提供了。你看,他可以自动按照需要增长,本身是线程安全的,顺便帮你把清除元素时的内存泄露问题都考虑到了。简直是自动、安全、健康又环保啊:)

参考资料:

http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

http://docs.oracle.com/javase/7/docs/api/java/util/Vector.html

  • 大小: 6.8 KB
  • 大小: 36.2 KB
分享到:
评论

相关推荐

    Java数据结构实现之Stack.zip

    本篇将重点讨论Java中栈(Stack)这一重要数据结构的实现。 栈是一种线性数据结构,遵循“后进先出”(LIFO,Last In First Out)的原则。在栈中,最后加入的元素(称为顶元素)最先被移除。栈的操作主要包括两个...

    JAVA 模拟 STACK

    本示例程序旨在通过显式的方法,也就是不依赖Java内置的`java.util.Stack`类,来实现一个自定义的栈。下面我们将深入探讨这个“JAVA 模拟 STACK”作业的相关知识点。 首先,栈的基本操作包括: 1. **压栈(Push)**:...

    Java虚拟机实现原理分析.pdf

    通过分析JVM,我们可以深入理解Java程序如何运行,如何实现跨平台,以及如何进行高效的内存管理。这些知识对于Java开发人员来说至关重要,不仅有助于编写出更加高效和稳定的代码,也有助于更好地理解Java生态系统。

    stack实现括号匹配

    这里的“stack实现括号匹配”是指利用栈这种数据结构来判断一个字符串中的左右括号是否正确配对。栈是一种后进先出(LIFO)的数据结构,非常适合用于解决此类问题。 首先,我们需要理解栈的基本操作:压入(push)...

    Stack3 java.rar_Stack3 java_palindrome

    标题中的"Stack3 java.rar_Stack3 java_palindrome"表明这是一个关于使用Java编程语言实现堆栈(Stack)数据结构,并且应用在...要深入了解这个项目的具体实现,需要详细阅读`Stack3 java.doc`文档并分析其中的代码。

    24点游戏java版,LR分析法

    《24点游戏Java版与LR分析法》 24点游戏是一款广受欢迎的数学智力游戏,玩家需要从四张1到13的扑克牌中,通过加、减、乘、除运算,使得结果等于24。在这个Java版本的24点游戏中,开发者巧妙地运用了编译原理中的LR...

    java sip 协议栈实现客户端和服务

    Java Sip 协议栈是用于实现VoIP(Voice over IP)和其他实时通信服务的核心组件。SIP(Session Initiation Protocol)是一种应用层控制协议,主要用于建立、修改和终止多媒体会话,如语音通话、视频会议等。在这个...

    如何在Java中实现微服务的日志分析

    以下是如何在Java微服务中实现日志分析的详细步骤和代码示例。 通过上述步骤,可以在Java微服务架构中实现全面的日志分析。从日志收集、存储、分析到可视化和监控,每个环节都是构建高效日志系统的重要组成部分。...

    Sip注册 Java实现

    在Java实现中,`SipApplicationDispatcher`类通常用于处理SIP事件,如请求发送、接收响应等。开发者需要实现相应的监听器接口(如`javax.sip.EventListener`)以处理这些事件。 在提供的压缩包文件`Sip_Java`中,...

    Android下各语言加callStack示例

    在Android系统中,理解和分析调用堆栈(call stack)对于开发者来说至关重要,尤其是在调试和性能优化时。本文将深入探讨如何在Android环境下为不同语言(C语言、C++、Java以及内核空间)添加并打印调用堆栈信息。 ...

    Java 常用数据结构分析

    以下是对这些数据结构及其在Java中的具体实现的详细分析: 1. **线性表**: - **ArrayList**: 作为线性表的一种实现,ArrayList是一个动态数组,它允许快速的随机访问(O(1)时间复杂度)。通过索引可以快速获取...

    java蜘蛛纸牌的实现

    从给定的文件信息来看,实际上并没有直接提及到"java蜘蛛纸牌的实现"这一主题,而是详述了一个关于学生成绩管理信息系统的Java实验报告。不过,基于标题和描述,我们可以推测,"java蜘蛛纸牌的实现"可能指的是一个...

    Java 实例 - 栈的实现源代码-详细教程.zip

    在这个"Java实例 - 栈的实现源代码-详细教程"中,我们将深入探讨Java如何通过编程实现栈这种基本的数据结构,并通过实际的源代码来学习其工作原理。栈是一种后进先出(Last In First Out, LIFO)的数据结构,广泛...

    java-数据结构代码实现

    Java的`Stack`类是基于`Vector`实现的,但你也可以自定义栈结构,比如使用`ArrayList`或`LinkedList`。 3. **队列**:队列是一种先进先出(FIFO)的数据结构,常用于任务调度和消息传递。Java提供了`ArrayDeque`和`...

    elasticstack部署完全版

    ElasticStack,也常被称为ELK Stack,是由Elasticsearch、Logstash、Kibana和Beats等组件组成的一套开源工具集,主要用于搜索和分析大数据量的日志信息。ElasticStack6.2.3版本在2018年发布,相较于之前的版本,在...

    java算法实战设计与分析

    Java的Stack类实现了Deque接口,提供push()用于入栈,pop()用于出栈,peek()用于查看栈顶元素。堆栈常用于表达式求值、函数调用、回溯算法等。 以上这些数据结构和算法在Java编程中有着广泛的应用。理解它们的概念...

    JAVA基本5种数据结构的实现。

    在Java编程语言中,数据结构是组织和管理数据的关键元素,它们提供了高效访问和操作数据的方式。...源代码文件提供了具体的实现细节,通过阅读和分析,我们可以学习到如何在Java中有效地实现和使用这些基础数据结构。

    ELKstack 中文指南

    并详细介绍了各种日志数据的场景应用,如nginx访问日志、nginx错误日志、postfix日志、ossec日志、windows系统日志、Java日志、MySQL慢查询日志等。 Kibana是ELK Stack中的数据可视化工具,它提供了强大的数据展示...

    Java语言编写的数据结构-栈实现

    在计算机科学中,数据结构是组织和存储数据的方式,它对于高效的算法设计至关重要...通过分析`stack_SqStack`和`stack_SLinkList`这两个文件,你可以深入了解Java中栈的两种实现方式,并学习如何在实际项目中灵活运用。

    深入分析JAVA Vector和Stack的具体用法

    深入分析JAVA Vector和Stack的具体用法 JAVA 中的 Vector 和 Stack 是两个重要的数据结构, Vector 是一个线程安全的动态数组,而 Stack 是一个继承自 Vector 的栈结构。本文将对 Vector 和 Stack 进行深入分析,...

Global site tag (gtag.js) - Google Analytics