摘要：在改進(jìn)前使用數(shù)組的一個缺點是必須聲明數(shù)組的大小，所以棧有確定的容量。待解決的問題建立一個能夠增長或者縮短到任意大小的棧。下邊的圖是觀察時間開銷的另一種方式，表示了入棧操作需要訪問數(shù)組的次數(shù)。

上一篇：算法分析
下一篇：基本排序

本篇內(nèi)容主要是棧，隊列 (和包)的基本數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)
文章里頭所有的對數(shù)函數(shù)都是以 2 為底
關(guān)于性能分析，可能還是需要一些數(shù)學(xué)知識，有時間可以回一下
在很多應(yīng)用中，我們需要維護(hù)多個對象的集合，而對這個集合的操作也很簡單

對象的集合

操作：

insert -- 向集合中添加新的對象

remove -- 去掉集合中的某個元素

iterate -- 遍歷集合中的元素并對他們執(zhí)行某種操作

test if empty -- 檢查集合是否為空

做插入和刪除操作時我們要明確以什么樣的形式去添加元素，或我們要刪除集合中的哪個元素。

處理這類問題有兩個經(jīng)典的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)：棧(stack) 和隊列(queue)

兩者的區(qū)別在于去除元素的方式：

棧：去除最近加入的元素，遵循后進(jìn)先出原則(LIFO: last in first out)。

插入元素對應(yīng)的術(shù)語是入棧 -- push；去掉最近加入的元素叫出棧 -- pop

隊列：去除最開始加入的元素，遵循先進(jìn)先出原則(FIFO: first in first out)。

關(guān)注最開始加入隊列的元素，為了和棧的操作區(qū)分，隊列加入元素的操作叫做入隊 -- enqueue；去除元素的操作叫出隊 -- dequeue

此篇隱含的主題是模塊式編程，也是平時開發(fā)需要遵守的原則

這一原則的思想是將接口與實現(xiàn)完全分離。比如我們精確定義了一些數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)(如棧，隊列等)，我們想要的是把實現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)完全與客戶端分離。客戶端可以選擇數(shù)據(jù)結(jié)構(gòu)不同的實現(xiàn)方式，但是客戶端代碼只能執(zhí)行基本操作。

實現(xiàn)的部分無法知道客戶端需求的細(xì)節(jié)，它所要做的只是實現(xiàn)這些操作，這樣，很多不同的客戶端都可以使用同一個實現(xiàn)，這使得我們能夠用模塊式可復(fù)用的算法與數(shù)據(jù)結(jié)構(gòu)庫來構(gòu)建更復(fù)雜的算法和數(shù)據(jù)結(jié)構(gòu)，并在必要的時候更關(guān)注算法的效率。

Separate client and implementation via API.

API：描述數(shù)據(jù)類型特征的操作
Client：使用API??操作的客戶端程序。
Implementation：實現(xiàn)API操作的代碼。

下面具體看下這兩種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)

假設(shè)我們有一個字符串集合，我們想要實現(xiàn)字符串集合的儲存，定期取出并且返回最后加入的字符串，并檢查集合是否為空。我們需要先寫一個客戶端然后再看它的實現(xiàn)。

字符串?dāng)?shù)據(jù)類型的棧

性能要求：所有操作都花費常數(shù)時間
客戶端：從標(biāo)準(zhǔn)輸入讀取逆序的字符串序列

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public static void main(String[] args)
{
    StackOfStrings stack = new StackOfStrings();
    while (!StdIn.isEmpty())
    {
    //從標(biāo)準(zhǔn)輸入獲取一些字符串
    String s = StdIn.readString();
    //如果字符串為"-",則客戶端將棧頂?shù)淖址鰲?，并打印出棧的字符?    if (s.equals("-")) StdOut.print(stack.pop());
    //否則將字符串入棧到棧頂
    else stack.push(s);
    }
}

客戶端輸入輸出：

