栈（Stack）详解：从原理到实现，再到括号匹配应用

栈是一种基础而重要的线性数据结构，在计算机科学中被广泛应用于函数调用、表达式求值、回溯算法等场景。本文将围绕栈的定义、抽象数据类型（ADT）、ES6 实现方式（数组与链表）、性能对比，以及一个经典应用场景——括号匹配问题，进行系统讲解。

---

一、什么是栈？

栈（Stack）是一种遵循 先进后出（First In Last Out, FILO） 原则的线性数据结构。你可以把它想象成一摞盘子：你只能从顶部放入（入栈）或取出（出栈）盘子，不能从中间或底部操作。

栈的核心操作包括：

• push(x) ：将元素 x 压入栈顶。
• pop() ：弹出并返回栈顶元素。
• peek() / top() ：查看栈顶元素但不移除。
• isEmpty() ：判断栈是否为空。
• size() ：获取栈中元素个数。

---

二、栈的抽象数据类型（ADT）

抽象数据类型（Abstract Data Type, ADT）是对数据结构行为的规范描述，不涉及具体实现。栈的 ADT 应包含以下属性和方法：

属性/方法	描述
size	只读属性，返回当前栈的大小
isEmpty()	判断栈是否为空
push(val)	入栈操作
pop()	出栈操作，若栈空则抛出异常
peek()	返回栈顶元素，若栈空则抛出异常
toArray()	（可选）将栈内容转换为数组，便于调试或输出

---

三、ES6 Class 实现栈

ES6 引入了 class 语法，使面向对象编程更加清晰。结合私有字段（#）、get 访问器等特性，可以优雅地封装栈的实现细节。

1. 基于链表实现栈（LinkedListStack）

链表天然适合动态增长，每个节点包含值和指向下一个节点的指针。

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

class LinkedListStack {
    #stackPeek = null; // 私有栈顶指针
    #size = 0;

    push(num) {
        const node = new ListNode(num);
        node.next = this.#stackPeek;
        this.#stackPeek = node;
        this.#size++;
    }

    pop() {
        if (!this.#stackPeek) throw new Error('栈为空');
        const val = this.#stackPeek.val;
        this.#stackPeek = this.#stackPeek.next;
        this.#size--;
        return val;
    }

    peek() {
        if (!this.#stackPeek) throw new Error('栈为空');
        return this.#stackPeek.val;
    }

    get size() { return this.#size; }
    isEmpty() { return this.#size === 0; }

    toArray() {
        let node = this.#stackPeek;
        const res = new Array(this.#size);
        for (let i = res.length - 1; i >= 0; i--) {
            res[i] = node.val;
            node = node.next;
        }
        return res;
    }
}

✅ 优点：动态扩容，无空间浪费；插入/删除均为 O(1)
❌ 缺点：每个节点需额外存储指针，内存开销略大

---

2. 基于数组实现栈（ArrayStack）

利用 JavaScript 数组的 push 和 pop 方法，可快速实现栈。

class ArrayStack {
    #stack = [];

    get size() { return this.#stack.length; }
    isEmpty() { return this.size === 0; }

    push(num) {
        this.#stack.push(num);
    }

    pop() {
        if (this.isEmpty()) throw new Error("栈为空");
        return this.#stack.pop();
    }

    peek() {
        if (this.isEmpty()) throw new Error("栈为空");
        return this.#stack[this.size - 1];
    }

    toArray() {
        return [...this.#stack]; // 返回副本更安全
    }
}

✅ 优点：缓存友好，访问快；代码简洁
❌ 缺点：扩容时需复制整个数组（O(n)），但均摊时间复杂度仍为 O(1)

---

四、数组 vs 链表实现栈：性能对比

维度	数组实现	链表实现
时间效率	平均 O(1)，扩容时 O(n)	稳定 O(1)
空间效率	可能有预分配空间浪费	每个节点多一个指针开销
内存布局	连续内存，缓存命中率高	离散内存，缓存局部性差
适用场景	数据量可预估、追求速度	动态性强、内存敏感

💡 在大多数实际应用中，数组实现的栈更常用，因为其简单高效，且现代 JavaScript 引擎对数组优化极佳。

---

五、实战应用：括号匹配问题

栈的经典应用场景之一是验证括号字符串是否合法。例如："([{}])" 合法，而 "([)]" 不合法。

解题思路：

1. 遇到左括号 (、[、{，将其对应的右括号压入栈；
2. 遇到右括号，检查是否与栈顶元素匹配；
3. 若不匹配或栈为空，则非法；
4. 遍历结束后，栈必须为空才合法。

代码实现：

const leftToRight = {
    "(": ")",
    "[": "]",
    "{": "}"
};

function isValid(s) {
    if (!s) return true;
    const stack = [];
    for (const ch of s) {
        if (ch in leftToRight) {
            stack.push(leftToRight[ch]); // 压入期望的右括号
        } else {
            if (!stack.length || stack.pop() !== ch) {
                return false; // 不匹配或栈空
            }
        }
    }
    return stack.length === 0; // 必须完全匹配
}

✅ 时间复杂度：O(n)
✅ 空间复杂度：O(n)（最坏情况全为左括号）

---

六、总结

• 栈是一种 FILO 的线性结构，核心操作为 push、pop、peek。
• ES6 的 class、私有字段 # 和 get 访问器，让栈的实现更安全、更清晰。
• 数组实现简单高效，适合大多数场景；链表实现动态灵活，适合不确定规模的场景。
• 栈在算法中用途广泛，如括号匹配、表达式求值、深度优先搜索（DFS）等。

掌握栈，不仅是理解数据结构的第一步，更是打开算法世界大门的钥匙。

---

📌 提示：在实际开发中，除非有特殊需求（如限制使用内置数组方法），否则直接使用 Array 的 push/pop 即可高效模拟栈行为。