前言

在编程领域，栈（Stack）是一种常见的数据结构，它具有后进先出（Last In, First Out，LIFO）的特性。栈在许多算法和数据结构中都有重要的应用，因此在面试中，关于栈的问题也经常出现。

本部分将介绍常见的栈面试题，包括栈的基本概念、操作和应用。通过面试题，我们将深入了解栈的工作原理以及如何在实际编程中有效地使用它。

正文

栈的介绍

在 JavaScript 中，没有单独的栈结构，但是可以使用数组来模拟栈的行为。实际上，栈就是数组的一种应用场景，你可以将数组看作是一个被“阉割”的栈。

在使用数组模拟栈时，push 方法用于向数组末尾添加元素，pop 方法用于从数组末尾移除元素，它们一起使用可以实现入栈和出栈操作。而 unshift 方法用于向数组开头添加元素，shift 方法用于从数组开头移除元素，这两个方法一起使用也可以模拟一种特殊的入栈和出栈操作（与常规的栈操作顺序有所不同）。

栈只能从栈顶进出，而数组可以在数组的任何位置进出。

题目（力扣20）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。

示例

示例 1：
输入：s = "()"
输出：true

示例 2：
输入：s = "()[]{}"
输出：true

示例 3：
输入：s = "(]"
输出：false

题解

思考

我们将字符串s想象成一个栈。如将示例2中s = "()[]{}"，想象成[ '(' , ')' , '[' , ']' , '{' , '}' ]。我们创建一个stack栈后，我们将这个栈的右边看作为栈顶，从右往左依次通过pop方法出栈(pop方法除了可以移除元素，还能返回被移除的元素)。我们获取出栈元素item后进行判断：

• 如果item为右括号：我们就期待着有一个对应的左括号与之匹配，我们将所期待的括号放进创建的stack栈中。
  • 如果item为 ')'：将'(' 放入stack栈中。
  • 如果item为']' ：将'['放入stack栈中。
  • 如果item为'}'：将'{' 放入stack栈中。
• 如果item为左括号：说明我们遇到了我们所期待的左括号，我们只需要让stack的栈顶元素出栈并且获取其值item1然后再进行判断是否为对应的左括号。
  • 如果item为'(' ：
    • 如果item1不为'('则return false。
  • 如果item为'['：
    • 如果item1不为'['则return false。
  • 如果item为'{' ：
    • 如果item1不为'{'则return false。
• 如果都不是则return false。

待循环结束后，我们判断stack是否还存在我们所期望的括号，也就是判断stack.length是否为0：

若为0，则说明所有括号都匹配完成，就return ture。

若不为0，则说明还有括号没有配对，就return false。

图解

通过s="{[()]}"进行图解括号匹配过程。

最终匹配成功。

代码

将字符串s转换为栈（数组）进行操作。

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    let stack = []
    let arr = s.split('');
    while (arr.length) {
        let item = arr.pop();
        if (item == '}')
            stack.push('{');
        else if (item == ')') {
            stack.push('(');

        }
        else if (item == ']') {
            stack.push('[');
        }
        else {
            var item1 = stack.pop()
            if (item1 != item)
                return false;
        }
    }
    if (stack.length != 0)
        return false;
    else
        return true;
}

但是你会发现代码的可读性太差了，也就是不够优美。那我们在原本的思路上面进行一些优化。

1. 我们可以创建一个对象，使其键名为右括号，键值为对应的左括号。(可以减少判断的次数)
2. 我们在思考时可以把字符串s当作栈更好理解，但是字符串s也能通过遍历字符串替代栈的出栈操作。（原代码把字符串s转换为了栈，这一步可以省略，可以减少空间复杂度）
3. 最后在循环结束时，我们可以直接return !stack.length；因为在 JavaScript 中，0被视为假（false），而不是真（true）。（也可以减少判断语句）

优化后的代码

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {             
    let rightToLeft = {
        ')': '(',
        '}': '{',
        ']': '['
    }
    const stack = []
    for (let i = s.length - 1; i >= 0; i--) {
        if (s[i] == ')' || s[i] == '}' || s[i] == ']') {
            stack.push(rightToLeft[s[i]]);
        }
        else {
            if (s[i] != stack.pop())
                return false;
        }
    }
    return !stack.length；
}

小tips

你可能会发现，在stack栈内没有元素时进行pop操作会有点不对劲，感觉应该会报错才对，但是怎么没有报错呢？

在浏览器运行这段代码时并没有报错，并且输出的结果是undefined。

当stack.pop()的值为undefined时，会在判断括号是否匹配时return fasle。

小结

这篇文章有详细的思路和图解过程，以及优化思路。希望对你有帮助。