鏈表(linked-list)連接待添加...

我們想保存一個有節(jié)點組成的，用來儲存字符串的鏈表。節(jié)點包含指向鏈表中下一個元素的引用(first).

維持指針 first 指向鏈表中的第一個節(jié)點

Push：入棧，在鏈表頭插入一個新的節(jié)點

Pop：出棧，去掉鏈表頭處第一個節(jié)點

public class LinkedStackOfStrings
{
     //棧中唯一的實例變量是鏈表中的第一個節(jié)點的引用
     private Node first = null;
     
     //內(nèi)部類，節(jié)點對象，構(gòu)成鏈表中的元素，由一個字符串和指向另一個節(jié)點的引用組成
     private class Node
     {
         private String item;
         private Node next;
     }

     public boolean isEmpty()
     { return first == null; }
     
     //
     public void push(String item)
     {
         //將指向鏈表頭的指針先保存
         Node oldfirst = first;
         //創(chuàng)建新節(jié)點：我們將要插入表頭的節(jié)點
         first = new Node();
         first.item = item;
         //實例變量的next指針指向鏈表oldfirst元素，現(xiàn)在變成鏈表的第二個元素
         first.next = oldfirst;
     }
     
     //出棧
     public String pop()
     {
         //將鏈表中的第一個元素儲存在標(biāo)量 item 中
         String item = first.item;
         //去掉第一個節(jié)點：將原先指向第一個元素的指針指向下一個元素，然后第一個節(jié)點就等著被垃圾回收處理
         first = first.next;
         //返回鏈表中原先保存的元素
         return item;
     }
}

圖示：

出棧：

入棧：

通過分析提供給客戶算法和數(shù)據(jù)結(jié)構(gòu)的性能信息，評估這個實現(xiàn)對以不同客戶端程序的資源使用量

Proposition 在最壞的情況下，每個操作只需要消耗常數(shù)時間(沒有循環(huán))。
Proposition 具有n個元素的棧使用 ~40n 個字節(jié)內(nèi)存
(沒有考慮字符串本身的內(nèi)存，因為這些空間的開銷在客戶端上)

棧用鏈表是實現(xiàn)花費常數(shù)的時間，但是棧還有更快的實現(xiàn)

另一種實現(xiàn)棧的 natural way 是使用數(shù)組儲存棧上的元素
將棧中的N個元素保存在數(shù)組中，索引為 n，n 對應(yīng)的數(shù)組位置即為棧頂?shù)奈恢茫聪乱粋€元素加入的地方

使用數(shù)組 s[] 在棧上存儲n個元素。

push()：在 s[n] 處添加新元素。

pop()：從 s[n-1] 中刪除元素。

在改進(jìn)前使用數(shù)組的一個缺點是必須聲明數(shù)組的大小，所以棧有確定的容量。如果棧上的元素個數(shù)比棧的容量多，我們就必須處理這個問題(調(diào)整數(shù)組)

public class FixedCapacityStackOfStrings
{
     private String[] s;
     //n 為棧的大小，棧中下一個開放位置，也為下一個元素的索引
     private int n = 0;
     
    //int capacity：看以下說明
     public FixedCapacityStackOfStrings(int capacity)
     { s = new String[capacity]; }
    
     public boolean isEmpty()
     { return n == 0; }
    
     public void push(String item)
     { 
         //將元素放在 n 索引的位置，然后 n+1
         s[n++] = item; 
     }
    
     public String pop()
     { 
         //然后返回數(shù)組n-1的元素
         return s[--n]; 
     }
}

int capacity： 在構(gòu)造函數(shù)中加入了容量的參數(shù)，破壞了API，需要客戶端提供棧的容量。不過實際上我們不會這么做，因為大多數(shù)情況下，客戶端也無法確定需要多大棧，而且客戶端也可能需要同時維護(hù)很多棧，這些棧又不同時間到達(dá)最大容量，同時還有其他因素的影響。這里只是為了簡化。在調(diào)整數(shù)組中會處理可變?nèi)萘康膯栴}，避免溢出

