數據結構第06節：棧

棧（Stack）是一種后進先出（Last In First Out, LIFO）的數據結構，它只允許在一端，稱為棧頂（Top），進行添加（Push）和移除（Pop）數據項的操作。棧常用于解決遞歸、回溯、函數調用等問題。

棧的基本操作包括：

Push: 向棧頂添加一個元素。
Pop: 移除棧頂元素，并返回它。
Peek/Top: 返回棧頂元素但不移除它。
IsEmpty: 檢查棧是否為空。
Size: 返回棧中的元素數量。

下面是使用Java實現棧的一個簡單示例：

import java.util.EmptyStackException;public class Stack<T> {private static class StackNode<T> {private T data;private StackNode<T> next;public StackNode(T data) {this.data = data;}}private StackNode<T> top;private int size;public Stack() {top = null;size = 0;}public void push(T item) {StackNode<T> t = new StackNode<T>(item);t.next = top;top = t;size++;}public T pop() {if (isEmpty()) {throw new EmptyStackException();}T item = top.data;top = top.next;size--;return item;}public T peek() {if (isEmpty()) {throw new EmptyStackException();}return top.data;}public boolean isEmpty() {return top == null;}public int size() {return size;}
}

在這個Java實現中，我們使用了泛型（<T>），使得棧可以存儲任何類型的數據。內部的StackNode類用于表示棧中的每個元素，它包含數據和指向下一個元素的鏈接。Stack類本身維護了一個指向棧頂的引用top，以及棧的大小size。

使用這個棧類的方法如下：

public class Main {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();stack.push(1);stack.push(2);stack.push(3);System.out.println("Top element is: " + stack.peek()); // 輸出3while (!stack.isEmpty()) {System.out.println(stack.pop());}}
}

在這個例子中，我們創建了一個整數類型的棧，然后向棧中添加了幾個元素。使用peek方法可以查看棧頂元素而不移除它，最后通過一個循環，使用pop方法來移除并打印所有元素，直到棧為空。

Demo1:實現一個簡易的文本編輯器中的撤銷（Undo）功能

在文本編輯器中，每當用戶執行一個操作，比如插入或刪除文本，這個操作就會被壓入一個棧中。如果用戶想要撤銷最近的操作，編輯器就會從棧中彈出最近的一個操作并執行它的逆操作。

以下是使用Java實現文本編輯器中撤銷功能的示例代碼：

