栈与队列相关的问题就比较微妙了，很多时候相关题目中压根不会出现“栈”、“队列”这样的关键字，但只要你深入到真题里去、对栈和队列的应用场景建立起正确的感知，那么很多线索都会在分析的过程中被你轻松地挖掘出来。

这里也和大家分享一位读者在试读过程中的学习感悟：

感觉算法题除了理解还要靠练习，就像高考数学题，要锻炼出解题常规思维。任重道远啊🙊

其实就是这么回事，这也正是我们开篇就跟大家指明“以题为纲”这条路的初衷。

好啦，开工了老哥们！

# 典型真题快速上手-“有效括号”问题

题目描述：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 注意空字符串可被认为是有效字符串。

示例 1:

• 输入: “()”
• 输出: true

示例 2:

• 输入: “()[]{}”
• 输出: true

示例 3:

• 输入: “(]”
• 输出: false

示例 4:

• 输入: “([)]”
• 输出: false

示例 5:

• 输入: “{[]}”
• 输出: true

思路分析

括号问题在面试中出现频率非常高， 这类题目我们一般首选用栈来做。

为什么可以用栈做？大家想想，括号成立意味着什么？意味着对称性。

巧了，根据栈的后进先出原则，一组数据的入栈和出栈顺序刚好是对称的。比如说1、2、3、4、5、6按顺序入栈，其对应的出栈序列就是 6、5、4、3、2、1：

123456
654321

对称关系一目了然。

因此这里大家可以记下一个规律：题目中若涉及括号问题，则很有可能和栈相关。

回到题目中来，我们的思路就是在遍历字符串的过程中，往栈里 push 括号对应的配对字符。比如如果遍历到了 (，就往栈里 push )。

假如字符串中所有的括号都成立，那么前期我们 push 进去的一定全都是左括号、后期 push 进去的一定全都是右括号。而且左括号的入栈顺序，和其对应的右括号的入栈顺序应该是相反的，比如这个例子：

({[]})

最后一个入栈的左方括号[，与之匹配的右方括号]正是接下来第一个入栈的右括号。

因此，我们可以果断地认为在左括号全部入栈结束时，栈顶的那个左括号，就是第一个需要被配对的左括号。此时我们需要判断的是接下来入栈的第一个右括号是否和此时栈顶的左括号配对。如果配对成功，那么这一对括号就是有效的，否则直接 return false。

当判断出一对有效的括号之后，我们需要及时地丢掉它，去判断其它括号是否有效。这里这个“丢掉”的动作，就对应着两个括号一起出栈的过程。

每配对成功一对括号，我们都将这对括号出栈。这样一来，我们就可以确保栈顶的括号总是下一个需要被匹配的左括号。

如果说我们出栈到最后，栈不为空，那么意味着一部分没有被匹配上的括号被剩下来了，说明字符串中并非所有的括号都有效，判断 false；反之，则说明所有的括号都配对成功了，判断为 true。

编码实现

// 用一个 map 来维护左括号和右括号的对应关系
const leftToRight = {
  "(": ")",
  "[": "]",
  "{": "}"
};

/**
 * @param {string} s
 * @return {boolean}
 */
const isValid = function(s) {
  // 结合题意，空字符串无条件判断为 true
  if (!s) {
    return true;
  }
  // 初始化 stack 数组
  const stack = [];
  // 缓存字符串长度
  const len = s.length;
  // 遍历字符串
  for (let i = 0; i < len; i++) {
    // 缓存单个字符
    const ch = s[i];
    // 判断是否是左括号，这里我为了实现加速，没有用数组的 includes 方法，直接手写判断逻辑
    if (ch === "(" || ch === "{" || ch === "[") stack.push(leftToRight[ch]);