上述的實現(xiàn)中我們暫時沒有處理的問題：

Overflow and underflow

Underflow ：客戶端從空棧中出棧我們沒有拋出異常

Overflow ：使用數(shù)組實現(xiàn)，當(dāng)客戶端入棧超過容量發(fā)生棧溢出的問題

Null item：客戶端是否能向數(shù)據(jù)結(jié)構(gòu)中插入空元素，上邊我們是允許的

Duplicate items: 客戶端是否能向數(shù)據(jù)結(jié)構(gòu)中重復(fù)入棧同一個元素，上邊我們是允許的

Loitering 對象游離：即在棧的數(shù)組中，我們有一個對象的引用，可是我們已經(jīng)不再使用這個引用了

數(shù)組中當(dāng)我們減小 n 時，在數(shù)組中仍然有我們已經(jīng)出棧的對象的指針，盡管我們不再使用它，但是Java系統(tǒng)并不知道。所以為了避免這個問題，有效地利用內(nèi)存，最好將去除元素對應(yīng)的項設(shè)為 null，這樣就不會剩下舊元素的引用指針，接下來就等著垃圾回收機制去回收這些內(nèi)存。這個問題比較細(xì)節(jié)化，但是卻很重要。

public String pop()
{
 String item = s[--n];
 s[n] = null;
 return item;
} 

之前棧的基本數(shù)組實現(xiàn)需要客戶端提供棧的最大容量，現(xiàn)在我們來看解決這個問題的技術(shù)。

待解決的問題：建立一個能夠增長或者縮短到任意大小的棧。
調(diào)整大小是一個挑戰(zhàn)，而且要通過某種方式確保它不會頻繁地發(fā)生。

反復(fù)增倍法 (repeated doubling)：當(dāng)數(shù)組被填滿時，建立一個大小翻倍的新數(shù)組，然后將所有的元素復(fù)制過去。這樣我們就不會那么頻繁地創(chuàng)建新數(shù)組。

public class ResizingArrayStackOfStrings {

    private String[] s;

    //n 為棧的大小，棧中下一個開放位置，也為下一個元素的索引
    private int n = 0;

    public ResizingArrayStackOfStrings(){
        s = new String[2];
    }

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

    /**
     * 從大小為1的數(shù)組開始，如果發(fā)現(xiàn)數(shù)組被填滿，那么就在插入元素之前，將數(shù)組長度調(diào)整為原來的2倍
     * @param item
     */
    public void push(String item) {
        if (n == s.length) resize(2 * s.length);
        s[n++] = item;
    }

    /**
     * 調(diào)整數(shù)組方法
     * 創(chuàng)建具有目標(biāo)容量的新數(shù)組，然后把當(dāng)前棧復(fù)制到新棧的前一半
     * 然后重新設(shè)置和返回實例標(biāo)量
     * @param capacity
     */
    private void resize(int capacity) {
        System.out.println("resize when insert item "+ (n+1));
        String[] copy = new String[capacity];
        for (int i = 0; i < n; i++)
            copy[i] = s[i];
        s = copy;
    }

    public String pop() {
        return s[--n];
    }
}

往棧中插入 n 個元素的時間復(fù)雜度是線性相近的,即與 n 成正比 ~n

Q. 假設(shè)我們從一個空的棧開始，我們執(zhí)行 n 次入棧, 那么我們的 **resize()** 方法被調(diào)用了幾次？
A. 是以 2 為底的對數(shù)次。因為我們只有在棧的大小等于 2 的冪函數(shù)的時候，即 2^1,2^2,2^3 ... 2^i 的時候才會調(diào)用 resize().
   在 1 到 n 之間，符合 2 的冪的數(shù)字(如 2,4,8,16...) 一共有 logn 個，其中 log 以為 2 為底.

