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

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

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

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

好啦，开工了老哥们！

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

⚡ 30 秒速记

• 遇左括号就把“期待的右括号”入栈，遇右括号与栈顶比较。
• 右括号出现时栈为空、类型不匹配，都立即返回 false。
• 扫描结束还要检查栈为空，否则 (( 会被误判。
• 每个字符至多进出栈一次：时间 O(n)，最坏空间 O(n)。

遇到左括号就把对应的右括号压栈，遇到右括号时只和栈顶比较。 括号嵌套要求最后打开的括号最先闭合，本质上正好符合栈的后进先出。若右括号出现时栈为空，或者弹出的字符与它不一致，就可以立即返回 false。扫描结束后还要确认栈为空，否则像 (( 这种未闭合输入会被误判；整体时间和最坏空间都是 O(n)。

回答参考：“括号嵌套要求最后打开的括号最先关闭，正好符合 LIFO。我把期望的闭括号压栈，右括号只需和栈顶比较。”

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

有效字符串需满足：

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

示例 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。