数据结构-栈（Stack）

[zgq105]

栈（Stack）是一种后进先出（LIFO）数据结构。在JDK中，Stack继承自Vector，提供了基本的入栈（push）、出栈（pop）、查找栈顶元素（peek）、查找元素在栈中位置（search）等方法；同时是一个线程安全的类。

入栈push分析

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

        return item;
    }

//这个方法是Stack的父类Vector中的方法
public synchronized void addElement(E obj) {
        modCount++;//操作记录+1
        ensureCapacityHelper(elementCount + 1); //扩容判断
        elementData[elementCount++] = obj; //添加到栈顶
    }

出栈（pop）分析

public synchronized E pop() {
        E       obj;
        int     len = size();//数组大小

        obj = peek(); //获取栈顶元素
        removeElementAt(len - 1); //删除最后一个元素，即删除栈顶元素

        return obj;
    }

//获取栈顶元素

public synchronized E peek() {
        int     len = size();

        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1); //数组的最后一个元素就是栈顶元素
    }

//这个是父类Vector中的方法

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

//这个是父类Vector中的方法
public synchronized void removeElementAt(int index) {
        modCount++;//修改记录+1
        if (index >= elementCount) { //判断数组越界情况
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
        else if (index < 0) {//判断数组越界情况
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {//因为出栈是栈顶元素，因此j==0
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--; //数组大小-1
        elementData[elementCount] = null; /* to let gc do its work *///清空元素
    }