我們在插入 2^i 個元素時，需要復(fù)制數(shù)組 logn 次，需要花費訪問數(shù)組 n + (2 + 4 + 8 + ... + m) ~3n 的時間，其中 m = 2^logn = n

n : 無論數(shù)組翻不翻倍，對于每個新元素，入棧需要 Θ(1) 時間。因此，對于 n 個元素，它需要 Θ(n) 時間。即忽略常數(shù)項，插入 n 個 就有 n 次入棧的操作，就訪問 n 次數(shù)組

(2 + 4 + 8 + ... + n)：

如果 n = 2^i 個元素入棧，需要數(shù)組翻倍 lgn 次。
從技術(shù)上講，總和（2 + 4 + 8 + .. + m）是具有 logN 個元素的幾何級數(shù)
然后：（2 + 4 + 8 + .. + m）= 2 *(2 ^ log N - 1) = 2(N - 1) = 2N - 2 ~2N

=> N +（2 + 4 + 8 + .. + N）= N + 2N - 2 = 3N - 2 ~3N

舉個栗子~，如果我們往棧中插入 8 (2^3) 個元素，那么我們必須將數(shù)組翻倍 lg8 次，即3次。因此，8個元素入棧的開銷為 8 +（2 + 4 + 8）= 22 次 ≈ 24 次

再舉個栗子~，如果插入 16 (2^4) 個元素，那么我們必須將數(shù)組翻倍 lg16 次，即4次。因此，16個元素入棧的開銷為 16 +（2 + 4 + 8 + 16）= 46 次 ≈ 48 次

或者粗略想象一下，如果我們計算一下開銷，插入前 n (n = 2^i) 個元素，是對 2 的冪從1到N求和。 這樣，總的開銷大約是3N。先要訪問數(shù)組一次，對于復(fù)制要訪問兩次。所以，要插入元素，大約需要訪問數(shù)組三次。
下邊的圖是觀察時間開銷的另一種方式，表示了入棧操作需要訪問數(shù)組的次數(shù)。

每次遇到2的冪，需要進(jìn)行斜線上的數(shù)組訪問時間，但是從宏觀上來看，是將那些元素入棧上花去了紅色直線那些時間 這叫做平攤分析?？紤]開銷時將總的開銷平均給所有的操作。關(guān)于平攤分析就不再解釋了，有興趣可以自行了解...

如果數(shù)組翻倍多次后，又有多次出棧，那么如果不調(diào)整數(shù)組大小，數(shù)組可能會變得太空。那數(shù)組在什么情況下去縮小，縮小多少才合適？
我們也許這么考慮，當(dāng)數(shù)組滿了的時候?qū)⑷萘糠?，那么?dāng)它只有一半滿的時候，將容量縮減一半。但是這樣并不合理，因為有一種現(xiàn)象叫做thrashing：即客戶端剛好反復(fù)交替入棧出棧入棧出棧...

如果數(shù)組滿了就會反復(fù)翻倍減半翻倍減半，并且每個操作都會新建數(shù)組，都要花掉正比與N的時間，這樣就會導(dǎo)致thrashing頻繁發(fā)生要花費平方時間，這不是我們想要的。

有效的解決方案是直到數(shù)組變?yōu)?1/4 滿的時候才將容量減半
我們只要測試數(shù)組是否為 1/4 滿，如果是，則調(diào)整大小使其為 1/2 滿。

不變式：數(shù)組總是介于25% 滿與全滿之間

 public String pop()
 {
     String item = s[--n];
     //解決之前說的對象引用游離問題
     s[n] = null;
     if (n > 0 && n == s.length/4) resize(s.length/2);
     return item;
 }

這樣的好處:

因為是半滿的，既可以插入向棧插入元素，又可以從棧刪除元素，而不需要再次進(jìn)行調(diào)整數(shù)組大小的操作直到數(shù)組全滿，或者再次1/4滿。

