Java/堆疊之道
abstract data typeseeADT ADT encapsulation
到目前為止，我們所見過的所有資料型別都是具體的，因為我們已經完全指定了它們的實現方式。例如，Card 類使用兩個整數來表示一張卡片。正如我在當時討論的那樣，這不是表示卡片的唯一方式；還有許多替代的實現方式。
抽象資料型別（ADT）指定了一組操作（或方法）以及操作的語義（它們的作用），但它沒有指定操作的實現方式。這就是它抽象的原因。
專案符號
如果你可以指定所需的運算而不必同時考慮運算的執行方式，那麼這將簡化指定演算法的任務。
由於通常有許多方法可以實現 ADT，因此編寫可與任何可能的實現方式一起使用的演算法可能會有用。
眾所周知的 ADT（例如本章中的堆疊 ADT）通常在標準庫中實現，因此可以編寫一次，由許多程式設計師使用。
ADT 上的操作為指定和討論演算法提供了通用的高階語言。
專案符號
當我們談論 ADT 時，我們經常將使用 ADT 的程式碼（稱為客戶端程式碼）與實現 ADT 的程式碼（稱為提供者程式碼）區分開來，因為它提供了一組標準服務。
client provider
stack collection ADT!Stack
在本章中，我們將研究一種常見的 ADT，即堆疊。堆疊是一種集合，這意味著它是一種包含多個元素的資料結構。我們見過的其他集合包括陣列和列表。
正如我所說，ADT 由一組操作定義。堆疊可以執行以下操作集
描述
[建構函式:] 建立一個新的空堆疊。
[push:] 向堆疊新增一個新專案。
[pop:] 從堆疊中刪除並返回一個專案。返回的專案始終是最後新增的專案。
[empty:] 檢查堆疊是否為空。
描述
堆疊有時被稱為“後進先出”或 LIFO 資料結構，因為最後新增的專案是第一個被移除的專案。
Stack class!Stack generic data structure data structure!generic
Java 提供了一個名為 Stack 的內建物件型別，它實現了堆疊 ADT。你應該努力使這兩件事（ADT 和 Java 實現）保持一致。在使用 Stack 類之前，我們必須從 java.util 中匯入它。
然後構造一個新 Stack 的語法是
逐字
Stack stack = new Stack ();
逐字
最初堆疊為空，我們可以用 empty 方法確認，該方法返回一個布林值
逐字
System.out.println (stack.empty ());
逐字
堆疊是一種泛型資料結構，這意味著我們可以向其中新增任何型別的專案。但是，在 Java 實現中，我們只能新增物件型別。在我們的第一個示例中，我們將使用 Node 物件，如上一章中定義的那樣。讓我們從建立和列印一個簡短的列表開始。
逐字
LinkedList list = new LinkedList (); list.addFirst (3); list.addFirst (2); list.addFirst (1); list.print ();
逐字
輸出是 (1, 2, 3)。要將 Node 物件放入堆疊，請使用 push 方法
verbatim stack.push (list.head); verbatim
以下迴圈遍歷列表並將所有節點推入堆疊
逐字
for (Node node = list.head; node != null; node = node.next)
stack.push (node);
逐字
我們可以使用 pop 方法從堆疊中刪除一個元素。
逐字
Object obj = stack.pop ();
逐字
pop 的返回型別是 Object！這是因為堆疊實現實際上不知道它包含的物件的型別。當我們推入 Node 物件時，它們會自動轉換為 Object。當我們從堆疊中取回它們時，我們必須將它們轉換回 Node。
verbatim Node node = (Node) obj; System.out.println (node); verbatim
不幸的是，跟蹤堆疊中的物件並在從堆疊中刪除它們時將其轉換回正確的型別的責任落在了程式設計師身上。如果你嘗試將物件轉換為錯誤的型別，你將得到一個 ClassCastException。
以下迴圈是在堆疊為空時停止，彈出堆疊中所有元素的常用慣用法
逐字
while (!stack.empty ())
Node node = (Node) stack.pop ();
System.out.print (node + " ");
逐字
輸出是 3 2 1。換句話說，我們剛剛使用堆疊以相反的順序列印了列表的元素！當然，這不是列印列表的標準格式，但使用堆疊，這樣做非常容易。
你應該將這段程式碼與上一章中 printBackward 的實現進行比較。這裡遞迴版本的 printBackward 和堆疊演算法之間存在自然的平行關係。區別在於 printBackward 使用執行時堆疊跟蹤節點，同時遍歷列表，然後在從遞迴返回時列印它們。堆疊演算法做同樣的事情，只是使用 Stack 物件而不是執行時堆疊。
wrapper class class!wrapper object type primitive type
對於 Java 中的每種基本型別，都有一個名為包裝類的內建物件型別。例如，int 的包裝類稱為 Integer；對於 double，它被稱為 Double。
包裝類很有用，原因如下
專案符號
你可以例項化包裝類並建立包含基本值的 物件。換句話說，你可以將基本值包裝在一個物件中，這在你需要呼叫需要物件型別的方法時很有用。
每個包裝類都包含特殊值（例如型別的最小值和最大值）以及用於型別之間轉換的有用方法。
專案符號
wrapper class!instantiating
建立包裝物件最直接的方法是使用其建構函式
逐字
Integer i = new Integer (17);
Double d = new Double (3.14159);
Character c = new Character ('b');
逐字
從技術上講，String 不是包裝類，因為沒有相應的基本型別，但建立 String 物件的語法相同
逐字
String s = new String ("fred");
逐字
另一方面，沒有人使用 String 物件的建構函式，因為你可以用簡單的 String 值獲得相同的效果
逐字
String s = "fred";
逐字
一些包裝類具有第二個建構函式，該建構函式以 String 作為引數並嘗試轉換為適當的型別。例如
逐字
Integer i = new Integer ("17");
Double d = new Double ("3.14159");
逐字
型別轉換過程不是很健壯。例如，如果 String 格式不正確，它們將導致 NumberFormatException。String 中的任何非數字字元（包括空格）都將導致轉換失敗。
NumberFormatException exception!NumberFormat
逐字
Integer i = new Integer ("17.1"); // WRONG!!
Double d = new Double ("3.1459 "); // WRONG!!
逐字
在嘗試轉換 String 之前，通常最好檢查 String 的格式。
wrapper class!extracting value
Java 知道如何列印包裝物件，因此提取值的 easiest 方式就是列印物件
逐字
Integer i = new Integer (17); Double d = new Double (3.14159); System.out.println (i); System.out.println (d);
逐字
或者，你可以使用 toString 方法將包裝物件的內容轉換為 String
逐字
String istring = i.toString(); String dstring = d.toString();
逐字
最後，如果你只想從物件中提取基本值，每個包裝類中都有一個物件方法可以完成這項工作
逐字
int iprim = i.intValue (); double dprim = d.doubleValue ();
逐字
還有將包裝物件轉換為不同基本型別的方法。你應該檢視每個包裝類的文件，以瞭解有哪些可用方法。
wrapper class!methods
正如我提到的，包裝類包含與每個型別相關的有用方法。例如，Character 類包含許多用於將字元轉換為大小寫以及檢查字元是否為數字、字母或符號的方法。
String 類還包含用於轉換為大小寫的方法。但是請記住，它們是函式，而不是修飾符（參見不可變部分）。
舉個例子，Integer 類包含用於以不同進位制解釋和列印整數的方法。如果有一個包含以 6 進製表示的數字的字串，可以使用 parseInt 將其轉換為 10 進位制。
逐字
String base6 = "12345"; int base10 = Integer.parseInt (base6, 6); System.out.println (base10);
逐字
由於 parseInt 是一個類方法，因此可以透過點表示法命名類和方法來呼叫它。
6 進位制可能沒有那麼有用，但十六進位制（16 進位制）和八進位制（8 進位制）在與計算機科學相關的領域中很常見。
字尾表示式
[edit | edit source]postfix infix expressions
在大多數程式語言中，數學表示式是用運算子放在兩個運算元之間來寫的，比如 1+2。這種格式稱為中綴。一些計算器使用另一種稱為字尾的格式。在後綴中，運算子位於運算元之後，例如 1 2+。
字尾有時很有用，因為有一種使用堆疊自然地計算字尾表示式的辦法。
專案符號
從表示式的開頭開始，一次獲取一個項（運算子或運算元）。
專案符號
如果該項是運算元，則將其壓入堆疊。
如果該項是運算子，則從堆疊中彈出兩個運算元，對它們執行操作，並將結果壓回堆疊。
專案符號
當我們到達表示式的末尾時，堆疊上應該只剩下一個運算元。這個運算元就是結果。
專案符號
作為練習，將此演算法應用於表示式 1 2 + 3 *。
此示例演示了字尾的一個優勢：不需要使用括號來控制操作順序。要獲得相同的結果，在中綴中，我們必須寫成 (1 + 2) * 3。作為練習，寫一個與 1 + 2 * 3 等效的字尾表示式？
解析
[edit | edit source]parse token delimiter class!StringTokenizer StringTokenizer class
為了實現上一節中的演算法，我們需要能夠遍歷一個字串，並將其分解為運算元和運算子。這個過程是一個解析的例子，結果——字串的各個片段——被稱為標記。
Java 提供了一個名為 StringTokenizer 的內建類，它解析字串並將它們分解成標記。要使用它，必須從 java.util 中匯入它。
在最簡單的形式中，StringTokenizer 使用空格來標記標記之間的邊界。一個標記邊界的字元稱為分隔符。
我們可以透過通常的方式建立一個 StringTokenizer，將要解析的字串作為引數傳遞。
逐字
StringTokenizer st = new StringTokenizer ("Here are four tokens.");
逐字
以下迴圈是用於從 StringTokenizer 中提取標記的標準慣用法。
逐字
while (st.hasMoreTokens ())
System.out.println (st.nextToken());
逐字
輸出是
verbatim 這裡有四個標記。 verbatim
為了解析表示式，我們可以選擇指定其他將用作分隔符的字元
逐字
StringTokenizer st = new StringTokenizer ("11 22+33*", " +-*/");
逐字
第二個引數是一個包含所有將用作分隔符的字元的字串。現在輸出是
verbatim 11 22 33 verbatim
這成功地提取了所有運算元，但我們丟失了運算子。幸運的是，StringTokenizer 還有另一種選擇。
逐字
StringTokenizer st = new StringTokenizer ("11 22+33*", " +-*/", true);
逐字
第三個引數表示，“是的，我們想將分隔符也作為標記處理”。現在輸出是
verbatim 11 verbatim
22 + 33
逐字
這正是我們用來計算這個表示式的標記流。
實現 ADT
[edit | edit source]encapsulation ADT
ADT 的基本目標之一是分離提供者（編寫實現 ADT 的程式碼的人）和客戶端（使用 ADT 的人）的關注點。提供者只需擔心實現是否正確——符合 ADT 的規範——而不必擔心如何使用它。
相反，客戶端假設 ADT 的實現是正確的，並且不關心細節。當您使用 Java 的內建類之一時，您可以享受只作為客戶端思考的便利。
另一方面，當您實現 ADT 時，您還需要編寫客戶端程式碼來測試它。在這種情況下，您有時必須仔細考慮在特定時刻扮演的是哪種角色。
在接下來的幾節中，我們將換個思路，看看使用陣列實現 Stack ADT 的一種方法。開始像提供者一樣思考。
Stack ADT 的陣列實現
[edit | edit source]arraystack
implementation!Stack stack!array implementation
此實現的例項變數是一個 Object 陣列，它將包含堆疊中的專案，以及一個整數索引，它將跟蹤陣列中下一個可用的空間。最初，陣列為空，索引為 0。
要向堆疊中新增元素（push），我們將對其引用複製到堆疊上，並增加索引。要刪除元素（pop），我們必須先減少索引，然後將元素複製出來。
以下是類定義
verbatim public class Stack verbatim
Object[] array; int index;
public Stack ()
this.array = new Object[128];
this.index = 0;
逐字
像往常一樣，一旦我們選擇了例項變數，編寫建構函式就是一個機械過程。現在，預設大小為 128 個專案。稍後我們將考慮處理此問題的更好方法。
檢查空堆疊是微不足道的。
逐字
public boolean empty ()
return index == 0;
逐字
但是，重要的是要記住，堆疊中的元素數量與陣列的大小不同。最初，大小為 128，但元素數量為 0。
push 和 pop 的實現自然地遵循規範。
逐字
public void push (Object item)
array[index] = item;
index++;
public Object pop ()
index--;
return array[index];
逐字
為了測試這些方法，我們可以利用我們用來練習內建 Stack 的客戶端程式碼。我們只需要註釋掉行 import java.util.Stack。然後，程式將使用我們剛剛編寫的實現，而不是使用 java.util 中的堆疊實現。
如果一切按計劃進行，程式應該無需任何額外更改即可執行。再一次，使用 ADT 的優勢之一是，您可以更改實現而無需更改客戶端程式碼。
調整陣列大小
[edit | edit source]resize
array!resizing ArrayIndexOutOfBounds exception!ArrayIndexOutOfBounds
此實現的一個缺點是，它在建立 Stack 時為陣列選擇了一個任意大小。如果使用者向堆疊中推入超過 128 個專案，它將導致 ArrayIndexOutOfBounds 異常。
ArrayIndexOutOfBounds exception!ArrayIndexOutOfBounds
另一種方法是讓客戶端程式碼指定陣列的大小。這可以緩解問題，但它要求客戶端提前知道需要多少個專案，而這並不總是可能的。
更好的解決方案是在必要時檢查陣列是否已滿，並將其變大。由於我們不知道陣列需要多大，所以從一個小尺寸開始，每次溢位時將其加倍是一個合理的策略。
以下是 push 的改進版本
逐字
public void push (Object item)
if (full ()) resize ();
// at this point we can prove that index < array.length
array[index] = item;
index++;
逐字
在將新專案放入陣列之前，我們檢查陣列是否已滿。如果是，則呼叫 resize。在 if 語句之後，我們知道要麼 (1) 陣列中有空間，要麼 (2) 陣列已調整大小，並且有空間。如果 full 和 resize 是正確的，那麼我們可以證明 index < array.length，因此下一條語句不會導致異常。
現在我們只需要實現 full 和 resize 即可。
逐字
private boolean full ()
return index == array.length;
private void resize ()
Object[] newArray = new Object[array.length * 2];
// we assume that the old array is full
for (int i=0; i<array.length; i++)
newArray[i] = array[i];
array = newArray;
逐字
這兩個方法都被宣告為私有，這意味著它們不能從另一個類呼叫，只能從當前類內部呼叫。這是可以接受的，因為沒有理由讓客戶端程式碼使用這些函式，並且是可取的，因為它強制執行了實現和客戶端之間的邊界。
method!private private method
full 的實現是微不足道的；它只是檢查索引是否超出了有效索引範圍。
resize 的實現很簡單，但有一個前提，即它假定舊陣列已滿。換句話說，這個假設是這個方法的前提條件。很容易看出這個前提條件是滿足的，因為 resize 被呼叫的唯一方式是 full 返回 true，而這隻有在 index == array.length 時才會發生。
在 resize 的末尾，我們用新陣列替換舊陣列（導致舊陣列被垃圾回收）。新的 array.length 是舊陣列的兩倍，而 index 沒有改變，所以現在必須為真 index < array.length。這個斷言是 resize 的後置條件：在方法完成時必須為真的內容（只要它的前提條件得到滿足）。
前提條件、後置條件和不變式是用於分析程式和證明其正確性的有用工具。在本例中，我演示了一種有利於程式分析的程式設計風格和一種有助於證明正確性的文件風格。
precondition postcondition invariant
ADT client provider wrapper class infix postfix parse token delimiter predicate postcondition
描述
[抽象資料型別 (ADT):] 一種由一組操作定義的資料型別（通常是物件的集合），但可以以多種方式實現。
[客戶端:] 使用 ADT 的程式（或編寫該程式的人）。
[提供者:] 實現 ADT 的程式碼（或編寫該程式碼的人）。
[包裝類:] 一些 Java 類，如 Double 和 Integer，它們提供物件來包含原始型別，以及對原始型別進行操作的方法。
[私有:] 一個 Java 關鍵字，表示方法或例項變數不能從當前類定義之外訪問。
[中綴:] 一種用運算子位於運算元之間的形式來編寫數學表示式的格式。
[字尾:] 一種用運算子位於運算元之後的形式來編寫數學表示式的格式。
[解析:] 讀取字元或標記字串並分析其語法結構。
[標記:] 一組字元，在解析時被視為一個單元，就像自然語言中的詞語一樣。
[分隔符:] 用於分隔標記的字元，就像自然語言中的標點符號一樣。
[謂詞:] 一種數學命題，要麼為真，要麼為假。
[後置條件:] 在方法結束時必須為真的謂詞（前提是在開始時為真的）。