数据结构第06节：栈

栈（Stack）是一种后进先出（Last In First Out, LIFO）的数据结构，它只允许在一端，称为栈顶（Top），进行添加（Push）和移除（Pop）数据项的操作。栈常用于解决递归、回溯、函数调用等问题。

栈的基本操作包括：

1. Push: 向栈顶添加一个元素。
2. Pop: 移除栈顶元素，并返回它。
3. Peek/Top: 返回栈顶元素但不移除它。
4. IsEmpty: 检查栈是否为空。
5. 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

在这个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()); // 输出3

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在这个例子中，我们创建了一个整数类型的栈，然后向栈中添加了几个元素。使用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() {
            @Override
            public void execute() {
                // 这里不需要实现，因为我们不会重新执行这个操作
            }

            @Override
            public 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());  // 输出 ""
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

在这个例子中，我们定义了一个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"
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

在这个例子中，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)); // 输出结果
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

在这个例子中，ExpressionEvaluator类使用两个栈：numbers用于存储操作数，operators用于存储运算符。evaluate方法遍历表达式字符串，当遇到数字时将其累加到num字符串中，当遇到运算符或括号时，执行相应的操作。

• 如果遇到左括号(，将其压入operators栈。
• 如果遇到右括号)，从栈中弹出运算符并执行相应的运算，直到遇到左括号。
• 如果遇到运算符，检查栈顶运算符的优先级，如果当前运算符优先级更高或相同，则先执行栈中的运算。
• 最后，如果栈中还有运算符，继续执行运算直到所有运算符都被处理完毕。

isOperator方法用于检查字符是否是运算符，hasHigherPrecedence方法用于比较两个运算符的优先级，applyOperation方法用于执行具体的运算。

这个例子展示了栈在处理带有括号的表达式求值中的实用性，能够有效地处理运算符优先级和括号匹配的问题。