Stack源码(一)

Java 2018-03-03

继承于Vector

Vector跟ArrayList有点像,也是用数组保存元素。
newElementArray方法类似于toArray
也有add方法,意味着Stack有可能继承这个方法,还有remove,contains等等方法。同时还有迭代器内部类。

hashCode是在Object类中的,其他类都是继承Object类的。
Vector中的capacityIncrement是扩容因子,在原先的栈已经满的时候,扩容一定数量的空间。

private void growByOne() {
        int adding = 0;
        if (capacityIncrement <= 0) {
            if ((adding = elementData.length) == 0) {
                adding = 1;
            }
        } else {
            adding = capacityIncrement;
        }

        E[] newData = newElementArray(elementData.length + adding);
        System.arraycopy(elementData, 0, newData, 0, elementCount);
        elementData = newData;
    }
扩容因子初始化的时候可以传入参数 `public Vector(int capacity, int capacityIncrement)`

否则,默认为0

  public Vector() {
            this(DEFAULT_SIZE, 0);
        }

栈里面穿什么类型具体看泛型
以下方法基于jdk1.8
peek方法是返回栈顶元素

/**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return  the object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();

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

pop方法

/**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     *
     * @return  The object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();

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

        return obj;
    }

上面的removeElementAt方法:

/**
     * Deletes the component at the specified index. Each component in
     * this vector with an index greater or equal to the specified
     * {@code index} is shifted downward to have an index one
     * smaller than the value it had previously. The size of this vector
     * is decreased by {@code 1}.
     *
     * <p>The index must be a value greater than or equal to {@code 0}
     * and less than the current size of the vector.
     *
     * <p>This method is identical in functionality to the {@link #remove(int)}
     * method (which is part of the {@link List} interface).  Note that the
     * {@code remove} method returns the old value that was stored at the
     * specified position.
     *
     * @param      index   the index of the object to remove
     * @throws ArrayIndexOutOfBoundsException if the index is out of range
     *         ({@code index < 0 || index >= size()})
     */
    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 */
    }

可见没有缩减数组的空间,仅仅是把elementCount-1即可,因为不然的话后面要push的时候再扩容。没有必要这样省内存

再来看看push方法

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

        return item;
    }

里面的addElement方法(Android API14):

 public synchronized void addElement(E object) {
        if (elementCount == elementData.length) {
            growByOne();
        }
        elementData[elementCount++] = object;
        modCount++;
    }

search方法

/**
     * Returns the index of the first occurrence of the object, starting from
     * the top of the stack.
     *
     * @return the index of the first occurrence of the object, assuming that
     *         the topmost object on the stack has a distance of one.
     * @param o
     *            the object to be searched.
     */
public synchronized int search(Object o) {
        final Object[] dumpArray = elementData;
        final int size = elementCount;
        if (o != null) {
            for (int i = size - 1; i >= 0; i--) {
                if (o.equals(dumpArray[i])) {
                    return size - i;
                }
            }
        } else {
            for (int i = size - 1; i >= 0; i--) {
                if (dumpArray[i] == null) {
                    return size - i;
                }
            }
        }
        return -1;
    }

上面代码像
final Object[] dumpArray = elementData;
final int size = elementCount;
重新赋值一下是为了不改变elementData,elementCount本身,类似c的指针如果直接修改会改变本身的值

这个代码是从栈顶找的,返回第一个找到的元素,也可以自己写一个从栈底的,这个无所谓

返回size-i表示从栈顶数,第i个元素


本文由 方方無 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

还不快抢沙发

添加新评论

shijiebei 365bet manbetx 188bet xinshui caipiao 95zz tongbaoyule beplay 88bifa 18luck betway bwin hg0088 aomenjinshayulecheng ca88 shenbotaiyangcheng vwin w88 weide