Java教程

从Java底层分析Stack(栈)的用法——源码分析系列

本文主要是介绍从Java底层分析Stack(栈)的用法——源码分析系列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

最近找工作时,面试了阿里、百度、腾讯、字节等一线互联网大厂。

发现这些大厂有一个共同特征,就是喜欢考查面试者查看底层代码的能力。

于是就有了这个系列, 希望能够帮到大家。



Stack底层源码分析

先来看一下Stack的全部源码

package java.util;

public class Stack<E> extends Vector<E> {
    private static final long serialVersionUID = 1224463164541339165L;

    public Stack() {
    }

    public E push(E var1) {
        this.addElement(var1);
        return var1;
    }

    public synchronized E pop() {
        int var2 = this.size();
        Object var1 = this.peek();
        this.removeElementAt(var2 - 1);
        return var1;
    }

    public synchronized E peek() {
        int var1 = this.size();
        if (var1 == 0) {
            throw new EmptyStackException();
        } else {
            return this.elementAt(var1 - 1);
        }
    }

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

    public synchronized int search(Object var1) {
        int var2 = this.lastIndexOf(var1);
        return var2 >= 0 ? this.size() - var2 : -1;
    }
}

我们发现,Stack是继承Vector实现栈原理的。

接下来一个一个方法来进行分析:

1. 声明栈

声明语句:Stack<Integer>st = new Stack<Integer>();
注意:Stack中只能压入包装类,即只能声明Integer,没办法声明int。

压入:Push()

源码:

// push源码
    public E push(E var1) {
        this.addElement(var1);
        return var1;
    }

这里我们发现它代用了一个addElement方法。这个方法基于synchronized修饰,是一个线程安全的方法。

点进去查看, 发现跳转到了vector源代码中,证明Stack与Vector共用一个添加元素的方法(addElement)。

该方法首先要判断数组的容量是否能够容纳新的元素,若不能,则需要进行扩容操作,然后将元素e放置在数组的size位置。ensureCapacityHelper(int)方法源码如下

// addElement 方法
    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

在ensureCapacityHelper()方法中,判断数组实际容纳的元素数量是否超过了当前数组长度,若是,则执行扩容操作, 即grow方法。

// ensureCapacityHelper 方法
    private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        // 如果超过了数组长度,则需要扩容。
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
// grow 方法
private void grow(int minCapacity) {
    // overflow-conscious code
    // 获取elementData的原始容量
    int oldCapacity = elementData.length;
    // 计算新的容量
    // 如果在构造方法中设置了capacityIncrement > 0,那么新数组长度就是原数组长度 + capacityIncrement
    // 否则,新数组长度就是原数组长度 * 2
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                        capacityIncrement : oldCapacity);
    // 若进行扩容后,capacity仍然比实际需要的小,则新容量更改为实际需要的大小,即minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新数组的长度比虚拟机能够提供给数组的最大存储空间大,则将新数组长度更改为最大正数:Integer.MAX_VALUE
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 按照新的容量newCapacity创建一个新数组,然后再将原数组中的内容copy到新数组中
    elementData = Arrays.copyOf(elementData, newCapacity);
}

注意:扩容后的数组长度为原数组长度*2

以上,即为Stack中push的全部源码分析。


弹出:Pop()

Pop的源码:

  • 该方法被synchronized修饰,是线程安全的。

  • var2为当前栈长度,var1为栈顶元素,首先通过removeElementAt()方法移除栈顶元素,然后返回被移除的栈顶元素值。

    public synchronized E pop() {
        int var2 = this.size();
        Object var1 = this.peek();
        this.removeElementAt(var2 - 1);
        return var1;
    }

接下来查看removeElementAt()方法

    public synchronized void removeElementAt(int index) {
    // index是移除一个元素后数组的长度
    // index大于等于元素个数,则抛出异常
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
    // index小于0,则抛异常
    // ArrayIndexOutOfBoundsException:数组索引越界异常
        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()

如果为0,则返回空栈异常

反之,进行元素查找并返回的操作(elementAt()方法)

    public synchronized E peek() {
        int var1 = this.size();
        if (var1 == 0) {
            throw new EmptyStackException();
        } else {
            return this.elementAt(var1 - 1);
        }
    }

判断是否为空:empty()

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

查找:search()

lastIndexOf()方法:从后向前查找元素,若查找成功,则返回位置,反之,返回-1。

var2存储查找结果,如果var2>=0,则证明查找成功,则返回位置

    public synchronized int search(Object var1) {
        int var2 = this.lastIndexOf(var1);
        return var2 >= 0 ? this.size() - var2 : -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;
    }
这篇关于从Java底层分析Stack(栈)的用法——源码分析系列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!