JavaScript数据结构与算法之栈实例分析

栈（Stack）是一种常见的数据结构，它遵循“后进先出”（LIFO, Last In First Out）的原则。栈的操作主要包括入栈（push）、出栈（pop）、查看栈顶元素（peek）以及判断栈是否为空（isEmpty）。栈在计算机科学中有着广泛的应用，例如函数调用栈、表达式求值、括号匹配等。

本文将详细介绍栈的基本概念、操作及其在JavaScript中的实现，并通过实例分析栈的应用场景。

1. 栈的基本概念

栈是一种线性数据结构，它只允许在一端进行插入和删除操作。这一端被称为栈顶（top），另一端被称为栈底（bottom）。栈的操作主要包括以下几种：

• 入栈（push）：将元素添加到栈顶。
• 出栈（pop）：移除并返回栈顶元素。
• 查看栈顶元素（peek）：返回栈顶元素但不移除它。
• 判断栈是否为空（isEmpty）：判断栈中是否没有元素。

2. 栈的实现

在JavaScript中，栈可以通过数组或链表来实现。下面我们使用数组来实现一个简单的栈类。

class Stack {
    constructor() {
        this.items = [];
    }

    // 入栈
    push(element) {
        this.items.push(element);
    }

    // 出栈
    pop() {
        if (this.isEmpty()) {
            return "栈为空";
        }
        return this.items.pop();
    }

    // 查看栈顶元素
    peek() {
        if (this.isEmpty()) {
            return "栈为空";
        }
        return this.items[this.items.length - 1];
    }

    // 判断栈是否为空
    isEmpty() {
        return this.items.length === 0;
    }

    // 返回栈的大小
    size() {
        return this.items.length;
    }

    // 清空栈
    clear() {
        this.items = [];
    }

    // 打印栈内容
    print() {
        console.log(this.items.toString());
    }
}

2.1 使用示例

const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);

stack.print(); // 输出: 10,20,30

console.log(stack.peek()); // 输出: 30

stack.pop();
stack.print(); // 输出: 10,20

console.log(stack.isEmpty()); // 输出: false

stack.clear();
console.log(stack.isEmpty()); // 输出: true

3. 栈的应用实例

3.1 括号匹配

括号匹配是栈的一个经典应用场景。给定一个字符串，判断其中的括号是否匹配。例如，{[()]} 是匹配的，而 {[(])} 是不匹配的。

function isBalanced(expression) {
    const stack = new Stack();
    const brackets = { '{': '}', '[': ']', '(': ')' };

    for (let char of expression) {
        if (brackets[char]) {
            stack.push(char);
        } else if (char === '}' || char === ']' || char === ')') {
            if (stack.isEmpty() || brackets[stack.pop()] !== char) {
                return false;
            }
        }
    }

    return stack.isEmpty();
}

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

3.2 表达式求值

栈还可以用于表达式求值，特别是后缀表达式（逆波兰表达式）的求值。后缀表达式是一种不需要括号的表达式表示方法，运算符位于操作数之后。

function evaluatePostfix(expression) {
    const stack = new Stack();
    const operators = ['+', '-', '*', '/'];

    for (let char of expression) {
        if (!isNaN(char)) {
            stack.push(Number(char));
        } else if (operators.includes(char)) {
            const operand2 = stack.pop();
            const operand1 = stack.pop();
            const result = calculate(operand1, operand2, char);
            stack.push(result);
        }
    }

    return stack.pop();
}

function calculate(operand1, operand2, operator) {
    switch (operator) {
        case '+': return operand1 + operand2;
        case '-': return operand1 - operand2;
        case '*': return operand1 * operand2;
        case '/': return operand1 / operand2;
        default: throw new Error("未知的运算符");
    }
}

console.log(evaluatePostfix("23*5+")); // 输出: 11

3.3 函数调用栈

在JavaScript中，函数调用栈用于管理函数的调用顺序。每当一个函数被调用时，它会被压入调用栈中，当函数执行完毕后，它会被弹出调用栈。

function first() {
    console.log("First function");
    second();
}

function second() {
    console.log("Second function");
    third();
}

function third() {
    console.log("Third function");
}

first();

在上述代码中，函数调用的顺序是 first -> second -> third，调用栈的顺序也是 first -> second -> third。当 third 函数执行完毕后，它会从调用栈中弹出，然后是 second，最后是 first。

4. 总结

栈是一种简单但功能强大的数据结构，它在计算机科学中有着广泛的应用。本文介绍了栈的基本概念、操作及其在JavaScript中的实现，并通过实例分析了栈的应用场景。掌握栈的使用对于理解算法和解决实际问题具有重要意义。