数据结构第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)); // 输出结果}
}