堆棧Stack · 《Java 編程思想》第五版

## [堆棧Stack](https://lingcoder.gitee.io/onjava8/#/book/12-Collections?id=%e5%a0%86%e6%a0%88stack) 堆棧是“后進先出”（LIFO）集合。它有時被稱為*疊加棧*（pushdown stack），因為最后“壓入”（push）棧的元素，第一個被“彈出”（pop）棧。經常用來類比棧的事物是帶有彈簧支架的自助餐廳托盤。最后裝入的托盤總是最先拿出來使用的。 Java 1.0 中附帶了一個**Stack**類，結果設計得很糟糕（為了向后兼容，我們永遠堅持 Java 中的舊設計錯誤）。Java 6 添加了**ArrayDeque**，其中包含直接實現堆棧功能的方法： ~~~ // collections/StackTest.java import java.util.*; public class StackTest { public static void main(String[] args) { Deque<String> stack = new ArrayDeque<>(); for(String s : "My dog has fleas".split(" ")) stack.push(s); while(!stack.isEmpty()) System.out.print(stack.pop() + " "); } } /* Output: fleas has dog My */ ~~~ 即使它是作為一個堆棧在使用，我們仍然必須將其聲明為**Deque**。有時一個名為**Stack**的類更能把事情講清楚： ~~~ // onjava/Stack.java // A Stack class built with an ArrayDeque package onjava; import java.util.Deque; import java.util.ArrayDeque; public class Stack<T> { private Deque<T> storage = new ArrayDeque<>(); public void push(T v) { storage.push(v); } public T peek() { return storage.peek(); } public T pop() { return storage.pop(); } public boolean isEmpty() { return storage.isEmpty(); } @Override public String toString() { return storage.toString(); } } ~~~ 這里引入了使用泛型的類定義的最簡單的可能示例。類名稱后面的告訴編譯器這是一個參數化類型，而其中的類型參數**T**會在使用類時被實際類型替換。基本上，這個類是在聲明“我們在定義一個可以持有**T**類型對象的**Stack**。”**Stack**是使用**ArrayDeque**實現的，而**ArrayDeque**也被告知它將持有**T**類型對象。注意，`push()`接受類型為**T**的對象，而`peek()`和`pop()`返回類型為**T**的對象。`peek()`方法將返回棧頂元素，但并不將其從棧頂刪除，而`pop()`刪除并返回頂部元素。如果只需要棧的行為，那么使用繼承是不合適的，因為這將產生一個具有**ArrayDeque**的其它所有方法的類（在[附錄：集合主題](https://lingcoder.gitee.io/onjava8/#/)中將會看到，**Java 1.0**設計者在創建**java.util.Stack**時，就犯了這個錯誤）。使用組合，可以選擇要公開的方法以及如何命名它們。下面將使用**StackTest.java**中的相同代碼來演示這個新的**Stack**類： ~~~ // collections/StackTest2.java import onjava.*; public class StackTest2 { public static void main(String[] args) { Stack<String> stack = new Stack<>(); for(String s : "My dog has fleas".split(" ")) stack.push(s); while(!stack.isEmpty()) System.out.print(stack.pop() + " "); } } /* Output: fleas has dog My */ ~~~ 如果想在自己的代碼中使用這個**Stack**類，當在創建其實例時，就需要完整指定包名，或者更改這個類的名稱；否則，就有可能會與**java.util**包中的**Stack**發生沖突。例如，如果我們在上面的例子中導入 \**java.util.\*\**，那么就必須使用包名來防止沖突： ~~~ // collections/StackCollision.java public class StackCollision { public static void main(String[] args) { onjava.Stack<String> stack = new onjava.Stack<>(); for(String s : "My dog has fleas".split(" ")) stack.push(s); while(!stack.isEmpty()) System.out.print(stack.pop() + " "); System.out.println(); java.util.Stack<String> stack2 = new java.util.Stack<>(); for(String s : "My dog has fleas".split(" ")) stack2.push(s); while(!stack2.empty()) System.out.print(stack2.pop() + " "); } } /* Output: fleas has dog My fleas has dog My */ ~~~ 盡管已經有了**java.util.Stack**，但是**ArrayDeque**可以產生更好的**Stack**，因此更可取。還可以使用顯式導入來控制對“首選”**Stack**實現的選擇： ~~~ import onjava.Stack; ~~~ 現在,任何對**Stack**的引用都將選擇**onjava**版本，而在選擇**java.util.Stack**時，必須使用全限定名稱（full qualification）。