深入理解Stack

发布时间:2022-09-27 23:00

1,特性

顾名思义,Stack,具有一般栈的特性,先进后出,后进先出
Stack直接继承Vector,因此,Vector有的特性,Stack也有,包括具有线程安全

2,继承关系

深入理解Stack_第1张图片

3,走进源码

原理:基于数组存取
数据结构

	//存储数据区域
	protected Object[] elementData;
	//集合大小记录器
    protected int elementCount;

3.1 构造函数

只有一个空的构造函数

    public Stack() {
    }

3.2添加元素(进栈)

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

addElement()方法 (注意有synchronized 关键字)

    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        //把元素添加到栈顶
        elementData[elementCount++] = obj;
    }

ensureCapacityHelper(方法)跟Vector的几乎相同,这里不细说

 private void ensureCapacityHelper(int minCapacity) {
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

grow()方法 跟Vector的几乎相同,这里不细说

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

3.3删除元素(出栈)

  public synchronized E pop() {
        E obj;
        //获取当前栈大小
        int len = size();
        //获取栈顶元素
        obj = peek();
        //
        removeElementAt(len - 1);
        return obj;
    }

size()方法 ,返回当前栈的长度

  public synchronized int size() {
        return elementCount;
    }

peek()方法, 返回栈顶元素

   public synchronized E peek() {
        int len = size();
        if (len == 0)
            throw new EmptyStackException();
         //返回数组末端的元素
        return elementAt(len - 1);
    }

elementAt()方法 , 返回栈顶元素具体细节

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

removeElementAt()方法(继承于Vector的方法)

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

3.4查找

正式查找

   public synchronized int search(Object o) {
   //从数组末端(栈顶)往回找
        int i = lastIndexOf(o);
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

还有一个peek()方法,就是返回栈顶元素的操作,请看上面细节

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号