如何實(shí)現(xiàn)Stack棧

一，Stack源碼分析

Stack，棧，也是數(shù)據(jù)結(jié)構(gòu)的一種，對(duì)于java應(yīng)用開發(fā)者而言，我使用棧的應(yīng)用場(chǎng)景比較少，一般做做算法類的題會(huì)用到，對(duì)于實(shí)際的應(yīng)用場(chǎng)景我覺得棧還是比較厲害的一種數(shù)據(jù)結(jié)構(gòu)，棧的特點(diǎn)嘛，先進(jìn)后出，后進(jìn)先出。 

二，方法分析

其實(shí)，怎么說(shuō)呢，我分析過(guò)了Vector集合的源碼分析了，然而棧繼承了Vector類，所以，你懂得，棧就是Vector集合的一種特例了，所以，這篇文章會(huì)很簡(jiǎn)短，但是我還是來(lái)分析了。

Vector集合最全面的源碼分析 

2.1，棧結(jié)構(gòu)繼承結(jié)構(gòu)

//記住和理解java類的"單繼承，多實(shí)現(xiàn)"的特點(diǎn)哈
public class Stack<E> extends Vector<E> {}  
  

2.2，構(gòu)造函數(shù)

//一個(gè)無(wú)參構(gòu)造函數(shù)
public Stack() {
    }  
  

2.3，push（）方法

其實(shí)，棧也是看作一種集合嘛，集合就是用來(lái)裝填數(shù)據(jù)元素的嘛，所以我們接下來(lái)就是分析棧的各種方法了，如何裝填數(shù)據(jù)元素呢，當(dāng)然了，我們要看下push()方法了。

public E push(E item) {
    //看下第二步操作
        addElement(item);

        return item;
    }
//第二步操作
public synchronized void addElement(E obj) {
    //modCount的含義下面的這個(gè)解釋已經(jīng)很形象了
    //The number of times this list has been  modified
        modCount++;
    //這一步就是擴(kuò)容操作了，這里不分析了，可以看下vector源碼分析這篇文章
        ensureCapacityHelper(elementCount + 1);
    //將元素裝填在數(shù)組中
        elementData[elementCount++] = obj;
    }  
  

2.4，pop（）方法

public synchronized E pop() {
        E       obj;
     //第二步操作，獲取棧的大小
        int     len = size();
     //第三步操作，調(diào)用peek()方法獲取棧頂元素位置
        obj = peek();
     //第四步操作，將棧頂?shù)脑貏h除，就達(dá)到了pop()的功能
     //等下一起分析下peek()方法
        removeElementAt(len - 1);

        return obj;
    }
//第二步操作   
    public synchronized int size() {
        //這是一個(gè)線程安全的方法，返回集合元素的個(gè)數(shù)，成員變量elementCount
        return elementCount;
    }
//第四步操作
public synchronized void removeElementAt(int index) {
    //其實(shí)，這個(gè)不用太關(guān)心了
        modCount++;
    //首先，我們刪除一個(gè)元素的時(shí)候，會(huì)先判斷是否存在這個(gè)元素的
    //這里index=len-1就是數(shù)組空間的最后一個(gè)元素
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                                                     elementCount);
        }
    //數(shù)組空間的起始位置是從0開始的，所以小于0，就需要拋出索引越界的問題
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
    //確定j的位置，便于數(shù)組元素的移動(dòng)
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
    //集合元素個(gè)數(shù)減一
        elementCount--;
    //將移除的元素置為null，和下面注釋表達(dá)的一樣的，就是為了觸發(fā)gc來(lái)回收不可達(dá)對(duì)象的
    //以便整合內(nèi)存空間
        elementData[elementCount] = null; /* to let gc do its work */
    }  
  

2.5，peek（）方法

public synchronized E peek() {
    //獲取集合元素個(gè)數(shù)
        int     len = size();
  //集合個(gè)數(shù)長(zhǎng)度為0時(shí)，再去獲取元素時(shí)就應(yīng)該拋出棧為空的異常
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
//第二步操作
public synchronized E elementAt(int index) {
    //校驗(yàn)索引是否越界
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
//根據(jù)索引下標(biāo)位置獲取指定位置的元素
        return elementData(index);
    }
//第三步操作
E elementData(int index) {
        return (E) elementData[index];
    }  
  

2.6，isEmpty（）方法

public boolean empty() {
     //判斷集合size是否等于0
        return size() == 0;
    }  
  

2.7，search（）方法

public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
//第二步操作
public synchronized int lastIndexOf(Object o) {
        return lastIndexOf(o, elementCount-1);
    }
//第三步操作
public synchronized int lastIndexOf(Object o, int index) {
    //預(yù)檢查機(jī)制
        if (index >= elementCount)
            throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
//其實(shí)，集合是可以裝填null元素的，所以這里需要區(qū)分，時(shí)間復(fù)雜度為O(n)
        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;
    }