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

码农王同学

发布于 2020-04-09 10:10:18

4140

发布于 2020-04-09 10:10:18

文章被收录于专栏：后端Coder后端Coder

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的结构方法。