栈与队列 (Stacks & Queues)
为什么栈与队列很重要
栈和队列提供了严谨的 访问模式，是管理数据流和任务调度的核心基础：
- 栈 (LIFO)：函数调用栈、撤销 (Undo) 操作、表达式求值、回溯算法（DFS）。
- 队列 (FIFO)：任务调度、消息中间件、请求处理流、广度优先搜索（BFS）。
- 双端队列 (Deque)：窗口滑动、回文检测等两端操作场景。
- 优先级队列：任务权重调度、Dijkstra 最短路径算法、中位数动态追踪。
实际影响：几乎每个 Web 服务器都使用请求队列。一个配置不当的队列会导致高负载下的 503 错误，而配合背压 (Backpressure) 机制的合理限流能让系统吞吐量提升 10 倍。
核心概念
栈 (后进先出 - LIFO)
想象一叠盘子，你只能在顶部添加或取走。
- Java 最佳实践：使用
ArrayDeque。避免使用古老的Stack类，因为它继承自 Vector 且带有不必要的同步锁开销。
队列 (先进先出 - FIFO)
想象排队买票，先来的先走。
- 关键操作：
offer（入队）、poll（出队，若空返回 null）、peek（查看队头）。
双端队列 (Deque)
支持在两端高效执行插入和删除。
- 实现方案：
ArrayDeque（基于循环数组，推荐）或LinkedList（基于双向链表）。
深入理解
1. 单调栈 (Monotonic Stack)
核心逻辑：栈内元素始终保持单调递增或递减。当新元素破坏单调性时，弹出栈顶元素并记录结果。
- 应用场景：寻找下一个更大/更小元素（Next Greater Element）、接雨水、柱状图中最大的矩形。
2. 循环数组实现 (ArrayDeque)
原理：利用位运算 (head - 1) & (mask) 实现索引环绕，避免了数组元素的搬移。
- 收益：相比
LinkedList，它具有更好的 CPU 缓存局部性，且没有频繁创建 Node 对象的内存开销。
实战应用
带背压的请求队列
策略：使用有界队列。当队列满时，触发 offer 超时或直接拒绝（RejectedExecutionException），主动通知上游减速，防止系统因过载而崩溃（OOM）。
逆波兰表达式求值
逻辑：遇到数字入栈，遇到运算符弹出两个数字计算后将结果重新入栈。
面试高频题
Q1: 有效的括号 (简单)
思路：遇到左括号入栈对应的右括号，遇到右括号检查栈顶是否匹配且不为空。
Q2: 最小栈 (简单)
思路：辅助栈同步存储当前最小值，或者在主栈中存储 [值, 当前最小值]。
Q3: 用栈实现队列 (简单)
思路：双栈方案。一个 inStack 负责写，一个 outStack 负责读。只有当 outStack 为空时，才将 inStack 全部倒入。
Q4: 滑动窗口最大值 (困难)
思路：使用单调双端队列存储元素的索引。队列头部始终保存当前窗口的最大值索引。每移动一步，移除过期的索引，并保持队内元素单调递减。