Stack-栈的源码分析与实现

码农王同学

发布于 2020-12-25 14:11:50

4970

发布于 2020-12-25 14:11:50

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

一，Stack源码分析

Stack，栈，也是数据结构的一种，对于java应用开发者而言，我使用栈的应用场景比较少，一般做做算法类的题会用到，对于实际的应用场景我觉得栈还是比较厉害的一种数据结构，栈的特点嘛，先进后出，后进先出。

二，方法分析

其实，怎么说呢，我分析过了Vector集合的源码分析了，然而栈继承了Vector类，所以，你懂得，栈就是Vector集合的一种特例了，所以，这篇文章会很简短，但是我还是来分析了。

Vector集合最全面的源码分析

2.1，栈结构继承结构

//记住和理解java类的"单继承，多实现"的特点哈
public class Stack<E> extends Vector<E> {}

2.2，构造函数

//一个无参构造函数
public Stack() {
    }

2.3，push（）方法

其实，栈也是看作一种集合嘛，集合就是用来装填数据元素的嘛，所以我们接下来就是分析栈的各种方法了，如何装填数据元素呢，当然了，我们要看下push()方法了。

public E push(E item) {
    //看下第二步操作
        addElement(item);

        return item;
    }
//第二步操作
public synchronized void addElement(E obj) {
    //modCount的含义下面的这个解释已经很形象了
    //The number of times this list has been  modified
        modCount++;
    //这一步就是扩容操作了，这里不分析了，可以看下vector源码分析这篇文章
        ensureCapacityHelper(elementCount + 1);
    //将元素装填在数组中
        elementData[elementCount++] = obj;
    }

2.4，pop（）方法

public synchronized E pop() {
        E       obj;
     //第二步操作，获取栈的大小
        int     len = size();
     //第三步操作，调用peek()方法获取栈顶元素位置
        obj = peek();
     //第四步操作，将栈顶的元素删除，就达到了pop()的功能
     //等下一起分析下peek()方法
        removeElementAt(len - 1);

        return obj;
    }
//第二步操作   
    public synchronized int size() {
        //这是一个线程安全的方法，返回集合元素的个数，成员变量elementCount
        return elementCount;
    }
//第四步操作
public synchronized void removeElementAt(int index) {
    //其实，这个不用太关心了
        modCount++;
    //首先，我们删除一个元素的时候，会先判断是否存在这个元素的
    //这里index=len-1就是数组空间的最后一个元素
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
    //数组空间的起始位置是从0开始的，所以小于0，就需要抛出索引越界的问题
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
    //确定j的位置，便于数组元素的移动
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
    //集合元素个数减一
        elementCount--;
    //将移除的元素置为null，和下面注释表达的一样的，就是为了触发gc来回收不可达对象的
    //以便整合内存空间
        elementData[elementCount] = null; /* to let gc do its work */
    }

2.5，peek（）方法

public synchronized E peek() {
    //获取集合元素个数
        int     len = size();
  //集合个数长度为0时，再去获取元素时就应该抛出栈为空的异常
        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);
    }
//第三步操作
E elementData(int index) {
        return (E) elementData[index];
    }

2.6，isEmpty（）方法

public boolean empty() {
     //判断集合size是否等于0
        return size() == 0;
    }

2.7，search（）方法

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

        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);
//其实，集合是可以装填null元素的，所以这里需要区分，时间复杂度为O(n)
        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;
    }