📚 栈 Stack 可视化

栈是后进先出（LIFO）的数据结构，像一摞盘子，只能从顶部操作

⬅ 栈顶 (top)
欢迎！体验栈的 push 和 pop 操作

栈的经典应用：括号匹配

( { [ ] } )
点击"检查匹配"验证括号是否配对

原理：遇到左括号入栈，遇到右括号检查栈顶是否匹配。
匹配则弹出栈顶，不匹配则括号序列非法。最后栈为空则全部匹配。

JavaScript 实现（数组模拟栈）

// 栈类实现
class Stack {
    constructor() {
        this.items = [];
    }

    // 入栈 - O(1)
    push(item) {
        this.items.push(item);
    }

    // 出栈 - O(1)
    pop() {
        if (this.isEmpty()) {
            throw new Error('Stack underflow');
        }
        return this.items.pop();
    }

    // 查看栈顶 - O(1)
    peek() {
        return this.items[this.items.length - 1];
    }

    // 判空 - O(1)
    isEmpty() {
        return this.items.length === 0;
    }

    // 栈大小 - O(1)
    size() {
        return this.items.length;
    }
}

// 括号匹配应用
function isBalanced(str) {
    const stack = new Stack();
    const pairs = { ')': '(', ']': '[', '}': '{' };

    for (const ch of str) {
        if (ch === '(' || ch === '[' || ch === '{') {
            stack.push(ch);  // 左括号入栈
        } else if (ch === ')' || ch === ']' || ch === '}') {
            if (stack.isEmpty() || stack.pop() !== pairs[ch]) {
                return false;  // 不匹配
            }
        }
    }
    return stack.isEmpty();  // 栈空则全部匹配
}

时间复杂度分析

操作时间复杂度说明
Push 入栈O(1)在栈顶添加元素
Pop 出栈O(1)移除栈顶元素
Peek 查看O(1)不修改栈
isEmpty 判空O(1)检查长度
搜索O(n)需要遍历（一般不推荐）

实际应用场景

  • 🧮 函数调用栈：程序运行时函数调用和返回
  • ↩️ 撤销操作：编辑器 Undo 功能
  • 🔙 浏览器历史：前进后退导航
  • 🧮 表达式求值：中缀转后缀、计算器
  • 📝 括号匹配：编译器语法检查
  • 🌲 深度优先搜索：DFS 非递归实现