当前位置:   article > 正文

数据结构第06节:栈

数据结构第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接口,它包含executeundo方法。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方法用于执行具体的运算。

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/786600
推荐阅读
相关标签
  

闽ICP备14008679号