3- 栈（Stack）

一、Stack ADT

1.1 什么是Stack

Stack（栈）是一种抽象数据类型（ADT），遵循后进先出（LIFO, Last In First Out）原则。栈有两个主要操作：

push: 将元素添加到栈顶。
pop: 从栈顶移除并返回元素。

此外，还有两个辅助操作：

peek: 返回栈顶元素但不移除。
isEmpty: 检查栈是否为空。

栈在计算机科学中有广泛的应用，包括：

函数调用的递归实现（调用栈）。
表达式求值与语法解析（例如计算器、编译器）。
深度优先搜索算法（DFS）。
撤销操作（如文字处理器中的撤销功能）。

二、Java中的Stack接口

Java提供了两种方式来使用栈：一种是使用Java标准库中的java.util.Stack类，另一种是通过自定义接口和类来实现。

2.1 `java.util.Stack`

Java中的java.util.Stack类继承自Vector类，由于Vector的大部分操作都是同步的，这使得Stack在多线程环境中性能较低。实际上，对于大多数现代Java应用程序，更推荐使用Deque接口的实现，如ArrayDeque，它提供了更快的非同步操作。

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("Stack: " + stack);
        System.out.println("Top element: " + stack.peek());

        System.out.println("Popped element: " + stack.pop());
        System.out.println("Stack after pop: " + stack);
    }
}

2.2 自定义Stack接口

定义一个简单的Stack接口，包含push、pop、peek和isEmpty方法：

public interface Stack<E> {
    void push(E element);
    E pop();
    E peek();
    boolean isEmpty();
}

三、基于数组的实现

3.1 基本思路

使用数组来实现栈的优点是访问元素速度快（O(1)），缺点是数组大小固定，需要手动扩容。

3.2 实现代码

public class ArrayStack<E> implements Stack<E> {
    private E[] elements;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;

    public ArrayStack() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
        size = 0;

        // 在Java中，Java的泛型在编译时会进行类型擦除，导致运行时不保留关于泛型实际类型参数的信息，所以我们不能直接创建泛型数组。
        // 这里使用(E[]) new Object[DEFAULT_CAPACITY]进行类型转换是一种常见的做法。虽然这不是类型安全的，
        // 但它在实际应用中是可接受的。要完全避免这种做法，可以考虑使用ArrayList或其他集合类。
        // 用ArrayList来代替数组，也能避免手动扩容的问题。
    }

    @Override
    public void push(E element) {
        if (size == elements.length) {
            resize(2 * elements.length);
        }
        elements[size++] = element;
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException("Cannot pop from an empty stack.");
            // 在实现pop方法时抛出EmptyStackException，这是一种防御式编程技巧，
            // 可以避免在空栈上进行操作导致程序崩溃。在错误消息中提供更多的上下文可以帮助调试。
            // 记得先 import java.util.EmptyStackException;
        }
        E result = elements[--size];
        elements[size] = null;  // Clear to let GC do its work
        return result;
    }

    @Override
    public E peek() { // 返回栈顶元素
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return elements[size - 1];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private void resize(int capacity) {
        E[] newArray = (E[]) new Object[capacity];
        System.arraycopy(elements, 0, newArray, 0, size);
        elements = newArray;
    }

    public int getSize() {
        return size;
    }
}

四、基于链表的实现

4.1 基本思路

使用链表来实现栈的优点是没有容量限制，可以动态扩展，缺点是每次访问元素需要遍历链表（O(n)）。

4.2 实现代码

public class LinkedListStack<E> implements Stack<E> {
    private Node<E> top;
    private int size;

    private static class Node<E> {
        E element;
        Node<E> next;

        Node(E element, Node<E> next) {
            this.element = element;
            this.next = next;
        }
    }

    public LinkedListStack() {
        top = null;
        size = 0;
    }

    @Override
    public void push(E element) {
        Node<E> newNode = new Node<>(element, top);
        top = newNode;
        size++;
    }

    @Override
    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        E result = top.element;
        top = top.next;
        size--;
        return result;
    }

    @Override
    public E peek() { // 返回栈顶元素
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.element;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    public int getSize() {
        return size;
    }
}

应用场景

1. Web浏览器历史记录

Web浏览器使用栈来管理用户的浏览历史。每当用户访问一个新页面，浏览器就会将该页面的地址“推”入栈中。当用户点击后退按钮时，浏览器会“弹出”栈顶的页面地址，从而实现页面的后退功能。

2. 文本编辑器中的撤销操作

在文本编辑器中，每一次编辑操作（如插入、删除文字）都可以被推入一个栈中。当用户执行撤销操作时，最近的编辑操作可以通过弹出栈顶元素来撤销，这样可以连续撤销多个操作。

3. 方法调用链（如JVM中的调用栈）

在Java虚拟机（JVM）中，每个方法的调用都会形成一个栈帧，这些栈帧存储在调用栈中。当一个方法调用另一个方法时，新的栈帧就会被推入栈顶。方法返回时，其栈帧被弹出，控制权回到调用该方法的栈帧中。

4. 算法和其他数据结构组件

栈在各种算法中扮演重要角色，如在图的深度优先搜索（DFS）中管理待访问的节点。此外，栈也是某些复杂数据结构的组成部分，如在表达式求值和语法解析中使用。

括号匹配算法

实现原理

括号匹配算法是一个常见的使用栈来解决的问题，主要用于检查代码或数学表达式中的括号是否正确匹配。算法步骤如下：

遍历表达式的每个字符。

2.如果是开括号（如(, {, [），则将其推入栈中。

如果是闭括号（如), }, ]），则检查栈顶元素：
- 如果栈顶元素与当前闭括号匹配，将栈顶元素弹出。
- 如果不匹配或栈为空，则表达式括号不匹配。
遍历完成后，如果栈为空，则所有括号正确匹配；如果栈不为空，表示有未匹配的开括号。

示例代码

import java.util.Stack;

public class ParenthesesMatching {
    public static boolean isValid(String expression) {
        Stack<Character> stack = new Stack<>();
        for (char ch : expression.toCharArray()) {
            switch (ch) {
                case '(': case '{': case '[':
                    stack.push(ch);
                    break;
                case ')': case '}': case ']':
                    if (stack.isEmpty() || !isMatchingPair(stack.pop(), ch)) {
                        return false;
                    }
                    break;
            }
        }
        return stack.isEmpty();
    }

    private static boolean isMatchingPair(char opening, char closing) {
        return (opening == '(' && closing == ')') ||
               (opening == '{' && closing == '}') ||
               (opening == '[' && closing == ']');
    }

    public static void main(String[] args) {
        String expression = "{[()]}";
        System.out.println("Expression is valid: " + isValid(expression));
    }
}

HTML标签匹配

HTML标签匹配算法与括号匹配类似，不过HTML中有成对的标签和不成对的标签，它处理的是HTML文档中的开闭标签。这个算法确保每个开始标签（如<div>）都有对应的结束标签（如</div>），并且嵌套顺序正确。

实现思路

遍历HTML文档。
遇到开始标签时，将标签名推入栈中。
遇到结束标签时，检查栈顶标签：
- 如果栈顶标签与结束标签匹配，弹出栈顶。
- 如果不匹配，HTML文档结构有误。
遍历结束后，栈应为空。如果不为空，则表示有标签未正确关闭。

这种方法可以有效检测HTML文档的结构正确性，对于开发Web应用或者HTML编辑器的开发者来说非常有用。通过以上示例，我们可以看到栈不仅是一种基本的数据结构，也是解决实际问题的强大工具。希望这些知识能帮助你在实际开发中更好地应用栈的概念。