Java之--Stack棧

Stack棧

====================================================

【 後進先出】的結構

Stack本身通過擴充Vector而來，而Vector本身是一個可增長的對象數組（a growable array of objects）

棧的數組結構實作

jdk1.7(其它版本可能不同)

---------------------------------------------------------

Stack.class   5個方法

E push(E item)             把項壓入棧頂部。            

E pop()                           移除棧頂部的對象，并作為此函數的值傳回該對象。          

E peek()                         檢視棧頂部的對象，但不從堆棧中移除它。         

boolean empty()           測試棧是否為空。            

int search(Object o)     傳回對象在棧中的位置，以1為基數。      

---------------------------------------------------------

public class Stack<E> extends Vector<E>{}

public class Vector<E> extends AbstractList<E> implements List<E>, ...{

    protected Object[] elementData;     //數組

    protected int elementCount;             //數組中元素個數

    protected int capacityIncrement;      //自動遞增量(大小)

}

0.初始化

Stack stack = new Stack();//就這一個構造方法

會調用Vector的構造方法, Vector線程安全

public Vector() {

    this(10);

}

public Vector(int initialCapacity, int capacityIncrement) {

    this.elementData = new Object[initialCapacity];     //初始容量為10

    this.capacityIncrement = capacityIncrement;          //初始遞增量為0

}

1.push()把對象壓入棧頂

public E push(E item) {

       addElement(item);

        return item;

}

public synchronized void addElement(E obj) {

        modCount++;

        ensureCapacityHelper(elementCount + 1);//確定需不需要擴容

        elementData[elementCount++] = obj;//elementCount++數組中元素個數加1；加入的資料依次往後放

}

private void ensureCapacityHelper(int minCapacity) {

        if (minCapacity - elementData.length > 0)//大于數組中元素個數時擴容

            grow(minCapacity);//擴容

}

//Stack stcapacityIncrement=0，擴容量為原來的一倍

//原來elementData.length=10，擴容後為20，再擴容後為40

private void grow(int minCapacity) {

        // overflow-conscious code

        int oldCapacity = elementData.length;

        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?

                                         capacityIncrement : oldCapacity);//如果capacityIncrement=0，擴容量為原來的一倍

        if (newCapacity - minCapacity < 0)

            newCapacity = minCapacity;

        if (newCapacity - MAX_ARRAY_SIZE > 0)//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

            newCapacity = hugeCapacity(minCapacity);

        elementData = Arrays.copyOf(elementData, newCapacity);

}

2.pop()移除棧頂部的對象

public synchronized E pop() {

        E obj = peek();//棧頂對象

        removeElementAt(size() - 1);//移除棧頂對象

        return obj;//傳回棧頂對象

    }

public synchronized void removeElementAt(int index) {

      ......  

        elementCount--;

        elementData[elementCount] = null;

    }

3.peek()檢視棧頂部的對象

//return the object at the top of this stack (the last item of the Vector object).

public synchronized E peek() {

        int     len = size();

        if (len == 0)

            throw new EmptyStackException();

        return elementAt(len - 1);

    }

相當于 elementData[size() - 1]

4.empty()

public boolean empty() {

        return size() == 0;

    }

5. search()傳回對象在棧中的位置

public synchronized int search(Object o) {

        int i = lastIndexOf(o);

        if (i >= 0) {

            return size() - i;//對象在棧中的位置，以1為基數；從棧頂到棧底的順序

        }

        return -1;

    }

public synchronized int lastIndexOf(Object o, int elementCount-1) {

        ......

        for (int i = index; i >= 0; i--)//從數組後面往前找(相當于從棧頂往棧底找)

            if (o.equals(elementData[i]))

               return i;

        return -1;

    }

Stack不要求其中儲存資料的唯一性，當Stack中有多個相同的item時，調用search方法，

隻傳回與查找對象equal并且離棧頂最近的item與棧頂間距離