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

一，Stack源碼分析

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

二，方法分析

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

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òu)造函數(shù)
public Stack() {
   }  
  

2.3，push（）方法

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

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

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

2.5，peek（）方法

public synchronized E peek() {
   //獲取集合元素個數(shù)
       int     len = size();
 //集合個數(shù)長度為0時，再去獲取元素時就應(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ū)分，時間復(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;
   }