栈与栈的经典应用场景

算法数据结构栈

算法

发布日期: 2024-09-03

作者: 小乐

文章字数: 982

阅读时长: 4 分

阅读次数:

一、栈的定义

栈(Stack)是一种后进先出(LIFO, Last In First Out)的线性数据结构。

1.1 核心操作

操作	说明	时间复杂度
push	入栈	( O(1) )
pop	出栈	( O(1) )
peek/top	查看栈顶	( O(1) )
isEmpty	判空	( O(1) )

1.2 形象比喻

就像一摞盘子，只能从最上面放盘子(push)，也只能从最上面取盘子(pop)。

二、栈的实现

2.1 数组实现

class ArrayStack {
    private int[] data;
    private int top = -1;
    
    public void push(int val) {
        if (top == data.length - 1) {
            // 扩容
        }
        data[++top] = val;
    }
    
    public int pop() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return data[top--];
    }
    
    public int peek() {
        return data[top];
    }
    
    public boolean isEmpty() {
        return top == -1;
    }
}

2.2 链表实现

class LinkedStack {
    private ListNode top;
    
    public void push(int val) {
        ListNode node = new ListNode(val);
        node.next = top;
        top = node;
    }
    
    public int pop() {
        if (top == null) throw new RuntimeException("Stack is empty");
        int val = top.val;
        top = top.next;
        return val;
    }
}

2.3 Java标准库

Stack<Integer> stack = new Stack<>();  // 不推荐，线程同步有开销
Deque<Integer> stack = new ArrayDeque<>();  // 推荐

三、经典应用场景

3.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 ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

3.2 表达式求值

问题：计算中缀表达式 3 + 5 * 2 - 8 / 4

思路：使用操作符栈和数字栈。

// 中缀转后缀（逆波兰表达式），再求值
// 后缀表达式: 3 5 2 * + 8 4 / -
public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String token : tokens) {
        switch (token) {
            case "+": stack.push(stack.pop() + stack.pop()); break;
            case "-": stack.push(-stack.pop() + stack.pop()); break;
            case "*": stack.push(stack.pop() * stack.pop()); break;
            case "/":
                int b = stack.pop(), a = stack.pop();
                stack.push(a / b);
                break;
            default: stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

3.3 单调栈 - 下一个更大元素

问题：数组中每个元素右边第一个比它大的元素。

public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>();  // 存索引
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            res[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return res;
}

3.4 浏览器前进后退

class BrowserHistory {
    Deque<String> back = new ArrayDeque<>();
    Deque<String> forward = new ArrayDeque<>();
    String current;
    
    public void visit(String url) {
        back.push(current);
        current = url;
        forward.clear();
    }
    
    public String back() {
        if (!back.isEmpty()) {
            forward.push(current);
            current = back.pop();
        }
        return current;
    }
}

3.5 函数调用栈

程序运行时的函数调用就是通过栈实现的：

main()
  └── funcA()
        └── funcB()
              └── funcC()  ← 当前执行

每次函数调用，将返回地址、参数、局部变量压入栈。函数返回时出栈恢复现场。

四、单调栈专题

4.1 单调递减栈

栈内元素从底到顶递减，用于找下一个更大元素。

4.2 单调递增栈

栈内元素从底到顶递增，用于找下一个更小元素。

4.3 接雨水问题

public int trap(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();
    int water = 0;
    
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
            int bottom = height[stack.pop()];
            if (stack.isEmpty()) break;
            int left = stack.peek();
            int w = i - left - 1;
            int h = Math.min(height[left], height[i]) - bottom;
            water += w * h;
        }
        stack.push(i);
    }
    return water;
}