栈

栈是一种后进先出（LIFO, Last In First Out）的数据结构，只允许在特定一端（栈顶）进行插入和删除操作。

栈的特性

• 后进先出：最后插入的元素最先被删除
• 只允许在栈顶操作：插入（push）和删除（pop）都在栈顶进行
• 时间复杂度：push、pop、peek 都是 O(1)

栈的实现

数组实现

public class ArrayStack<E> {
    private E[] data;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    
    @SuppressWarnings("unchecked")
    public ArrayStack() {
        this.data = (E[]) new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }
    
    // 入栈 - O(1) 均摊
    public void push(E element) {
        if (size == data.length) {
            resize(data.length * 2);
        }
        data[size++] = element;
    }
    
    // 出栈 - O(1) 均摊
    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        
        E element = data[--size];
        data[size] = null;  // 帮助 GC
        
        if (size > 0 && size == data.length / 4) {
            resize(data.length / 2);
        }
        
        return element;
    }
    
    // 查看栈顶 - O(1)
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return data[size - 1];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
}

链表实现

public class LinkedStack<E> {
    private static class Node<E> {
        E val;
        Node<E> next;
        Node(E val) { this.val = val; }
    }
    
    private Node<E> top;
    private int size;
    
    // 入栈 - O(1)
    public void push(E element) {
        Node<E> newNode = new Node<>(element);
        newNode.next = top;
        top = newNode;
        size++;
    }
    
    // 出栈 - O(1)
    public E pop() {
        if (isEmpty()) throw new IllegalStateException("Stack is empty");
        E element = top.val;
        top = top.next;
        size--;
        return element;
    }
    
    public boolean isEmpty() { return size == 0; }
}

栈的应用

1. 括号匹配

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

2. 逆波兰表达式求值

使用栈存储操作数，遇到操作符时弹出两个操作数进行计算。

3. 最小栈

通过辅助栈同步存储当前栈的最小值。

4. 单调栈

单调栈用于解决“找左/右边第一个比当前元素大/小”的问题。

// 每日温度 (LeetCode 739)
public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prev = stack.pop();
            result[prev] = i - prev;
        }
        stack.push(i);
    }
    return result;
}

练习

1. LeetCode 20：有效的括号
2. LeetCode 155：最小栈
3. LeetCode 739：每日温度
4. LeetCode 42：接雨水 (单调栈解法)
5. LeetCode 84：柱状图中最大的矩形 (单调栈解法)