1. 棧的定義
Stack是Vector的一個子類，它實現標準的后進先出堆棧。Stack只定義了創建空堆棧的默認構造方法。（實際上是實現了List接口，因為Vector是List的子類）。
Stack() // 創建一個空棧
2. 棧的基本操作
// 壓棧操作
public E push(E item) // 將元素壓入棧頂// 彈棧操作
public E pop() // 移除棧頂元素并返回該元素// 查看棧頂元素但不移除
public E peek() // 查看棧頂元素但不移除// 判斷棧是否為空
public boolean empty() // 測試棧是否為空// 查找元素在棧中的位置（從棧頂開始為1）
public int search(Object o) // 返回對象在棧中的位置，1表示棧頂3. 繼承自Vector的方法
由于Stack繼承自Vector，所以還擁有以下方法：
// 獲取棧的大小
public int size() // 判斷棧是否包含指定元素
public boolean contains(Object o)// 返回指定位置的元素
public E get(int index)// 清空棧
public void clear()4. Java 中的 Stack 類
Java 提供了一個內置的 Stack 類，它擴展了 Vector 類。盡管 Stack 類仍然可用，但在現代 Java 編程中，通常推薦使用 Deque 接口的實現（如 ArrayDeque ）來模擬棧的行為。
- 由于Stack繼承自Vector，所有方法都是同步的，這在多線程環境下是安全的，但在單線程環境下會有性能損失。
Deque接口提供了更完整的棧操作，性能更好（非同步實現）
4.1. 使用 Java 的 Stack 類
import java.util.Stack;public class StackExample {public static void main(String[] args) {Stack<String> stack = new Stack<>();// 壓棧操作stack.push("Apple");stack.push("Banana");stack.push("Cherry");// 查看棧大小System.out.println("Stack size: " + stack.size()); // 輸出: 3// 查看棧頂元素System.out.println("Top element: " + stack.peek()); // 輸出: Cherry// 彈棧操作System.out.println("Popped: " + stack.pop()); // 輸出: CherrySystem.out.println("Popped: " + stack.pop()); // 輸出: Banana// 判斷棧是否為空System.out.println("Is stack empty? " + stack.empty()); // 輸出: false// 查找元素位置System.out.println("Apple position: " + stack.search("Apple")); // 輸出: 1// 清空棧stack.clear();System.out.println("Is stack empty after clear? " + stack.empty()); // 輸出: true}
}4.2. 使用 Deque 接口實現棧
import java.util.ArrayDeque;
import java.util.Deque;public class DequeAsStackExample {public static void main(String[] args) {Deque<String> stack = new ArrayDeque<>();// 壓棧stack.push("Apple");stack.push("Banana");stack.push("Cherry");System.out.println("Stack: " + stack);// 出棧String top = stack.pop();System.out.println("Popped element: " + top);// 查看System.out.println("Top element: " + stack.peek());System.out.println("Updated stack: " + stack);// 判空System.out.println("Is stack empty? " + stack.isEmpty());}
}
5. 實現自定義棧
我們可以使用數組或鏈表來實現自定義棧。以下是使用數組實現的簡單棧：
public class ArrayStack<T> {private T[] array;private int top;private int capacity;@SuppressWarnings("unchecked")public ArrayStack(int capacity) {this.capacity = capacity;array = (T[]) new Object[capacity];top = -1;}public void push(T item) {if (isFull()) {throw new IllegalStateException("Stack is full");}array[++top] = item;}public T pop() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return array[top--];}public T peek() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return array[top];}public boolean isEmpty() {return top == -1;}public boolean isFull() {return top == capacity - 1;}
}
6. 棧的應用
棧在計算機科學和日常編程中有廣泛的應用，例如：
- 函數調用和遞歸
- 表達式求值和語法解析
- 撤銷操作（Undo）
- 深度優先搜索（DFS）算法
- 括號匹配問題
7. 棧的實際應用示例
7.1. 括號匹配
public static boolean isBalanced(String expression) {Stack<Character> stack = new Stack<>();for (char ch : expression.toCharArray()) {if (ch == '(' || ch == '[' || ch == '{') {stack.push(ch);} else if (ch == ')' || ch == ']' || ch == '}') {if (stack.isEmpty()) {return false;}char top = stack.pop();if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) {return false;}}}return stack.isEmpty();
}
7.2. 逆波蘭表達式求值
public static int evaluateRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String token : tokens) {if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {int b = stack.pop();int a = stack.pop();switch (token) {case "+": stack.push(a + b); break;case "-": stack.push(a - b); break;case "*": stack.push(a * b); break;case "/": stack.push(a / b); break;}} else {stack.push(Integer.parseInt(token));}}return stack.pop();
}8. 棧的優缺點
優點：
- 實現簡單
- 后進先出的特性適用于許多算法和問題解決
- 函數調用和遞歸的基礎
缺點：
- 只能訪問最頂端的元素
- 不支持隨機訪問
- 大小通常是固定的（使用數組實現時）
9. 參考資料
Java 數據結構 - 棧(Stack) - KenWan - 博客園
