栈和队列这四道题，我在不同时间段反复刷过三轮，每轮都有新体会。刚开始只觉得是套模板：栈先进后出，队列先进先出，互相实现一下，再拿栈去匹配括号、去重字符串，好像没什么难度。直到后面面试被追问"为什么用双向队列不用Stack类""为什么peek和pop要共用一段搬运逻辑"才意识到，这几道题真正想训练的不是背代码，而是理解数据结构之间的转换关系和边界条件。尤其232和225互为逆向，20和1047又恰好展示了栈的两个高频应用场景，四道题放在一起刷，性价比非常高。
这篇文章就完整记录我这轮重刷的全部思路和实现细节，包括Java里用Deque还是Queue的选择、摊还复杂度怎么算、哪些边界条件容易漏，以及我踩过的几个真实错误。无论你是刚开始刷题的新手，还是准备面试想快速过一遍栈队列专题的开发者，都可以直接参考这里的代码和思路。
1. 四个题目里的两条主线：先把数据结构想透
1.1 栈与队列的本质差异：死胡同和排队通道
很多初学者把栈和队列单纯记成"两种线性结构"，但它们的本质差异在操作受限方式上。栈只允许在一端插入删除，所以后进去的先出来，典型场景是一叠盘子，你只能从最上面拿；队列允许一端进另一端出，先来的先走，典型场景是食堂排队打饭。
这个差异直接决定了后面所有题目的思考方向。
232题要你用栈实现队列，本质上是想用"后进先出"模拟"先进先出"。一个栈做不到，因为数据顺序会被完全逆转；两个栈配合，一个负责收数据，一个负责吐数据，负担就出来了。225题反过来，要你用队列实现栈，队列的顺序是天然正向的，但栈需要的是"最后进来的先出去"，那就要想办法把队尾的元素挪到队首。
20题"有效的括号"是栈的典型应用，因为括号匹配天然具有"最近配对"的特性：遇到右括号时，需要和它匹配的左括号一定是最新出现的那个未匹配左括号，这正是栈顶元素。
1047题"删除所有相邻重复项"同样是栈的经典场，连续两个相同字符互相抵消，每抵消一次，新的相邻关系会暴露出来，继续判断，这个过程用栈可以做到线性扫描。
1.2 题目编排的隐藏逻辑：先互转，再应用
这四道题的顺序很有意思。232和225是"结构互转"题，逼着你把两种数据结构的底层行为差异抠清楚；20和1047是"栈的应用题"，拿栈去解决现实问题。先互转再应用，等于先让你彻底理解栈队列本身，再拿这种理解去解决实际问题。
我重刷时特意先不看题解，而是自己在白纸上推导"如果用栈实现队列，到底要几步才能把顺序翻回来"。这种推导过程比直接抄代码重要得多。理解了两组数据结构互相转换的原理，后面20和1047的解法本质上是"把栈当工具"，思路一下就顺了。
2. 题目一：用栈实现队列（232）：双栈翻转，把后进先出变成先进先出
2.1 为什么必须用两个栈：单栈根本无法完成任务
队列的特点是FIFO，先入队的元素先出队。栈的特点是LIFO，后入栈的元素先出栈。
如果只用一个栈，你往里面依次push了1、2、3，依次弹出的会是3、2、1，顺序完全颠倒。想要把它重新颠倒回1、2、3，必须再做一次逆序操作，也就是再来一个栈，把3、2、1依次压入第二个栈，再弹出时就是1、2、3。
所以双栈方案的核心思路非常清楚：
- inStack专门处理push操作，新元素直接压入；
- outStack专门处理pop和peek操作，当outStack为空时，把inStack中所有元素一次性倒入outStack，完成逆序翻转；
- outStack有数据时，直接从outStack弹出即可。
这样每次搬运完成后，outStack的栈顶就是队列的队首元素，栈顶到栈底恰好对应队首到队尾。
2.2 完整实现代码和一个关键细节
用Java实现时，我推荐使用Deque接口配合ArrayDeque作为栈的底层实现，而不是古老的Stack类。Stack类继承自Vector，所有方法都带Synchronized，单线程环境里有不必要的开销，而且Stack和ArrayDeque在性能上差距明显。ArrayDeque底层是循环数组，入栈出栈都是常数时间且没有任何同步锁。
class MyQueue { private Deque<Integer> inStack; private Deque<Integer> outStack; public MyQueue() { inStack = new ArrayDeque<>(); outStack = new ArrayDeque<>(); } public void push(int x) { inStack.push(x); } public int pop() { if (outStack.isEmpty()) { inToOut(); } return outStack.pop(); } public int peek() { if (outStack.isEmpty()) { inToOut(); } return outStack.peek(); } public boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); } private void inToOut() { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } }这段代码里最需要关注的地方是peek和pop都要先检查outStack是否为空，并且要复用同一个搬运逻辑。我第一版实现把搬运代码复制了两份，后面改成inToOut()方法后，不仅代码更整洁，逻辑也更不容易出错。
还有一个细节：empty()方法判断的是两个栈同时为空。有人会漏掉inStack的判断条件，但队列里只要还有元素没搬运到outStack，就不能算空。比如连续push三次然后peek一次，outStack里有数据，没问题；但如果连续push三次一次都没pop，inStack里有数据而outStack为空，直接判断outStack.isEmpty()就会误判。
2.3 摊还时间复杂度与常见的面试追问
每次push是O(1)，直接压栈。每次pop如果outStack非空也是O(1)；如果为空，需要把inStack中所有元素搬运过来。这个搬运操作单次最坏是O(n)，但每个元素只会被搬运一次，所以把连续n次pop操作看成一个整体，总代价还是O(n)，平均到每次pop就是O(1)。这就是摊还时间复杂度的含义，面试官问到"为什么符合队列要求"时，这个解释很关键。
我实际遇到过面试官追问：如果频繁地push一次、pop一次、push一次、pop一次，会不会导致每次都触发搬运？答案是不会。因为每次搬运后outStack里有数据，下一次pop直接从outStack取，只有outStack被取空了且inStack有新数据时才会再次搬运。频繁交错push和pop时，每次pop虽然可能触发搬运，但搬运一次能支撑后续多次pop，整体依然是摊还O(1)。
3. 题目二：用队列实现栈（225）：单队列循环滚动是个巧妙思路
3.1 双队列法：一个主队列加一个备份队列
用队列实现栈有两条常见路线，第一种是双队列法。核心策略是push时将元素放入主队列，然后依次取出主队列中除了新元素以外的所有元素放入备份队列，最后再把这部分元素搬回来，确保新元素始终在队首，队首就对应栈顶。
class MyStack { private Queue<Integer> queue; public MyStack() { queue = new LinkedList<>(); } public void push(int x) { queue.offer(x); int size = queue.size(); for (int i = 0; i < size - 1; i++) { queue.offer(queue.poll()); } } public int pop() { return queue.poll(); } public int top() { return queue.peek(); } public boolean empty() { return queue.isEmpty(); } }仔细看这段代码：push时先把新元素offer到队尾，然后统计当前队列长度size，再把前面size - 1个元素依次出队并重新入队。执行完这一串操作后，最新的元素已经被轮转到队首。
这种单队列的push是O(n)，pop和top是O(1)，空间复杂度O(n)。比起维护两个队列，单队列在空间上更省，逻辑也更好想。我第一次自己写就是用的双队列，写得绕来绕去，后来看题解改成单队列，反而一下就通了。
3.2 为什么单队列够用：循环移动就能改变队首
单队列方案的精髓在于：队列本身是环形的逻辑结构，把前n-1个元素依次搬到队尾，新元素自然就成了队首。这个操作不需要额外空间，一个队列反复轮转即可完成。
用生活类比的话，就像几个人排队买奶茶，最前面的人和最后面的人互换位置不方便直接实现，但如果让队伍整体转动一圈，让最后一个走到第一位，问题就解决了。队列的offer和poll组合恰好可以完成这种转动操作。
3.3 复杂度和面试扩展：从栈延伸到滚动数组
双队列法和单队列法做对比，差别主要体现在push操作的代价和额外空间上：
| 实现方案 | push | pop/top | 额外空间 |
|---|---|---|---|
| 双队列法 | O(1) | O(n) | 需要第二个队列 |
| 单队列滚动法 | O(n) | O(1) | O(1) |
两种方案都满足栈的行为要求，但在实际刷题和面试中，我更推荐单队列滚动法，因为代码量更少，边界条件也更简单。面试官还会顺着问"如果让你用两个队列实现栈，反过来用两个栈实现队列，这两种转换的时间复杂度差异在哪里"，核心答案就是：栈转队列借助了逆序翻转的摊还思想，队列转栈则借助了循环滚动的整体搬移思想。
4. 题目三：有效的括号（20）：栈的配对与剪枝逻辑
4.1 为什么括号匹配适合栈：最近配对原则
括号匹配的问题场景很典型：遇到右括号时，要判断它是否和最近的左括号匹配。这个"最近"天然对应栈顶。
比如( [ ] )这个序列，扫描到(入栈，扫描到[入栈，现在栈顶是[；遇到]时弹出栈顶[，匹配成功；遇到)时弹出栈顶(，匹配成功。整个过程没有任何冲突。
但如果是( [ ) ]，扫描到)时栈顶是[，不匹配，直接判false。
4.2 剪枝技巧：奇数长度一律false，入栈右括号更简洁
写这个题最直观的版本是：遇到左括号就push左括号，遇到右括号就检查栈顶是否是对应的左括号。这种做法没问题，但我更推荐另一种写法：遇到左括号时直接push对应的右括号，遇到右括号时只需检查栈顶是否等于当前字符。
class Solution { public boolean isValid(String s) { if (s == null || s.length() % 2 != 0) { return false; } Deque<Character> stack = new ArrayDeque<>(); for (char c : s.toCharArray()) { if (c == '(') { stack.push(')'); } else if (c == '[') { stack.push(']'); } else if (c == '{') { stack.push('}'); } else { if (stack.isEmpty() || stack.pop() != c) { return false; } } } return stack.isEmpty(); } }这个写法的好处有三个：
第一，入栈的是右括号而不是左括号，遇到右括号时只需要比较当前字符和栈顶是否相等，省去了一堆if-else的配对映射，代码更短更清晰。
第二，奇数长度的字符串可以直接返回false。括号必须成对出现，奇数长度一定不可能全部匹配，这个剪枝能省掉一些无谓的遍历。
第三，栈里存右括号不会丢失信息，弹出的那一刻如果和当前字符相等，说明匹配；如果不相等，说明括号交叉乱了。
4.3 容易被忽略的边界条件与高频变体
这个题目最常见的错误是漏掉栈非空的判断。比如输入是]，扫描到右括号时栈是空的，此时直接stack.pop()会抛异常，必须先判断stack.isEmpty()，为空直接返回false。
另一个常见错误是最后忘记判断stack.isEmpty()。比如输入是(，只有一个左括号，后面什么都没了，如果不检查栈是否为空，就会错误地返回true。完整的括号匹配必须保证扫描结束后栈也空了。
面试延伸场景很丰富：一对一括号匹配之外，还有带通配符的括号匹配（*可以当左括号、右括号或空），这时候单纯用栈就不够了，需要贪心思路维护左括号数量的上下边界。还有一种问题是让嵌套深度最大最小化，这属于构造问题了。
5. 题目四：删除字符串中的所有相邻重复项（1047）：栈的消消乐场景
5.1 思路核心：相邻消除会引发新的相邻关系
删除所有相邻重复项这个任务，要求反复删除相邻且相同的字符，直到没有连续两个相同字符为止。直接暴力做法是每次从左往右找相邻相等字符，删掉后重头再来，最坏情况是O(n²)。用栈可以把复杂度降到O(n)，因为每扫描一个字符，只需要和当前栈顶比较：
- 如果和栈顶相同，说明这两个字符相邻重复，弹出栈顶相当于消除；
- 如果和栈顶不同，压入栈中等待后续匹配。
这里有个隐藏点：消掉一对之后，新的相邻关系会马上暴露出来。比如abbaca，扫描到第一个b压栈，第二个b和栈顶b相同，弹出；接着扫描到a时，当前栈顶已经变成了前面的a，两个a又匹配，继续弹出。这就是栈的"动态暴露新相邻对"特性，模拟了字符串连续消除的过程。
5.2 一个更加高效的写法：直接用字符串模拟栈
很多人实现这道题时会先开辟一个显式的Stack，最后还得把栈里字符反转拼接。但实际上可以直接用StringBuilder做栈的载体，既省去显式的栈结构，也省去最后反转的操作。
class Solution { public String removeDuplicates(String s) { StringBuilder sb = new StringBuilder(); for (char c : s.toCharArray()) { if (sb.length() > 0 && sb.charAt(sb.length() - 1) == c) { sb.deleteCharAt(sb.length() - 1); } else { sb.append(c); } } return sb.toString(); } }StringBuilder的末尾相当于栈顶，删除末尾字符就是出栈，追加字符就是入栈。deleteCharAt(sb.length() - 1)和append(c)分别对应pop和push，代码简洁且不用反转。
从复杂度上看，遍历一次字符串，每次操作常数时间，整体O(n)，空间O(n)。对比显式用栈再反转的做法，这个写法空间占用相同，但少了一次栈出栈拼接的反转操作，常数更小。
5.3 这个题还可以变形：从相邻消除到保留部分重复
面试官常把这道题作为引子，继续考变体。比如"删除相邻重复项，但允许保留恰好2个相同字符"，或者"删除相邻且不同的配对"这类问题。
变体思路的核心还是栈，只是栈里存的不是单个字符，而是字符和它的出现次数。当出现次数达到阈值时弹栈，否则更新次数。这种"栈存二元组"的思路从这道题延伸出去，很多字符串处理题都能复用。
还有一种方向是不用额外栈，用双指针原地修改字符串。一个指针负责扫描，另一个指针负责写入位置，写入位置同时充当栈顶指针，空间复杂度降到O(1)。这在面试中属于进阶讲法，能主动提出会有加分效果。
6. 刷题踩坑与考场经验：这几处我最容易翻车
6.1 Java刷栈队列的避坑指南：选对容器是关键
Java里刷这类题，最容易被绊倒的点之一是容器选择。Java的Stack类虽然也叫栈，但它是继承Vector实现的，所有方法都加锁且性能较差。刷题和面试手写代码时，更标准的选择是用ArrayDeque，它实现Deque接口，支持push、pop、peek，效率高且语义清晰。
另一个容易混淆的点是Queue接口使用时要留意实现类的选择。Java标准库中LinkedList实现了Queue接口，可以用offer入队、poll出队、peek查看队首。也可以用ArrayDeque来实现队列，但注意ArrayDeque不允许null元素，如果业务里有null入队就会出问题，刷题一般用LinkedList更安全。
poll()和pop()的区别也值得记清楚。pop()是栈方法，栈为空时抛异常；poll()是队列方法，队列为空时返回null。在一道题里混用两种方法时想清楚自己是在用栈还是队列，别写出自己都看不懂的代码。
6.2 关于复杂度分析的三个常见面试追问点
面试官对这一专题的问题往往集中在复杂度上。针对232题，需要说出"每个元素最多被搬运两次，一次入inStack一次入outStack，所以均摊下来每次操作是O(1)"，只背结果不解释过程容易露馅。针对225题，要能说清为什么push要O(n)而pop是O(1)，核心在于每次push都要把前面的元素整体轮转到新元素后面。针对1047题，如果数据结构上写的是使用StringBuilder来做栈，复杂度依然是O(n)空间，不能因为没显式写Stack类就说"空间O(1)"。
我一个朋友在模拟面试时把1047题的空间复杂度答成了O(1)，理由是用了双指针不用额外栈，这其实是因为他直接用了题解里的双指针写法。双指针写法确实O(1)空间，但如果代码里用的是StringBuilder，它本身就是长度可变的额外空间，复杂度应该是O(n)。要诚实描述自己写的代码。
6.3 面试官最喜欢怎么考这个专题
这几道题在面试中出现的频率极高，但很少直接让你默写。常见问法是：
- "给我设计一个支持在平均O(1)时间内完成入队出队操作的队列实现"——对应232。
- "如果队列很大，怎样才能减少翻转次数"——对应232的摊还优化讨论。
- "实现一个支持返回栈顶元素且不用额外空间的栈"——对应225的单队列法。
- "括号匹配不只有大小两种括号时，代码会不会失控"——对应20。
- "在流式数据里如何维护不重复相邻字符的结果"——对应1047的在线处理特性。
这类问题考察的核心其实就是"你理解不了解数据结构转换时的行为表现"，而不只是记住代码模板。多在自己脑子里模拟几遍操作过程，比背题解有用。
6.4 一个复杂度速查表，方便面试前快速回忆
| 题目 | 核心操作 | 单次操作最坏复杂度 | 摊还/平均复杂度 | 额外空间 |
|---|---|---|---|---|
| 232 用栈实现队列 | pop / peek | O(n) | O(1) | O(n) |
| 225 用队列实现栈 | push / pop | 每次push O(n) | push O(n)，pop O(1) | O(n) |
| 20 有效的括号 | 单个字符处理 | O(1) | 总时间O(n) | O(n) |
| 1047 删除相邻重复项 | 单字符比较删除 | O(1) | 总时间O(n) | O(n) |
表格里232的pop单次最坏是O(n)是因为触发搬运时要把inStack所有元素倒出去，但摊还下来是O(1)。225如果采用双队列法，push是O(1)，pop变成O(n)；如果采用单队列法正好相反。这个表是我自己整理用来快速复习的，每次面试前扫一眼就能把复杂度拎清楚。
再分享一个我在实操中反复验证的小技巧：刷这类栈队列题目，最好养成"先画一遍执行过程再写代码"的习惯。232题画两个栈之间元素的转移过程，225题画队列元素在push前后的位置变化，20题画括号入栈出栈的时序，1047题画字符串扫描到消除时栈顶的变化。画完图再写代码，正确率明显会提高，尤其是面试白板题，这个习惯能帮你快速理清思路。
这几道题从表面看都是"数据结构模拟题"，但反复刷完之后回头看，它们的价值在于逼着你把栈和队列的底层行为彻底想透。232是靠翻转构建逆序，225是靠轮转构建逆序，20靠的是栈顶最近匹配，1047靠的是消除的动态暴露，四道题把栈队列最常见的使用场景完整覆盖了一遍。把这组题吃透，后面面对单调栈、滑动窗口、表达式求值等问题时，基础都会更扎实。
