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

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

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

對象的集合

操作：

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

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

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

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

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

處理這類問題有兩個經典的基礎數據結構：棧(stack) 和隊列(queue)

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

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

插入元素對應的術語是入棧 -- push；去掉最近加入的元素叫出棧 -- pop

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

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

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

這一原則的思想是將接口與實現完全分離。比如我們精確定義了一些數據類型和數據結構(如棧，隊列等)，我們想要的是把實現這些數據結構的細節(jié)完全與客戶端分離?？蛻舳丝梢赃x擇數據結構不同的實現方式，但是客戶端代碼只能執(zhí)行基本操作。

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

Separate client and implementation via API.

API：描述數據類型特征的操作
Client：使用API??操作的客戶端程序。
Implementation：實現API操作的代碼。

下面具體看下這兩種數據結構的實現

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

字符串數據類型的棧

性能要求：所有操作都花費常數時間
客戶端：從標準輸入讀取逆序的字符串序列

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())
    {
    //從標準輸入獲取一些字符串
    String s = StdIn.readString();
    //如果字符串為"-",則客戶端將棧頂的字符串出棧，并打印出棧的字符串
    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;
     
     //內部類，節(jié)點對象，構成鏈表中的元素，由一個字符串和指向另一個節(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元素，現在變成鏈表的第二個元素
         first.next = oldfirst;
     }
     
     //出棧
     public String pop()
     {
         //將鏈表中的第一個元素儲存在標量 item 中
         String item = first.item;
         //去掉第一個節(jié)點：將原先指向第一個元素的指針指向下一個元素，然后第一個節(jié)點就等著被垃圾回收處理
         first = first.next;
         //返回鏈表中原先保存的元素
         return item;
     }
}

圖示：

出棧：

入棧：

通過分析提供給客戶算法和數據結構的性能信息，評估這個實現對以不同客戶端程序的資源使用量

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

棧用鏈表是實現花費常數的時間，但是棧還有更快的實現

另一種實現棧的 natural way 是使用數組儲存棧上的元素
將棧中的N個元素保存在數組中，索引為 n，n 對應的數組位置即為棧頂的位置，即下一個元素加入的地方

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

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

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

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

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()
     { 
         //然后返回數組n-1的元素
         return s[--n]; 
     }
}

int capacity： 在構造函數中加入了容量的參數，破壞了API，需要客戶端提供棧的容量。不過實際上我們不會這么做，因為大多數情況下，客戶端也無法確定需要多大棧，而且客戶端也可能需要同時維護很多棧，這些棧又不同時間到達最大容量，同時還有其他因素的影響。這里只是為了簡化。在調整數組中會處理可變容量的問題，避免溢出

上述的實現中我們暫時沒有處理的問題：

Overflow and underflow

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

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

Null item：客戶端是否能向數據結構中插入空元素，上邊我們是允許的

Duplicate items: 客戶端是否能向數據結構中重復入棧同一個元素，上邊我們是允許的

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

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

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

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

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

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

public class ResizingArrayStackOfStrings {

    private String[] s;

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

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

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

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

    /**
     * 調整數組方法
     * 創(chuàng)建具有目標容量的新數組，然后把當前棧復制到新棧的前一半
     * 然后重新設置和返回實例標量
     * @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 個元素的時間復雜度是線性相近的,即與 n 成正比 ~n

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

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

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

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

如果 n = 2^i 個元素入棧，需要數組翻倍 lgn 次。
從技術上講，總和（2 + 4 + 8 + .. + m）是具有 logN 個元素的幾何級數
然后：（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) 個元素，那么我們必須將數組翻倍 lg8 次，即3次。因此，8個元素入棧的開銷為 8 +（2 + 4 + 8）= 22 次 ≈ 24 次

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

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

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

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

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

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

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

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

這樣的好處:

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

每次調整大小時, 開銷已經在平攤給了每次入棧和出棧

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

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

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

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

棧的內存用量實際上比鏈表使用更少的內存。

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

只看 “private String[] s;”

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

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

那么使用可調整大小的數組與鏈表之間如何取舍呢？

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

哪個更好呢？

很多情形中，我們會有同一API的多種實現。你需要根據客戶端的性質選擇合適的實現。

Linked-list implementation.

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

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

Resizing-array implementation.

可調大小的數組實現有很好的分攤時間，所以整個過程總的平均效率不錯

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

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

客戶端就可以權衡，如果想要獲得保證每個操作能夠很快完成，就使用鏈表實現；
如果不需要保證每個操作，只是關心總的時間，可能就是用可調大小數組實現。因為總的時間會小得多，如果不是最壞情況下單個操作非常快。
盡管只有這些簡單的數據結構，我們都需要做很重要的權衡，在很多實際情形中真的會產生影響。

接下來我們簡要考慮一下使用相同基本底層數據結構的隊列的實現。

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

數據結構的性能要求：所有操作都花費常數時間。

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

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

出隊 dequeue

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

入隊 enqueue

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

實際上現在指針操作僅限于如棧和隊列這樣的少數幾個實現以及一些其他的基本數據結構了。現在很多操作鏈表的通用程序都封裝在了這樣的基本數據類型里。

Java 實現

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

用可調大小的數組實現并不難，但絕對是一個棘手的編程練習。

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

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

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

棘手的地方是一旦指針的位置超過了數組的容量，必須重置指針回到0，這里需要多寫一些代碼，而且和棧一樣實現數據結構的時候你需要加上調整容量的方法。

完整代碼：ResizingArrayQueue.java

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

實現參考：QueueWithTwoStacks.java

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

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

第一種方法：我們對每一個數據類型都實現一個多帶帶的棧

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

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

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

這樣做的問題在于：

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

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

第三種方法：使用泛型

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

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

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

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

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

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

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

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

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

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

     public FixedCapacityStack(int capacity)
     //看這里看這里像這樣，但是實際我們在java當中我卻不能這樣方便的實現
     { 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)建泛型數組。對于這個問題有各種技術方面的原因，在網上關于這個問題你能看到大量的爭論，這個不在我們討論的范圍之內。關于協變的內容，可以自行了解，嗯。。。我一會也去了解了解...

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

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

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

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

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

Autoboxing：基本數據類型到包裝類型的自動轉換。
unboxing：包裝器類型到基本數據類型的自動轉換。

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

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

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

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

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