04-栈-LeetCode解题

本讲为数据结构和算法系列第四讲，聚焦栈结构原理与 LeetCode 经典题解。

核心内容

• 栈的基本概念：LIFO 后进先出
• 顺序栈与链式栈实现
• 栈的应用场景：表达式求值、括号匹配、递归模拟
• LeetCode 栈相关题目精讲

// 基于数组的栈实现
public class ArrayStack<T> {
    private Object[] data;
    private int top;

    public ArrayStack(int capacity) {
        this.data = new Object[capacity];
        this.top = -1;
    }

    public void push(T value) {
        if (top == data.length - 1) resize();
        data[++top] = value;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (top == -1) throw new EmptyStackException();
        return (T) data[top--];
    }

    @SuppressWarnings("unchecked")
    public T peek() { return (T) data[top]; }
    public boolean isEmpty() { return top == -1; }
}

LeetCode 题解：有效的括号

题目：给定只包含 () [] {} 的字符串，判断字符串是否有效。

public boolean isValid(String s) {
    ArrayStack<Character> stack = new ArrayStack<>(s.length());
    for (char c : s.toCharArray()) {
        if (c == '(') stack.push(')');
        else if (c == '[') stack.push(']');
        else if (c == '{') stack.push('}');
        else if (stack.isEmpty() || stack.pop() != c) return false;
    }
    return stack.isEmpty();
}

复杂度分析

操作	时间复杂度
push	O(1)
pop	O(1)
peek	O(1)