深入學習數據結構之棧（一）

什麼是棧？

　　定義：  一種運算受限的線性表。其限制是僅允許線上性表的一端進行插入和刪除運算。可操作的一端被稱為棧頂，相對地，把另一端稱為棧底，棧底不可進行操作。

所以棧中的數據遵循 “先進後出” 即只能操作棧頂的數據。

　　分類：

　　　　　　如圖所示，將數據4壓入棧中，此時4為棧頂元素

　　　　　　如圖所示，將剛纔壓入棧的4彈出棧，

　　　　（4）棧頂peek：獲取棧頂元素，此時不彈出棧頂元素，僅僅獲取數據。

　　　　（5）判空 is_empty ： 判斷棧是否為空。註意如果是數組模式則不能直接通過數組大小進行判斷。

　　　　（6）清空 clear：清空棧中所有內容。註意數組模式和鏈表模式區別

　　Java Stack棧實現原理：

　·　　Stack類層次結構圖：

　　　  分析：從類結構圖可以初步看出，Java中的stack是基於數組實現的。

　　　源碼分析：

protected Object[] elementData; // 對象數組
　　protected int elementCount;  // 對象數量（無法通過數組大小獲取實際大小，需要額外定義）　　　　
　
　  // push添加
　　public E push(E item) {
　　　　　　addElement(item);
　　　　　　return item;
　　　}
　　public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }
　　
　　private void ensureCapacityHelper(int minCapacity) {
　　　　if (minCapacity - elementData.length > 0)
　　　　　　grow(minCapacity);
　　}

　　private void grow(int minCapacity) {
　　　　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);
　　}

　　// pop彈出
　　public synchronized E pop() {
        E obj;
        int len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
   }
 　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; 
    }


　　// 查看棧頂元素
　　public synchronized E peek() {
        int     len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
　　}
　　public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
        return elementData(index);
　　}

 總結：

　　數據結構中包含了兩部分信息：1、一個固定大小的數組，2、一個計數器elementCount

　　push 添加對象，在添加時需要校驗數組大小是否越界，如果數組大小不夠，則需要進行擴容。每次添加都是在當前數組elementCount的下一個節點進行添加。

　　　　因此數組大小並非當前棧的大小，棧的大小通過計數器elementCount進行標記。每次訪問需要根據elementCount進行定位。

　　pop 彈出對象，在彈出時會調用remove方法將elementCount-1這個元素清空，同時elementCount-- 。

　　peek 獲取棧頂對象，在獲取棧頂對象即獲取 數組 len-1下標的對象，此時不對原數據進行任何操作 。