每次調(diào)整大小時, 開銷已經(jīng)在平攤給了每次入棧和出棧

下圖展示了上邊測試寫的客戶端例子中數(shù)組上的操作

可以看到在開始時，數(shù)組大小從1倍增到2又到4，但一旦到8，數(shù)組的大小則維持一段時間不變，直到數(shù)組中只有2個元素時才縮小到4，等等。

數(shù)組調(diào)整大小并不經(jīng)常發(fā)生，但這是實現(xiàn)棧API的一種很有效的方式，客戶端不需要提供棧的最大容量，但依然保證了我們使用的內(nèi)存大小總是棧中實際元素個數(shù)的常數(shù)倍，所以分析說明對于任意的操作序列，每個操作的平均運行時間與常數(shù)成正比。

這里，存在最壞情況(worst case)。當(dāng)棧容量翻倍時，需要正比于N的時間，所以性能不如我們想要的那么好，但是優(yōu)勢在于進(jìn)行入棧出棧操作時非常快，入棧只需要訪問數(shù)組并移動棧頂索引。對于大多數(shù)操作都很高效的。對于眾多的客戶端這是個很有效的權(quán)衡。

棧的內(nèi)存用量實際上比鏈表使用更少的內(nèi)存。

給出的命題. 一個 ResizingArrayStackOfStrings 內(nèi)存用量在 ~8n bytes 到 ~32n bytes 之間，取決于數(shù)組有多滿。

只看 “private String[] s;”

?~ 8n 當(dāng)數(shù)組滿時. -- 棧的實際長度 = n，所以內(nèi)存占用是 8 乘以棧不為空的元素個數(shù)
?~ 32n 當(dāng)數(shù)組 1/4 滿時. -- 棧的實際長度 = 4n，所以內(nèi)存占用是 8 乘以(4 乘以棧的有效元素個數(shù))

這里只是計算了 Java中數(shù)組占用的空間。同樣地，這個分析只針對棧本身 而不包括客戶端上的字符串。

那么使用可調(diào)整大小的數(shù)組與鏈表之間如何取舍呢？

這是兩種 API相同的不同的實現(xiàn)，客戶端可以互換使用。

哪個更好呢？

很多情形中，我們會有同一API的多種實現(xiàn)。你需要根據(jù)客戶端的性質(zhì)選擇合適的實現(xiàn)。

Linked-list implementation.

對于鏈表，每個操作最壞情況下需要常數(shù)時間，這是有保障的

但是為了處理鏈接，我們需要一些額外的時間和空間。所以鏈表實現(xiàn)會慢一些

Resizing-array implementation.

可調(diào)大小的數(shù)組實現(xiàn)有很好的分?jǐn)倳r間，所以整個過程總的平均效率不錯

浪費更少的空間，對于每個操作也許有更快的實現(xiàn)

所以對于一些客戶端，也許會有區(qū)別。以下這樣的情形你不會想用可調(diào)大小數(shù)組實現(xiàn)：你有一架飛機進(jìn)場等待降落，你不想系統(tǒng)突然間不能高效運轉(zhuǎn)；或者互聯(lián)網(wǎng)上的一個路由器，數(shù)據(jù)包以很高的速度涌進(jìn)來，你不想因為某個操作突然變得很慢而丟失一些數(shù)據(jù)。

客戶端就可以權(quán)衡，如果想要獲得保證每個操作能夠很快完成，就使用鏈表實現(xiàn)；
如果不需要保證每個操作，只是關(guān)心總的時間，可能就是用可調(diào)大小數(shù)組實現(xiàn)。因為總的時間會小得多，如果不是最壞情況下單個操作非?？臁?br>盡管只有這些簡單的數(shù)據(jù)結(jié)構(gòu)，我們都需要做很重要的權(quán)衡，在很多實際情形中真的會產(chǎn)生影響。

接下來我們簡要考慮一下使用相同基本底層數(shù)據(jù)結(jié)構(gòu)的隊列的實現(xiàn)。

