Java中的棧

一、棧簡介

棧是一種數據結構，它具有先進後出的特點。在Java中，棧可以用Stack類來表示。同時，Java還提供了Deque（雙端隊列）和LinkedList類，它們也可以表示棧。

棧的操作主要包括壓棧（push）、出棧（pop）、查看棧頂元素（peek）和獲取棧的大小（size）。在進行棧的操作時，需要注意棧是否為空以及棧是否已滿。

二、Stack類的使用

Stack類是Java中棧的標準實現。以下是Stack類的常見操作：

Stack<Integer> stack = new Stack<>();

// 壓棧
stack.push(1);
stack.push(2);
stack.push(3);

// 查看棧頂元素
System.out.println(stack.peek()); // 輸出3

// 出棧
System.out.println(stack.pop()); // 輸出3
System.out.println(stack.pop()); // 輸出2
System.out.println(stack.pop()); // 輸出1

// 判斷棧是否為空
System.out.println(stack.isEmpty()); // 輸出true

三、Deque和LinkedList類表示棧

Deque和LinkedList類也可以用來表示棧。以下是使用LinkedList類實現棧的示例：

LinkedList<Integer> stack = new LinkedList<>();

// 壓棧
stack.push(1);
stack.push(2);
stack.push(3);

// 查看棧頂元素
System.out.println(stack.peek()); // 輸出3

// 出棧
System.out.println(stack.pop()); // 輸出3
System.out.println(stack.pop()); // 輸出2
System.out.println(stack.pop()); // 輸出1

// 判斷棧是否為空
System.out.println(stack.isEmpty()); // 輸出true

四、棧的應用

棧在計算機中的應用非常廣泛，以下是幾個例子：

• 計算表達式。通過將中綴表達式轉換為後綴表達式，然後使用棧計算後綴表達式來得到正確的結果。
• 括號匹配。使用棧來判斷表達式中的括號是否匹配。
• 逆序輸出。可以使用棧來逆序輸出一個字符串。

五、棧的實現原理

在Java中，棧的底層實現是數組。當壓棧時，元素會被加入數組的末尾。當出棧時，數組末尾的元素被彈出。查看棧頂元素時，返回數組末尾的元素即可。

數組實現的棧的優點是速度快、效率高。缺點是數組大小是固定的，當棧中的元素數量超過數組大小時，需要進行擴容。擴容會帶來額外的空間和時間開銷。

另一種實現棧的方式是使用鏈表。鏈表實現的棧可以動態地增加和刪除元素，不需要擴容。

六、小結

棧是一種重要的數據結構，在Java中可以使用Stack類、Deque類和LinkedList類來表示。棧的應用非常廣泛，包括計算表達式、括號匹配和逆序輸出等。棧的底層實現可以使用數組或鏈表。