JavaScript 栈

栈是一种遵循后进先出（LIFO, Last In First Out）原则的线性数据结构。想象一下你有一叠盘子，每次你往这叠盘子上放一个新的盘子时，你只能从顶部取走盘子。这就是栈的工作原理。

栈的基本操作

入栈 (Push)

入栈操作是指向栈中添加一个元素。这个元素会被添加到栈顶。

function push(stack, element) {
    stack[stack.length] = element;
}

出栈 (Pop)

出栈操作是从栈中移除一个元素。由于栈遵循后进先出的原则，因此移除的总是栈顶的元素。

function pop(stack) {
    if (stack.length === 0) {
        return undefined; // 如果栈为空，则返回undefined
    }
    const topElement = stack[stack.length - 1];
    stack.length = stack.length - 1;
    return topElement;
}

查看栈顶元素 (Peek)

查看栈顶元素操作是获取栈顶的元素而不移除它。

function peek(stack) {
    if (stack.length === 0) {
        return undefined; // 如果栈为空，则返回undefined
    }
    return stack[stack.length - 1];
}

检查栈是否为空 (IsEmpty)

检查栈是否为空操作是判断栈中是否有元素。

function isEmpty(stack) {
    return stack.length === 0;
}

获取栈的大小 (Size)

获取栈的大小操作是计算栈中元素的数量。

function size(stack) {
    return stack.length;
}

实现一个简单的栈类

我们可以将上述函数封装成一个栈类，以便更好地管理和操作栈。

// www.javascriptcn.com code example
class Stack {
    constructor() {
        this.items = [];
    }

    push(element) {
        this.items.push(element);
    }

    pop() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items.pop();
    }

    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }

    clear() {
        this.items = [];
    }

    toString() {
        return this.items.join(", ");
    }
}

栈的应用场景

括号匹配验证

括号匹配问题是计算机科学中的一个经典问题。使用栈可以有效地解决这个问题。每当遇到左括号时，我们将其压入栈中；当遇到右括号时，我们弹出栈顶元素并检查这对括号是否匹配。如果整个字符串处理完毕后，栈为空，则说明括号完全匹配。

// www.javascriptcn.com code example
function isBalanced(expression) {
    const stack = new Stack();
    const openingBrackets = "([{";
    const closingBrackets = ")]}";

    for (let char of expression) {
        if (openingBrackets.includes(char)) {
            stack.push(char);
        } else if (closingBrackets.includes(char)) {
            const lastOpeningBracket = stack.pop();
            if (!lastOpeningBracket || openingBrackets.indexOf(lastOpeningBracket) !== closingBrackets.indexOf(char)) {
                return false; // 括号不匹配
            }
        }
    }
    return stack.isEmpty(); // 如果栈为空，则说明括号匹配成功
}

后缀表达式求值

后缀表达式（也称为逆波兰表示法）是一种无需括号即可表示算术表达式的记法。例如，表达式 (5 + 4) * 3 可以写为 5 4 + 3 *。使用栈可以方便地计算这种表达式的值。

// www.javascriptcn.com code example
function evaluatePostfix(expression) {
    const stack = new Stack();
    const tokens = expression.split(" ");

    for (let token of tokens) {
        if (!isNaN(token)) {
            stack.push(Number(token));
        } else {
            const operand2 = stack.pop();
            const operand1 = stack.pop();
            switch (token) {
                case '+':
                    stack.push(operand1 + operand2);
                    break;
                case '-':
                    stack.push(operand1 - operand2);
                    break;
                case '*':
                    stack.push(operand1 * operand2);
                    break;
                case '/':
                    stack.push(operand1 / operand2);
                    break;
            }
        }
    }
    return stack.pop();
}

总结

栈作为一种简单而强大的数据结构，在计算机科学和编程中有着广泛的应用。通过学习和理解栈的工作原理及其基本操作，你可以更高效地解决许多实际问题。希望本章的内容对你有所帮助！