這是字符串隊列對應(yīng)的API，實際上和棧的API是相同的，只是名字不一樣而已...
入棧換成了入隊（enqueue），出棧換成了出隊（dequeue）。語義是不同的。
入隊操作向隊尾添加元素，而出隊操作從隊首移除元素。
就像你排隊買票一樣，入隊時你排在隊列的最后，在隊列里待的最久的人是下一個離開隊列的人。

數(shù)據(jù)結(jié)構(gòu)的性能要求：所有操作都花費常數(shù)時間。

隊列的鏈表表示中，我們需要維護(hù)兩個指針引用。一個是鏈表中的第一個元素，另一個是鏈表最后一個元素。

插入的時候我們在鏈表末端添加元素；移除元素的時候不變，依然從鏈表頭取出元素。

出隊 dequeue

那么這就是出隊操作的實現(xiàn)，和棧的出棧操作是一樣的。保存元素，前進(jìn)指針指向下一個節(jié)點，這樣就刪除了第一個節(jié)點，然后返回該元素。

入隊 enqueue

入隊操作時，向鏈表添加新節(jié)點。我們要把它放在鏈表末端，這樣它就是最后一個出隊的元素。
首先要做的是保存指向最后一個節(jié)點的指針，因為我們需要將它指向下一個節(jié)點的指針從null變?yōu)樾碌墓?jié)點。
然后給鏈表末端創(chuàng)建新的節(jié)點并對其屬性賦值，將舊的指針從null變?yōu)橹赶蛐鹿?jié)點。

實際上現(xiàn)在指針操作僅限于如棧和隊列這樣的少數(shù)幾個實現(xiàn)以及一些其他的基本數(shù)據(jù)結(jié)構(gòu)了?，F(xiàn)在很多操作鏈表的通用程序都封裝在了這樣的基本數(shù)據(jù)類型里。

Java 實現(xiàn)

這里處理了當(dāng)隊列為空時的特殊情況。為了保證去除最后一個元素后隊列是空的，我們將last設(shè)為null，還保證first和last始終都是符合我們預(yù)想。
完整代碼： Queue.java 這里用到了泛型和迭代器的實現(xiàn)

用可調(diào)大小的數(shù)組實現(xiàn)并不難，但絕對是一個棘手的編程練習(xí)。

我們維護(hù)兩個指針，分別指向隊列中的第一個元素和隊尾，即下一個元素要加入的地方。

對于入隊操作在 tail 指向的地方加入新元素

出隊操作移除 head 指向的元素

棘手的地方是一旦指針的位置超過了數(shù)組的容量，必須重置指針回到0，這里需要多寫一些代碼，而且和棧一樣實現(xiàn)數(shù)據(jù)結(jié)構(gòu)的時候你需要加上調(diào)整容量的方法。

完整代碼：ResizingArrayQueue.java

兩個棧實現(xiàn)隊列的數(shù)據(jù)結(jié)構(gòu)
實現(xiàn)具有兩個棧的隊列，以便每個隊列操作都是棧操作的常量次數(shù)(平攤次數(shù))。
提示：
1.如果將元素推入棧然后全部出棧，它們將以相反的順序出現(xiàn)。如果你重復(fù)這個過程，它們現(xiàn)在又恢復(fù)了正常的隊列順序。
2.為了避免不停的出棧入棧，可以加某個判定條件，比如當(dāng) dequeue 棧為空時，將 enqueue 棧的元素出棧到 dequeue 棧，然后最后從dequeue 棧出棧，也就實現(xiàn)了出隊的操作。直到 dequeue 棧的元素都出棧了，再次觸發(fā)出隊操作時，再從 enqueue 棧導(dǎo)入數(shù)據(jù)重復(fù)上邊的過程

實現(xiàn)參考：QueueWithTwoStacks.java

