最近在開始看《算法第四版》，剛學習了兩天，感覺還是收獲很大。

照著書上實現了一個下壓棧：

定容定類型的棧

棧的結構特點是先進先出，這里使用String數據類型，學習過數據結構的話應該不難寫出下面的基礎代碼，使用基本的數據類型數組來進行實現，和其他語言實現類似（C語言也是使用數組進行棧的實現）

有我們熟悉的API：isEmpty()，push()，pop()

public class FixedCapacityStackOfStrings {
    private String[] a;
    private int N; // 當前的size

    public FixedCapacityStackOfStrings(int cap) {
        a = new String[cap];
    }

    public int size(){
        return N;
    }

    public boolean isEmpty(){
        return N == 0;
    }

    public void push(String item){
        a[N++] = item;
    }

    public String pop(){
        return a[--N];
    }
}

當然，這個實現缺點也很明顯，棧的數據類型不能變，而且不能動態(tài)增長。

那么，想要實現動態(tài)增長，就需要用到Java的泛型，之前也沒有用到泛型，也相應的練習了段簡單的泛型代碼如下，定義了一個簡單的泛型類Pair，如字面意思，存儲一對任意類型元素并有它相應方法。

public class Pair<T> {
    private T first;
    private T second;

    public Pair(){
        this.first = null;
        this.second = null;
    }

    public Pair(T first, T second){
        this.first = first;
        this.second = second;
    }

    public T getFirst(){
        return this.first;
    }

    public T getSecond(){
        return this.second;
    }

    public void setFirst(T first) {
        this.first = first;
    }

    public void setSecond(T second) {
        this.second = second;
    }
}

有了泛型的基礎，還有一個問題需要解決，就是讓它的空間可以動態(tài)的增長，寫C語言時候用到的函數是malloc()內存分配的方法，我們可以想到使用Java里的new 關鍵字。

這里要注意一個點，Java里不允許創(chuàng)建泛型數組，所以需要使用類型轉換的方法來做

// 將棧移動到新的大小為max的數組中
    public void resize(int max){
        Item[] temp = (Item[]) new Object[max];
        for (int i=0; i<N; i++){
            temp[i] = a[i];
        }
        a = temp;
    }

那么有了上面的基礎，我們就可以寫出最終版本了！

import java.util.Iterator;

public class ResizingArrayStack<Item> implements Iterable<Item> {
    private Item[] a = (Item[]) new Object[1]; // 棧元素
    private int N = 0; // 當前元素數量

    public boolean isEmpty(){
        return  N==0;
    }

    public int size(){
        return N;
    }

    // 將棧移動到新的大小為max的數組中
    public void resize(int max){
        Item[] temp = (Item[]) new Object[max];
        for (int i=0; i<N; i++){
            temp[i] = a[i];
        }
        a = temp;
    }

    // 入棧
    public void push(Item item){
        if (N == a.length){
            this.resize(2*a.length);
        }
        a[N++] = item;
    }

    // 出棧
    public Item pop(){
        Item item = a[--N];
        a[N] = null; // 避免對象游離
        if (N>0 && N==a.length/4){
            this.resize(a.length/2);
        }
        return a[--N];
    }

    @Override
    public Iterator<Item> iterator() {
        return new ReverseArrayIterator();
    }

    // 內部類
    public class ReverseArrayIterator implements Iterator<Item>{
        private int i = N;

        public boolean hasNext(){
            return i> 0;
        }

        public Item next(){
            return a[--i];
        }

        public void remove(){

        }
    }
}