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

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

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

對(duì)象的集合

操作：

insert -- 向集合中添加新的對(duì)象

remove -- 去掉集合中的某個(gè)元素

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

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

做插入和刪除操作時(shí)我們要明確以什么樣的形式去添加元素，或我們要?jiǎng)h除集合中的哪個(gè)元素。

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

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

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

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

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

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

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

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

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

Separate client and implementation via API.

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

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

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

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

性能要求：所有操作都花費(fèi)常數(shù)時(shí)間
客戶(hù)端：從標(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();
    //如果字符串為"-",則客戶(hù)端將棧頂?shù)淖址鰲?，并打印出棧的字符?    if (s.equals("-")) StdOut.print(stack.pop());
    //否則將字符串入棧到棧頂
    else stack.push(s);
    }
}

客戶(hù)端輸入輸出：

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

我們想保存一個(gè)有節(jié)點(diǎn)組成的，用來(lái)儲(chǔ)存字符串的鏈表。節(jié)點(diǎn)包含指向鏈表中下一個(gè)元素的引用(first).

維持指針 first 指向鏈表中的第一個(gè)節(jié)點(diǎn)

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

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

public class LinkedStackOfStrings
{
     //棧中唯一的實(shí)例變量是鏈表中的第一個(gè)節(jié)點(diǎn)的引用
     private Node first = null;
     
     //內(nèi)部類(lèi)，節(jié)點(diǎn)對(duì)象，構(gòu)成鏈表中的元素，由一個(gè)字符串和指向另一個(gè)節(jié)點(diǎn)的引用組成
     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é)點(diǎn)：我們將要插入表頭的節(jié)點(diǎn)
         first = new Node();
         first.item = item;
         //實(shí)例變量的next指針指向鏈表oldfirst元素，現(xiàn)在變成鏈表的第二個(gè)元素
         first.next = oldfirst;
     }
     
     //出棧
     public String pop()
     {
         //將鏈表中的第一個(gè)元素儲(chǔ)存在標(biāo)量 item 中
         String item = first.item;
         //去掉第一個(gè)節(jié)點(diǎn)：將原先指向第一個(gè)元素的指針指向下一個(gè)元素，然后第一個(gè)節(jié)點(diǎn)就等著被垃圾回收處理
         first = first.next;
         //返回鏈表中原先保存的元素
         return item;
     }
}

圖示：

出棧：

入棧：

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

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

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

另一種實(shí)現(xiàn)棧的 natural way 是使用數(shù)組儲(chǔ)存棧上的元素
將棧中的N個(gè)元素保存在數(shù)組中，索引為 n，n 對(duì)應(yīng)的數(shù)組位置即為棧頂?shù)奈恢?，即下一個(gè)元素加入的地方

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

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

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

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

public class FixedCapacityStackOfStrings
{
     private String[] s;
     //n 為棧的大小，棧中下一個(gè)開(kāi)放位置，也為下一個(gè)元素的索引
     private int n = 0;
     
    //int capacity：看以下說(shuō)明
     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()
     { 
         //然后返回?cái)?shù)組n-1的元素
         return s[--n]; 
     }
}

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

上述的實(shí)現(xiàn)中我們暫時(shí)沒(méi)有處理的問(wèn)題：

Overflow and underflow

Underflow ：客戶(hù)端從空棧中出棧我們沒(méi)有拋出異常

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

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

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

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

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

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

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

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

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

public class ResizingArrayStackOfStrings {

    private String[] s;

    //n 為棧的大小，棧中下一個(gè)開(kāi)放位置，也為下一個(gè)元素的索引
    private int n = 0;

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

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