接下來我們要處理的是前面實現(xiàn)里另一個根本性的缺陷。前面的實現(xiàn)只適用于字符串，如果想要實現(xiàn)其他類型數(shù)據(jù)的隊列和棧怎么 StackOfURLs, StackOfInts... 嗯。。。
這個問題就涉及泛型的話題了。

實際上很多編程環(huán)境中這一點都是不得不考慮的。

第一種方法：我們對每一個數(shù)據(jù)類型都實現(xiàn)一個多帶帶的棧

這太雞肋了，我們要把代碼復(fù)制到需要實現(xiàn)棧的地方，然后把數(shù)據(jù)類型改成這個型那個型，那么如果我們要處理上百個不同的數(shù)據(jù)類型，我們就得有上百個不同的實現(xiàn)，想想就很心累。

不幸的是Java 推出 1.5 版本前就是陷在這種模式里，并且非常多的編程語言都無法擺脫這樣的模式。所以我們需要采用一種現(xiàn)代模式，不用給每個類型的數(shù)據(jù)都分別搞實現(xiàn)。

第二種方法：我們對 Object 類實現(xiàn)數(shù)據(jù)結(jié)構(gòu)
有一個廣泛采用的捷徑是使用強制類型轉(zhuǎn)換對不同的數(shù)據(jù)類型重用代碼。Java中所有的類都是 Object 的子類，當(dāng)客戶端使用時，就將結(jié)果轉(zhuǎn)換為對應(yīng)的類型。但是這種解決方案并不令人滿意。
這個例子中我們有兩個棧：蘋果的棧和桔子的棧。接下來，當(dāng)從蘋果棧出棧的時候需要客戶端將出棧元素強制轉(zhuǎn)換為蘋果類型，這樣類型檢查系統(tǒng)才不會報錯。

這樣做的問題在于：

必須客戶端完成強制類型轉(zhuǎn)換，通過編譯檢查。

存在一個隱患，如果類型不匹配，會發(fā)生運行時錯誤。

第三種方法：使用泛型

這種方法中客戶端程序不需要強制類型轉(zhuǎn)換。在編譯時就能發(fā)現(xiàn)類型不匹配的錯誤，而不是在運行時。

這個使用泛型的例子中棧的類型有一個類型參數(shù)(Apple)，在代碼里這個尖括號中。

如果我們有一個蘋果棧，并且試圖入棧一個桔子，我們在編譯時就會提示錯誤，因為聲明中那個棧只包含蘋果，桔子禁止入內(nèi)。

優(yōu)秀的模塊化編程的指導(dǎo)原則就是我們應(yīng)當(dāng)歡迎編譯時錯誤，避免運行時錯誤。

因為如果我們能在編譯時檢測到錯誤，我們給客戶交付產(chǎn)品或者部署對一個API的實現(xiàn)時，就有把握對于任何客戶端都是沒問題的。
有些運行時才會出現(xiàn)的錯誤可能在某些客戶端的開發(fā)中幾年之后才出現(xiàn)，如果這樣，就必須部署我們的軟件，這對每個人都是很困難的。

實際上優(yōu)秀的泛型實現(xiàn)并不難。只需要把每處使用的字符串替換為泛型類型名稱。

如這里的代碼所示，左邊是我們使用鏈表實現(xiàn)的字符串棧，右邊是泛型實現(xiàn)。

左邊每處用到字符串類型的地方我們換成了item。在最上面類聲明的地方我們用尖括號聲明 item 是我們要用的泛型類型，這樣的實現(xiàn)非常直截了當(dāng)，并且出色地解決了不同的數(shù)據(jù)類型多帶帶實現(xiàn)的問題。

基于數(shù)組的實現(xiàn)，這種方法不管用。目前很多編程語言這方面都有問題，而對Java尤其是個難題。我們想做的是用泛型名稱 item 直接聲明一個新的數(shù)組。比如這樣：

public class FixedCapacityStack
{
 private Item[] s;
 private int n = 0;