interface EditAction {void execute();  // 執行操作void undo();     // 撤銷操作
}class TextEditor {private String text;private Stack<EditAction> undoStack;public TextEditor() {text = "";undoStack = new Stack<>();}public void type(String input) {// 保存當前文本狀態以便撤銷undoStack.push(new EditAction() {@Overridepublic void execute() {// 這里不需要實現，因為我們不會重新執行這個操作}@Overridepublic void undo() {// 撤銷操作：刪除最近輸入的文本text = text.substring(0, text.length() - input.length());}});text += input;}public void undo() {if (!undoStack.isEmpty()) {EditAction action = undoStack.pop();action.undo();}}public String getText() {return text;}
}public class Main {public static void main(String[] args) {TextEditor editor = new TextEditor();editor.type("Hello");editor.type(" World");System.out.println(editor.getText());  // 輸出 "Hello World"editor.undo();  // 撤銷 " World"System.out.println(editor.getText());  // 輸出 "Hello"editor.undo();  // 撤銷 "Hello"System.out.println(editor.getText());  // 輸出 ""}
}

在這個例子中，我們定義了一個EditAction接口，它包含execute和undo方法。TextEditor類使用一個棧來存儲編輯操作，以便可以撤銷它們。type方法模擬用戶在文本編輯器中輸入文本，并將一個匿名內部類實例作為EditAction壓入棧中，該實例實現了撤銷最近輸入文本的功能。undo方法從棧中彈出最近的EditAction并調用其undo方法來撤銷操作。

這個簡單的撤銷功能展示了棧在實際應用中的一個典型用途，即維護一個操作的歷史記錄，以便可以按相反的順序撤銷它們。

Demo2:實現瀏覽器的前進和后退功能

瀏覽器歷史記錄可以通過兩個棧來實現：一個用于存儲后退歷史（Back Stack），另一個用于存儲前進歷史（Forward Stack）。當用戶訪問一個新頁面時，當前頁面會被推入后退棧，如果用戶點擊后退按鈕，頁面會從后退棧中彈出并推入前進棧；如果用戶點擊前進按鈕，頁面會從前進棧中彈出并推回后退棧。

以下是使用Java實現瀏覽器歷史記錄功能的示例代碼：

public class BrowserHistory {private Stack<String> backStack;private Stack<String> forwardStack;private String currentURL;public BrowserHistory() {backStack = new Stack<>();forwardStack = new Stack<>();currentURL = "Start Page";  // 假設初始頁面是起始頁}public void visit(String url) {backStack.push(currentURL);currentURL = url;forwardStack.clear();  // 清除前進棧，因為歷史已經改變}public String back() {if (backStack.isEmpty()) {return "No pages to go back to.";}forwardStack.push(currentURL);currentURL = backStack.pop();return currentURL;}public String forward() {if (forwardStack.isEmpty()) {return "No pages to go forward to.";}backStack.push(currentURL);currentURL = forwardStack.pop();return currentURL;}public String getCurrentURL() {return currentURL;}
}public class Main {public static void main(String[] args) {BrowserHistory history = new BrowserHistory();System.out.println(history.getCurrentURL());  // 輸出起始頁面history.visit("https://www.google.com");history.visit("https://www.example.com");System.out.println(history.getCurrentURL());  // 輸出 "https://www.example.com"history.back();System.out.println(history.getCurrentURL());  // 輸出 "https://www.google.com"history.forward();System.out.println(history.getCurrentURL());  // 輸出 "https://www.example.com"history.visit("https://www.anotherpage.com");System.out.println(history.getCurrentURL());  // 輸出 "https://www.anotherpage.com"history.back();System.out.println(history.getCurrentURL());  // 輸出 "https://www.google.com"}
}

在這個例子中，BrowserHistory類有兩個棧：backStack用于存儲后退歷史，forwardStack用于存儲前進歷史。visit方法模擬用戶訪問新頁面，將當前頁面URL壓入后退棧，并將新頁面URL設置為當前URL，同時清空前進棧。back方法模擬用戶點擊后退按鈕，將當前頁面URL壓入前進棧，并從后退棧中彈出之前的頁面URL作為當前頁面。forward方法模擬用戶點擊前進按鈕，將當前頁面URL壓入后退棧，并從前進棧中彈出下一個頁面URL作為當前頁面。

這個例子展示了棧在模擬瀏覽器歷史記錄中的實用性，允許用戶在訪問過的頁面之間前進和后退。

Demo3:表達式求值

使用棧可以方便地處理括號匹配和運算符優先級的問題。以下是一個使用棧進行基本算術表達式求值的Java實現：

import java.util.Stack;public class ExpressionEvaluator {public int evaluate(String expression) {Stack<Integer> numbers = new Stack<>();Stack<Character> operators = new Stack<>();String num = "";for (int i = 0; i < expression.length(); i++) {char c = expression.charAt(i);if (Character.isDigit(c)) {num += c;} else {if (!num.isEmpty()) {numbers.push(Integer.parseInt(num));num = "";}if (c == '(') {operators.push(c);} else if (c == ')') {while (!operators.isEmpty() && operators.peek() != '(') {numbers.push(applyOperation(numbers.pop(), numbers.pop(), operators.pop()));}operators.pop(); // Pop the '('} else if (isOperator(c)) {while (!operators.isEmpty() && hasHigherPrecedence(operators.peek(), c)) {numbers.push(applyOperation(numbers.pop(), numbers.pop(), operators.pop()));}operators.push(c);}}}if (!num.isEmpty()) {numbers.push(Integer.parseInt(num));}while (!operators.isEmpty()) {numbers.push(applyOperation(numbers.pop(), numbers.pop(), operators.pop()));}return numbers.pop();}private boolean isOperator(char c) {return c == '+' || c == '-' || c == '*' || c == '/';}private boolean hasHigherPrecedence(char op1, char op2) {return (op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-');}private int applyOperation(int b, int a, char op) {switch (op) {case '+': return a + b;case '-': return a - b;case '*': return a * b;case '/': return a / b;}return 0;}public static void main(String[] args) {ExpressionEvaluator evaluator = new ExpressionEvaluator();String expression = "3+5*(2-1)";System.out.println("Result: " + evaluator.evaluate(expression)); // 輸出結果}
}