    /**
     * 從大小為1的數(shù)組開(kāi)始，如果發(fā)現(xiàn)數(shù)組被填滿(mǎn)，那么就在插入元素之前，將數(shù)組長(zhǎng)度調(diào)整為原來(lái)的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è)置和返回實(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 個(gè)元素的時(shí)間復(fù)雜度是線(xiàn)性相近的,即與 n 成正比 ~n

Q. 假設(shè)我們從一個(gè)空的棧開(kāi)始，我們執(zhí)行 n 次入棧, 那么我們的 **resize()** 方法被調(diào)用了幾次？
A. 是以 2 為底的對(duì)數(shù)次。因?yàn)槲覀冎挥性跅５拇笮〉扔?2 的冪函數(shù)的時(shí)候，即 2^1,2^2,2^3 ... 2^i 的時(shí)候才會(huì)調(diào)用 resize().
   在 1 到 n 之間，符合 2 的冪的數(shù)字(如 2,4,8,16...) 一共有 logn 個(gè)，其中 log 以為 2 為底.

我們?cè)诓迦?2^i 個(gè)元素時(shí)，需要復(fù)制數(shù)組 logn 次，需要花費(fèi)訪問(wèn)數(shù)組 n + (2 + 4 + 8 + ... + m) ~3n 的時(shí)間，其中 m = 2^logn = n

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

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

如果 n = 2^i 個(gè)元素入棧，需要數(shù)組翻倍 lgn 次。
從技術(shù)上講，總和（2 + 4 + 8 + .. + m）是具有 logN 個(gè)元素的幾何級(jí)數(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

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

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

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

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

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

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

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

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

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

這樣的好處:

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

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

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

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

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

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

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

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

只看 “private String[] s;”

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

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

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

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

哪個(gè)更好呢？

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

Linked-list implementation.

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

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

Resizing-array implementation.

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

浪費(fèi)更少的空間，對(duì)于每個(gè)操作也許有更快的實(shí)現(xiàn)

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

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

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

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

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

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

插入的時(shí)候我們?cè)阪湵?strong>末端添加元素；移除元素的時(shí)候不變，依然從鏈表頭取出元素。

出隊(duì) dequeue

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

入隊(duì) enqueue

入隊(duì)操作時(shí)，向鏈表添加新節(jié)點(diǎn)。我們要把它放在鏈表末端，這樣它就是最后一個(gè)出隊(duì)的元素。
首先要做的是保存指向最后一個(gè)節(jié)點(diǎn)的指針，因?yàn)槲覀冃枰獙⑺赶蛳乱粋€(gè)節(jié)點(diǎn)的指針從null變?yōu)樾碌墓?jié)點(diǎn)。
然后給鏈表末端創(chuàng)建新的節(jié)點(diǎn)并對(duì)其屬性賦值，將舊的指針從null變?yōu)橹赶蛐鹿?jié)點(diǎn)。

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

Java 實(shí)現(xiàn)

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

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

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

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

出隊(duì)操作移除 head 指向的元素

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

完整代碼：ResizingArrayQueue.java

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

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

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

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

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

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

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

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

這樣做的問(wèn)題在于：

必須客戶(hù)端完成強(qiáng)制類(lèi)型轉(zhuǎn)換，通過(guò)編譯檢查。

存在一個(gè)隱患，如果類(lèi)型不匹配，會(huì)發(fā)生運(yùn)行時(shí)錯(cuò)誤。

第三種方法：使用泛型

這種方法中客戶(hù)端程序不需要強(qiáng)制類(lèi)型轉(zhuǎn)換。在編譯時(shí)就能發(fā)現(xiàn)類(lèi)型不匹配的錯(cuò)誤，而不是在運(yùn)行時(shí)。

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

如果我們有一個(gè)蘋(píng)果棧，并且試圖入棧一個(gè)桔子，我們?cè)诰幾g時(shí)就會(huì)提示錯(cuò)誤，因?yàn)槁暶髦心莻€(gè)棧只包含蘋(píng)果，桔子禁止入內(nèi)。

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

因?yàn)槿绻覀兡茉诰幾g時(shí)檢測(cè)到錯(cuò)誤，我們給客戶(hù)交付產(chǎn)品或者部署對(duì)一個(gè)API的實(shí)現(xiàn)時(shí)，就有把握對(duì)于任何客戶(hù)端都是沒(méi)問(wèn)題的。
有些運(yùn)行時(shí)才會(huì)出現(xiàn)的錯(cuò)誤可能在某些客戶(hù)端的開(kāi)發(fā)中幾年之后才出現(xiàn)，如果這樣，就必須部署我們的軟件，這對(duì)每個(gè)人都是很困難的。

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

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

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

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

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

     public FixedCapacityStack(int capacity)
     //看這里看這里像這樣，但是實(shí)際我們?cè)趈ava當(dāng)中我卻不能這樣方便的實(shí)現(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]; }
}

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

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

當(dāng)我們編譯這個(gè)程序的時(shí)候，Java會(huì)發(fā)出警告信息說(shuō)我們?cè)谑褂梦唇?jīng)檢查或者不安全的操作，詳細(xì)信息需要使用-Xlint=unchecked 參數(shù)重新編譯。

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

接下來(lái)，是個(gè)跟Java有關(guān)的細(xì)節(jié)問(wèn)題，
Q. 對(duì)基本數(shù)據(jù)類(lèi)型，我們?cè)鯓邮褂梅盒停?/strong>
我們用的泛型類(lèi)型是針對(duì) Object 及其子類(lèi)的。前面講過(guò)，是從 Object 數(shù)組強(qiáng)制類(lèi)型轉(zhuǎn)換來(lái)的。為了處理基本類(lèi)型，我們需要使用Java的包裝對(duì)象類(lèi)型。