     public FixedCapacityStack(int capacity)
     //看這里看這里像這樣，但是實際我們在java當(dāng)中我卻不能這樣方便的實現(xiàn)
     { s = new Item[capacity]; }

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

     public void push(Item item)
     { s[n++] = item; }

     public Item pop()
     { return s[--n]; }
}

如有備注的這行所示。其他部分都和之前的方法沒區(qū)別。不幸的是，Java不允許創(chuàng)建泛型數(shù)組。對于這個問題有各種技術(shù)方面的原因，在網(wǎng)上關(guān)于這個問題你能看到大量的爭論，這個不在我們討論的范圍之內(nèi)。關(guān)于協(xié)變的內(nèi)容，可以自行了解，嗯。。。我一會也去了解了解...

這里，要行得通我們需要加入強制類型轉(zhuǎn)換。
我們創(chuàng)建 Object 數(shù)組，然后將類型轉(zhuǎn)換為 item 數(shù)組。教授的觀點是優(yōu)秀的代碼應(yīng)該不用強制類型轉(zhuǎn)換, 要盡量避免強制類型轉(zhuǎn)換，因為它確實在我們的實現(xiàn)中留下了隱患。但這個情況中我們必須加入這個強制類型轉(zhuǎn)換。

當(dāng)我們編譯這個程序的時候，Java會發(fā)出警告信息說我們在使用未經(jīng)檢查或者不安全的操作，詳細(xì)信息需要使用-Xlint=unchecked 參數(shù)重新編譯。

我們加上這個參數(shù)重新編譯之后顯示你在代碼中加入了一個未經(jīng)檢查的強制類型轉(zhuǎn)換，然后 java 就警告你不應(yīng)該加入未經(jīng)檢查的強制類型轉(zhuǎn)換。但是這么做并不是我們的錯，因為你不允許我們聲明泛型數(shù)組，我們才不得不這么做。收到這個警告信息請不要認(rèn)為是你的代碼中有什么問題。

接下來，是個跟Java有關(guān)的細(xì)節(jié)問題，
Q. 對基本數(shù)據(jù)類型，我們怎樣使用泛型？
我們用的泛型類型是針對 Object 及其子類的。前面講過，是從 Object 數(shù)組強制類型轉(zhuǎn)換來的。為了處理基本類型，我們需要使用Java的包裝對象類型。

如大寫的 Integer 是整型的包裝類型等等。另外，有個過程叫自動打包，自動轉(zhuǎn)換基本類型與包裝類型，所以處理基本類型這個問題，基本上都是在后臺完成的.

Autoboxing：基本數(shù)據(jù)類型到包裝類型的自動轉(zhuǎn)換。
unboxing：包裝器類型到基本數(shù)據(jù)類型的自動轉(zhuǎn)換。

綜上所述，我們能定義適用于任何數(shù)據(jù)類型的泛型棧的API，而且我們有基于鏈表和數(shù)組兩種實現(xiàn)。我們講過的使用可變大小數(shù)組或者鏈表，對于任何數(shù)據(jù)類型都有非常好的性能。

在 Java 6, 必須在變量聲明（左側(cè)）和構(gòu)造函數(shù)調(diào)用（右側(cè)）中指定具體類型。從Java 7 開始，可以使用菱形運算符:
Stack stack = new Stack<>();

Q. 為什么Java需要強制轉(zhuǎn)換（或反射）？
簡短的回答: 向后兼容性。
詳細(xì)地回答：需要了解類型擦除和協(xié)變數(shù)組

Q. 當(dāng)我嘗試創(chuàng)建泛型數(shù)組時，為什么會出現(xiàn)“無法創(chuàng)建泛型數(shù)組”錯誤？
public class ResizingArrayStack {Item[] a = new Item[1];}

A. 根本原因是Java中的數(shù)組是協(xié)變的，但泛型不是。換句話說，String [] 是 Object [] 的子類型，但 Stack 不是 Stack