栈（Stack）

栈（Stack）是一种常用的数据结构，具备后进先出 （LIFO, Last In First Out）的特点。栈的数据操作只在一端进行，通常称为“栈顶”（Top）。在栈中，最新添加的元素最先被移除，这种特性使得栈在特定场景中具有高效的表现。

一、栈的定义

栈是一种限制性的数据结构，它只允许在一端进行数据的插入（入栈）和删除（出栈）操作。常见的例子包括书堆、浏览器历史记录、函数调用等。

特性

• 后进先出：栈中的最后一个元素将会是第一个被移除的元素。
• 单向访问：栈只允许从栈顶操作数据，无法直接访问中间的元素。

栈的术语

• 栈顶（Top）：栈中最靠近插入端的元素。
• 栈底（Bottom）：栈中最先被插入的元素，在栈底保持不动，直到栈中的所有元素被移除。
• 入栈（Push）：向栈顶添加元素。
• 出栈（Pop）：从栈顶移除元素。

二、栈的基本操作

栈的基本操作包括 Push、Pop、Peek 和 IsEmpty。

1. Push：将一个元素压入栈顶。
2. Pop：移除并返回栈顶的元素。如果栈为空，则通常返回错误或异常。
3. Peek：查看栈顶元素但不移除它。
4. IsEmpty：检查栈是否为空。

三、栈的应用场景

1. 表达式求值：在计算机中，中缀表达式（如 1 + 2 * 3）通常会转换为后缀表达式（如 1 2 3 * +），这时栈被用于存储和操作运算符和操作数。
2. 括号匹配：在解析或验证表达式中的括号是否匹配时，可以利用栈来追踪括号的开闭关系。
3. 浏览器的前进和后退：浏览器会将访问的页面依次压入栈中，用户可以通过出栈操作返回上一页。
4. 函数调用：在编译原理和操作系统中，函数调用的返回地址和局部变量会存储在栈上，以便函数调用的顺序能够正确返回。
5. 深度优先搜索（DFS）：DFS 通常借助栈实现，以便追踪节点的访问路径。

四、栈的优缺点

优点

1. 操作简单：栈的操作集中在栈顶，操作时间复杂度为 。
2. 应用灵活：栈的 LIFO 特性在许多场景中非常有效，如括号匹配、表达式求值等。

缺点

1. 随机访问不便：栈只能访问栈顶元素，无法直接访问栈中的任意位置。
2. 空间利用受限：栈的大小固定时可能会导致栈溢出（Stack Overflow），尤其在递归调用深度很深时。

五、栈的实现

栈可以通过数组或链表实现，每种方式有不同的特性和适用场景。

1. 基于数组实现

数组实现的栈称为顺序栈。可以在固定长度的数组中实现栈的基本操作，但需要注意栈的容量限制。

class Stack {
    constructor(size) {
        this.stack = new Array(size);
        this.top = -1; // 栈顶指针
        this.size = size;
    }

    // 入栈操作
    push(value) {
        if (this.top === this.size - 1) {
            throw new Error("Stack Overflow"); // 栈溢出
        }
        this.stack[++this.top] = value;
    }

    // 出栈操作
    pop() {
        if (this.top === -1) {
            throw new Error("Stack Underflow"); // 栈为空
        }
        return this.stack[this.top--];
    }

    // 查看栈顶元素
    peek() {
        if (this.top === -1) {
            throw new Error("Stack is empty");
        }
        return this.stack[this.top];
    }

    // 检查栈是否为空
    isEmpty() {
        return this.top === -1;
    }
}

// 示例
const stack = new Stack(5);
stack.push(1);
stack.push(2);
console.log(stack.pop());  // 输出: 2
console.log(stack.peek()); // 输出: 1

2. 基于链表实现

链表实现的栈称为链式栈，能动态地分配和释放内存，不受容量限制。

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class Stack {
    constructor() {
        this.top = null; // 栈顶指针
    }

    // 入栈操作
    push(value) {
        const newNode = new Node(value);
        newNode.next = this.top;
        this.top = newNode;
    }

    // 出栈操作
    pop() {
        if (this.isEmpty()) {
            throw new Error("Stack Underflow");
        }
        const value = this.top.value;
        this.top = this.top.next;
        return value;
    }

    // 查看栈顶元素
    peek() {
        if (this.isEmpty()) {
            throw new Error("Stack is empty");
        }
        return this.top.value;
    }

    // 检查栈是否为空
    isEmpty() {
        return this.top === null;
    }
}

// 示例
const stack = new Stack();
stack.push(1);
stack.push(2);
console.log(stack.pop());  // 输出: 2
console.log(stack.peek()); // 输出: 1

3. 使用 JavaScript 的原生栈模拟

在 JavaScript 中，Array 提供了 push 和 pop 方法，可以直接用来实现栈：

const stack = [];
stack.push(1);  // 入栈
stack.push(2);
console.log(stack.pop());  // 输出: 2
console.log(stack[stack.length - 1]); // 输出: 1 (查看栈顶元素)

六、栈在算法中的应用实例

1. 括号匹配

利用栈可以有效地判断字符串中的括号是否匹配。

function isValidParentheses(s) {
    const stack = [];
    const map = {
        ')': '(',
        '}': '{',
        ']': '['
    };

    for (const char of s) {
        if (char === '(' || char === '{' || char === '[') {
            stack.push(char);
        } else if (stack.length && stack[stack.length - 1] === map[char]) {
            stack.pop();
        } else {
            return false;
        }
    }

    return stack.length === 0;
}

// 示例
console.log(isValidParentheses("({[]})")); // 输出: true
console.log(isValidParentheses("({[})"));  // 输出: false

2. 表达式求值（逆波兰表达式）

栈在逆波兰表达式（RPN）的求值中非常常见。

function evalRPN(tokens) {
    const stack = [];

    for (const token of tokens) {
        if (!isNaN(token)) {
            stack.push(Number(token));
        } else {
            const b = stack.pop();
            const a = stack.pop();
            switch (token) {
                case '+': stack.push(a + b); break;
                case '-': stack.push(a - b); break;
                case '*': stack.push(a * b); break;
                case '/': stack.push(Math.trunc(a / b)); break;
            }
        }
    }

    return stack.pop();
}

// 示例
console.log(evalRPN(["2", "1", "+", "3", "*"])); // 输出: 9
console.log(evalRPN(["4", "13", "5", "/", "+"])); // 输出: 6

七、总结

栈是一种简单但非常有效的数据结构，其“后进先出”的特性使其在许多算法和数据处理流程中发挥着关键作用。了解栈的特性和常用实现方式，可以帮助我们在多种场景下有效地使用它。