栈和队列这两个结构几乎每个写 Java 的人都背过定义一个后进先出一个先进先出。但真落到项目和面试里问题从来不是能不能说出定义而是给定一个场景你选哪个实现类为什么不用 Stack循环队列的满和空怎么区分阻塞队列的 put 和 offer 差别在哪。我自己在排查线上问题时就遇到过一个典型情况有人用Stack类做多线程下的任务暂存加了锁还是出了数据错乱最后换成ConcurrentLinkedQueue才消停。这些坑光看定义是看不出来的。这篇东西我想把 Java 里的 Stack 和 Queue 从头到尾捋一遍先划清楚栈这个词在工程语境下的几个不同含义再讲 Java 集合框架里到底有哪些实现、各自适合什么场合然后手写一遍底层结构把原理吃透最后把高频场景和踩坑记录整理成可以直接查的表。不管你是刚开始学 Java 数据结构还是刷题刷到单调栈卡壳或者面试前想把基础题重新过一遍应该都能从里面拎出点能用的东西。所有代码我都尽量给到能直接跑的程度参数和容量的推导过程也会写清楚不做背结论式的讲解。1. 先把栈和队列这两个词的范围划清楚1.1 同名不同物数据结构栈、调用栈、docker stack搜索stack这个词的时候结果会非常杂。排在前面的一般是三类东西数据结构里的栈、程序运行时的调用栈、还有容器编排里的docker stack命令。这三者除了名字一样几乎没有关系。docker stack是一组服务的部署单元跟后进先出没有半毛钱关系调用栈确实是栈结构但它是 JVM 在运行时维护的你在 Java 代码里操作不到它的压栈弹栈只能通过StackOverflowError这种异常间接感受到它存在。我之所以一上来就强调这个是因为见过太多初学者被搜索结果带偏去研究docker stack deploy的用法然后以为自己学的是数据结构。真正的数据结构栈和队列讨论的是一组元素的存取顺序约束栈只允许在一端进出队列允许一端进另一端出。这个约束一旦定下来后面所有实现方式、性能特征、适用场景都是从这条约束推导出来的。判断标准很简单如果你能用元素之间的相对顺序来描述它解决的问题那它就是我们今天要讲的东西。1.2 两个结构的本质差异与统一视角栈和队列在教科书里经常被并列讲因为它们有一个共同点都是操作受限的线性表。数组和链表可以随便在中间插、随便按索引取栈和队列则主动把一部分能力砍掉。栈砍得最狠只留下一个出入口所以最后进去的最先出来队列砍掉的是两端的灵活性只保留一头进一头出所以先进去的先出来。为什么要主动砍能力因为约束本身就是价值。当你把操作限制住以后调用方就不需要关心内部状态怎么变并发场景下也更容易推理。比如一个任务队列如果允许从中间删除元素那么某个任务到底还会不会被执行这件事就变得极难判断一旦限定只能在头部取出语义就清晰了。这一点在做系统设计时非常重要很多看起来功能更全的容器反而因为语义模糊而在生产环境里埋雷。从实现角度看两个结构都可以用数组或链表来支撑。用数组的好处是内存连续、缓存命中率高、随机访问快用链表的好处是扩容不需要搬运数据、节点可以动态分配。这个选择不是随便定的它直接决定了push和pop的常数因子差多少。后面第 3 节我会把两种实现都手写一遍你会看到同样是压栈这个动作数组版本要处理容量判断和扩容拷贝链表版本要处理新建节点和指针改写两边的边界条件完全不同。1.3 面试官为什么反复问这两个结构面试里栈和队列出现频率极高原因不是它们难而是它们是一块很好的能力试金石。一道用两个栈实现队列的题能同时考察四件事你对两个结构语义的理解是否准确、边界条件处理是否严谨、代码是否干净、能不能分析出均摊时间复杂度。再往深一点问为什么ArrayDeque不让存 null就是在看你有没有翻过源码。另一个原因是这两个结构是很多高阶算法的地基。深度优先搜索用栈或者递归递归本质就是借用 JVM 的调用栈广度优先搜索用队列单调栈和单调队列又是解决下一个更大元素滑动窗口最大值这类题的标准工具。如果基础结构没吃透这些题就只能靠背模板题型稍微一变就废了。所以我的建议是与其刷一百道题不如先把这两个结构的几种实现和它们的复杂度账算清楚后面遇到变体题你会发现自己能当场推出来。2. Java 里实现栈和队列的几种姿势与选型2.1 Stack 类能不用就别用理由有三条Java 的java.util.Stack是一个很老的类它能用但官方文档和几乎所有有经验的人都不推荐在新代码里用它。原因有三条每一条单独看都不致命叠在一起就很别扭。第一条是继承关系错了。Stack继承自Vector而Vector是一个可以按索引随机访问、可以在任意位置插入删除的容器。这就意味着一个Stack对象上你既可以调push/pop也可以调add(0, element)或者set(3, x)从中间把元素换掉。栈的语义是只能在一端操作但这个类把不该暴露的方法全暴露出来了等于约束形同虚设。第二条是同步粒度太粗。Stack的所有方法都是synchronized的锁在实例对象上。单线程环境下用它是白白付同步开销多线程环境下它又没法满足复合操作的原子性——你连续调isEmpty()和pop()中间照样可能被别的线程插进来把元素取走该空栈异常还是照抛。第三条是迭代顺序反直觉。Stack的迭代器是从栈底往栈顶走的跟pop的顺序正好相反。很多人在遍历的时候想按出栈顺序打印结果拿到的顺序是倒的调试半天才发现是迭代器的锅。所以新代码里要栈用Deque接口实现类选ArrayDequeDequeInteger stack new ArrayDeque(); stack.push(1); // 等价于 addFirst stack.push(2); stack.push(3); System.out.println(stack.pop()); // 3 System.out.println(stack.peek()); // 2注意ArrayDeque的push是把元素放到头部pop是从头部取行为跟栈完全一致。但如果你不小心调了add那就变成从尾部加了语义就乱了。我个人习惯是声明类型用Deque变量名直接叫stack代码评审时一眼就能看出意图。2.2 Deque 接口与 ArrayDeque一把梭Deque是 double ended queue 的缩写双端队列。它同时提供了栈和队列两套语义的方法操作位置栈语义队列语义队列语义失败返回特殊值头部插入push(e)/addFirst(e)-offerFirst(e)头部删除pop()/removeFirst()-pollFirst()头部查看peek()/peekFirst()-peekFirst()尾部插入-add(e)/addLast(e)offer(e)/offerLast(e)尾部删除-remove()/removeLast()poll()/pollLast()尾部查看-element()/getLast()peek()/peekLast()这张表建议直接存下来。关键要记住add/remove/element这一组失败时抛异常offer/poll/peek这一组失败时返回false或null。在有界队列或者可能为空的场景下永远优先用返回特殊值的那一组因为用异常做流程控制既慢又难看。ArrayDeque是Deque最常用的实现。它内部是一个循环数组不允许存null非线程安全绝大多数操作是 O(1)。作为栈用的时候它比Stack快作为队列用的时候它比LinkedList快因为内存连续缓存友好。可以说在单线程、不需要按优先级排序的场景下ArrayDeque基本是默认答案。2.3 队列家族全览普通队列、优先队列、阻塞队列、并发队列队列这边选择就多了得按需求分。普通 FIFO 队列ArrayDeque和LinkedList。后者实现了Deque也能当队列用但每个元素都要包一个Node对象多两个引用外加对象头内存开销大概比数组版本高两到三倍。除非你需要频繁在中间插入删除否则没有理由选它。优先队列PriorityQueue内部是二叉堆出队顺序由比较器决定不是先进先出。插入和删除都是 O(log n)取堆顶是 O(1)。注意它是非线程安全的而且它的迭代器不保证任何顺序想看有序结果只能用poll一个个取。阻塞队列ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue、SynchronousQueue、DelayQueue。这一族是生产者消费者模型的核心队空时取会阻塞队满时放会阻塞。并发无阻塞队列ConcurrentLinkedQueue、ConcurrentLinkedDeque基于 CAS 实现适合高并发且队列几乎不会真正满的场景。2.4 选型对照表需求推荐实现时间复杂度线程安全单线程栈ArrayDequepush/pop O(1)否单线程队列ArrayDequeoffer/poll O(1)否需要按优先级出队PriorityQueueoffer/poll O(log n)否固定容量阻塞队列ArrayBlockingQueueO(1)是高吞吐阻塞队列LinkedBlockingQueueO(1)是不存储元素的交接SynchronousQueueO(1)是高并发非阻塞ConcurrentLinkedQueue摊还 O(1)是需要延迟出队DelayQueueO(log n)是选型的核心判断线只有两条要不要线程安全要不要排序。这两条确定之后剩下的基本就是ArrayDeque和LinkedBlockingQueue二选一的问题。3. 手写实现底层原理一次讲透这一节我们把数组栈、循环队列、链表队列各写一遍。不是为了造轮子而是因为只有自己实现过才知道 JDK 里那些奇怪的设计比如为什么ArrayDeque的容量一定是 2 的幂、为什么循环队列要空一个槽到底在解决什么问题。3.1 数组栈扩容策略与摊还代价计算先看一个能跑的数组栈import java.util.EmptyStackException; public class ArrayStackE { private Object[] elements; private int size; private static final int DEFAULT_CAPACITY 10; public ArrayStack() { elements new Object[DEFAULT_CAPACITY]; } public ArrayStack(int initialCapacity) { if (initialCapacity 1) initialCapacity 1; elements new Object[initialCapacity]; } public void push(E e) { ensureCapacity(size 1); elements[size] e; } SuppressWarnings(unchecked) public E pop() { if (size 0) { throw new EmptyStackException(); } E e (E) elements[--size]; elements[size] null; // 断开引用帮助 GC return e; } SuppressWarnings(unchecked) public E peek() { if (size 0) { throw new EmptyStackException(); } return (E) elements[size - 1]; } public boolean isEmpty() { return size 0; } public int size() { return size; } private void ensureCapacity(int minCapacity) { if (minCapacity elements.length) { int newCapacity elements.length (elements.length 1); // 1.5 倍 if (newCapacity minCapacity) { newCapacity minCapacity; } Object[] bigger new Object[newCapacity]; System.arraycopy(elements, 0, bigger, 0, size); elements bigger; } } }这里面有两个细节值得展开。第一pop里为什么要写elements[size] null。如果不置空数组里那个槽位仍然持有对象的强引用只要栈对象活着这个元素就不会被回收也就是所谓的对象游离或者内存泄漏。JDK 的ArrayList、Vector在做删除时都会置空就是这个原因。我自己写第一版的时候漏了这行压了十万个订单对象再全部弹出堆占用一直不降查了半天才想起来。第二扩容倍数选多少。上面用的是 1.5 倍length length 1ArrayList也是这个策略。为什么不选 2 倍因为 1.5 倍在多次扩容后之前释放的内存块有机会被复用比如 10 → 15 → 22.5 取整 22 → 33旧块有的能被后续分配接上而严格的 2 倍扩容会导致前面所有块的总和永远小于下一块内存复用率差。代价是比较时的乘除运算1.5 倍可以用位移加一次加法代替开销很低。摊还代价的账是这样算的假设每次扩容翻倍从容量 1 开始压入 n 个元素。总拷贝次数是 1 2 4 ... n/2 n - 1 次加上 n 次写入总共约 2n 次操作摊到每个push上是 O(1)。注意是摊还 O(1)不是每次都是 O(1)——某一次push恰好触发扩容时要拷贝所有元素那一次就是 O(n)。这个区别在实时性要求高的系统里很重要像某些音视频处理场景偶尔一次卡顿都是事故这时候可能就要预先分配足够大的容量或者改用链表实现。3.2 循环队列为什么必须牺牲一个槽位队列如果也用数组实现直接从尾部追加、从头部删除删除后不搬数据那么头指针会一直往后走前面的空间永远用不上。解决办法是把数组首尾相接变成环形。但环形结构马上带来一个问题队空和队满的时候头尾指针的位置关系是一样的都满足head tail。怎么区分常见的有三种解法牺牲一个槽位认为队满条件是(tail 1) % capacity head此时实际元素数是capacity - 1。额外维护一个 size 变量队空看size 0队满看size capacity。维护一个标志位记录上一次操作是入队还是出队。我推荐第二种因为逻辑最直白而且size()方法是 O(1) 的不需要遍历。第一种会让人在算容量时反复踩坑——你声明容量 100实际只能存 99 个这个暗亏在很多初始化逻辑里都会被忽略。先看第一种的写法理解原理public class CircularQueueE { private Object[] data; private int head; // 出队位置 private int tail; // 入队位置 public CircularQueue(int capacity) { data new Object[capacity 1]; // 多留一个槽位 } public boolean offer(E e) { if (isFull()) return false; data[tail] e; tail (tail 1) % data.length; return true; } SuppressWarnings(unchecked) public E poll() { if (isEmpty()) return null; E e (E) data[head]; data[head] null; // 同样是防止对象游离 head (head 1) % data.length; return e; } SuppressWarnings(unchecked) public E peek() { return isEmpty() ? null : (E) data[head]; } public boolean isEmpty() { return head tail; } public boolean isFull() { return (tail 1) % data.length head; } }再看带size的版本跟上面的差别只在判断条件上public class CircularQueue2E { private Object[] data; private int head; private int tail; private int size; public CircularQueue2(int capacity) { data new Object[capacity]; } public boolean offer(E e) { if (size data.length) return false; data[tail] e; tail (tail 1) % data.length; size; return true; } SuppressWarnings(unchecked) public E poll() { if (size 0) return null; E e (E) data[head]; data[head] null; head (head 1) % data.length; size--; return e; } public int size() { return size; } }两个版本有个共同的坑取模运算。%在 Java 里对整数来说是一次除法虽然现代 CPU 上一个除法只占几十个周期但在每秒千万次入队的热点路径上这个开销是可观的。这就是下一节要讲的ArrayDeque为什么把容量固定成 2 的幂——一旦是 2 的幂(index 1) % length就可以换成(index 1) (length - 1)一条按位与指令搞定。3.3 链表实现与边界条件链表队列写起来不难但空队列转非空的那一刻最容易出错public class LinkedQueueE { private static class NodeE { E item; NodeE next; Node(E item) { this.item item; } } private NodeE head; // 出队端 private NodeE tail; // 入队端 private int size; public boolean offer(E e) { NodeE node new Node(e); if (tail null) { head tail node; // 第一个元素头尾都要指 } else { tail.next node; tail node; } size; return true; } SuppressWarnings(unchecked) public E poll() { if (head null) return null; E e head.item; head.item null; // 断开引用 head head.next; if (head null) { tail null; // 出队到空尾指针也要清 } size--; return e; } public boolean isEmpty() { return head null; } }两个必须同时更新的地方第一个节点入队时head和tail都要指向它最后一个节点出队后tail必须置回 null。漏掉后者的话tail会指向一个已经被摘掉的节点下一次入队就会挂到游离节点后面队列彻底断链。这个 bug 在单元测试里不一定暴露得出来因为只有清空后再入队这个序列才会触发很多测试用例恰好没覆盖到。链表实现的优势在扩容这件事上不需要整块搬运容量理论上只受内存限制。缺点也很实在每个元素多出的引用和对象头在小对象场景下非常浪费。我做过一个粗略的对比往LinkedList和ArrayDeque里各塞一百万条短字符串后者省下的堆内存大约在 30% 到 40% 之间。所以除非有明确的中间插入删除需求队列实现优先选数组版本。4. 源码与并发进阶细节4.1 ArrayDeque 用位运算取模的原理ArrayDeque内部的数组长度永远保持 2 的幂。在allocateElements方法里它会把传入的容量向上取到最近的 2 的幂private void allocateElements(int numElements) { int initialCapacity 8; // MIN_INITIAL_CAPACITY if (numElements initialCapacity) { initialCapacity numElements; initialCapacity | (initialCapacity 1); initialCapacity | (initialCapacity 2); initialCapacity | (initialCapacity 4); initialCapacity | (initialCapacity 8); initialCapacity | (initialCapacity 16); initialCapacity; if (initialCapacity 0) { initialCapacity 1; // 溢出则退到 2^30 } } elements new Object[initialCapacity]; }这段连续右移再或的操作效果是把最高位 1 下面所有位都填成 1再加一就得到下一个 2 的幂。比如传 11二进制 1011右移或之后变成 1111加一是 10000也就是 16。这是 32 位整数上的标准技巧JDK 里从HashMap到ArrayDeque都在用。扩容后的搬运也很有讲究。因为是环形结构元素可能被拆成了两段一段在head到数组末尾一段在数组开头到tail。doubleCapacity用两次arraycopy把它们拼到新数组的开头private void doubleCapacity() { int p head; int n elements.length; int r n - p; // head 右边有多少元素 int newCapacity n 1; // 翻倍 Object[] a new Object[newCapacity]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); elements a; head 0; tail n; }扩容倍数就是硬翻倍不是 1.5 倍。原因在于环形结构一旦容量不是 2 的幂所有取模运算就得退回除法这个损失远大于内存复用的收益。4.2 为什么 ArrayDeque 禁止 null这个是面试里很爱问的点。核心原因是null被用作队列为空的返回信号。poll()在队空时返回nullpeek()在队空时也返回null。如果允许存null那么当你拿到一个null的返回值时根本没法定制是队列本来就是空的还是取出来的元素本身就是 null。对比一下LinkedList它是允许存 null 的因为它用节点对象来表示链表结构节点存在与否跟节点里存什么值无关判断队空看的是head null而不是值。这就是结构表示和值表示的差异。用ArrayDeque的时候如果你确实需要表达空值用一个专门的哨兵对象代替比如private static final Object NULL_SENTINEL new Object();取出时再还原。顺带说一个相关点HashMap也允许 null 键和 null 值那是因为它用hashCode计算槽位对 null 做了特判null 的哈希值固定为 0但这也带来过不少争议。集合类比这个设计取舍挺有意思安全性和便利性往往要牺牲一个。4.3 阻塞队列的四组方法与你该选哪组阻塞队列把方法分成了四组这个表我建议背下来生产环境选错方法是很常见的翻车点操作抛异常返回特殊值一直阻塞超时退出插入add(e)offer(e)put(e)offer(e, time, unit)移除remove()poll()take()poll(time, unit)检查element()peek()不支持不支持怎么选看你对队列满/空这个状态的处理意愿。如果队列满了属于程序逻辑错误比如容量是按峰值 1.5 倍设置的用add让异常尽早暴露。如果满了只是暂时的背压希望稍后重试或者直接丢弃并记录用offer返回false然后自己决定策略。如果下游是必须等待的比如消费者必须拿到任务才能继续用put/take。我个人在生产代码里最常用的是带超时的offer因为它同时避免了无限阻塞和立即失败两个极端ArrayBlockingQueueTask queue new ArrayBlockingQueue(1000); boolean accepted queue.offer(task, 200, TimeUnit.MILLISECONDS); if (!accepted) { metrics.increment(task.rejected); // 落盘或者降级处理 }这个写法比put安全因为线程池被占满的情况下put会一直挂着拖垮整个线程池。超时时间给多少一般参考下游的平均处理耗时取它的两到三倍比较稳。4.4 线程安全队列的选型与陷阱LinkedBlockingQueue有个容易被忽略的默认行为无参构造时容量是Integer.MAX_VALUE。这意味着它实际上是无界的。生产者如果比消费者快很多任务会一直堆在队列里直到把堆撑爆抛OutOfMemoryError。所以这个类的正确用法是永远传一个容量参数哪怕是看起来很宽松的数字。这一点我在代码评审里见过太多次几乎每次都要提。ArrayBlockingQueue用的是单把锁读写互斥LinkedBlockingQueue用了两把锁putLock和takeLock入队和出队可以并行所以高并发下吞吐更好。代价是LinkedBlockingQueue每个节点都要额外维护一个AtomicInteger计数还有节点对象的开销。选的时候如果你追求的是极致的简单和可预测的延迟用ArrayBlockingQueue追求吞吐用LinkedBlockingQueue但记得设容量。SynchronousQueue比较特殊它不存储元素每个put必须等一个对应的take。它适合用来做线程之间的直接交接比如Executors.newCachedThreadPool()的内部队列就是它。用的时候要注意如果交接双方的速度不匹配会有一方一直等着。5. 高频实战场景逐个拆5.1 栈括号匹配、表达式求值、单调栈、列车调度括号匹配是最经典的入门题思路是遇到左括号就压栈遇到右括号就弹一个出来看是否匹配public boolean isValid(String s) { DequeCharacter stack new ArrayDeque(); for (char c : s.toCharArray()) { if (c ( || c [ || c {) { stack.push(c); } else { if (stack.isEmpty()) return false; char left stack.pop(); if ((c ) left ! () || (c ] left ! [) || (c } left ! {)) { return false; } } } return stack.isEmpty(); }最后那个stack.isEmpty()是关键忘了它的话像(((这种输入会被判成合法。这个小坑我在面试里问过不少人。表达式求值可以用双栈法一个栈存数字一个栈存运算符遇到优先级更高的运算符就往下压遇到低的就先把前面能算的都算完。也可以用经典的中缀转后缀再求值思路更清晰但代码长一些。单调栈是真正有实战价值的东西。它维护一个内部单调递增或递减的栈用来找下一个更大/更小元素。比如求柱状图中能形成的最大矩形面积或者求数组里每个元素右边第一个比它大的数public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; int[] answer new int[n]; DequeInteger stack new ArrayDeque(); // 存下标对应温度递减 for (int i 0; i n; i) { while (!stack.isEmpty() temperatures[i] temperatures[stack.peek()]) { int prev stack.pop(); answer[prev] i - prev; } stack.push(i); } return answer; }每个下标最多进栈一次、出栈一次所以整体是 O(n)。这个结构在工程里也有用比如统计最近一次价格下跌到今天隔了多少天或者处理带时间窗口的指标聚合。列车调度是数据结构课上的经典模型给一个入站顺序判断某个出站顺序是否可能。原理就是用一个栈模拟中转轨道能出就出出不了就继续进最后看栈是否为空。这个问题在真实的编组站调度里是有对应原型的只不过真实系统还要考虑轨道长度、优先级等约束。热词里出现列车调度 java我猜不少人是被课程设计卡住了把上面的模拟逻辑套一遍基本就能过。5.2 队列BFS、滑动窗口最大值、任务调度广度优先搜索用队列逐层扩展public int bfsShortestPath(int[][] grid, int[] start, int[] end) { int rows grid.length, cols grid[0].length; boolean[][] visited new boolean[rows][cols]; Dequeint[] queue new ArrayDeque(); queue.offer(start); visited[start[0]][start[1]] true; int steps 0; int[][] dirs {{1,0},{-1,0},{0,1},{0,-1}}; while (!queue.isEmpty()) { int levelSize queue.size(); // 关键记录当前层节点数 for (int i 0; i levelSize; i) { int[] cur queue.poll(); if (cur[0] end[0] cur[1] end[1]) return steps; for (int[] d : dirs) { int nr cur[0] d[0], nc cur[1] d[1]; if (nr 0 nr rows nc 0 nc cols grid[nr][nc] 0 !visited[nr][nc]) { visited[nr][nc] true; queue.offer(new int[]{nr, nc}); } } } steps; } return -1; }levelSize那一行是精髓它把当前这一层的所有节点和下一层的节点隔开这样才能正确统计步数。如果一边遍历一边入队层数就乱了。滑动窗口最大值用单调队列public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] result new int[n - k 1]; DequeInteger deque new ArrayDeque(); // 存下标对应值递减 for (int i 0; i n; i) { while (!deque.isEmpty() deque.peekFirst() i - k) { deque.pollFirst(); // 移出窗口 } while (!deque.isEmpty() nums[deque.peekLast()] nums[i]) { deque.pollLast(); // 保持递减 } deque.offerLast(i); if (i k - 1) { result[i - k 1] nums[deque.peekFirst()]; } } return result; }这里的队列两端都在用是典型的双端队列场景用ArrayDeque刚刚好。注意两个while的顺序不能反先清窗口外的再清比当前值小的否则边界会错。5.3 互相实现双栈队列、双队列栈用两个栈实现队列思路是把入队都压到in栈出队时如果out栈为空就把in栈里的元素全部倒过去再从out弹public class QueueByTwoStacksE { private final DequeE in new ArrayDeque(); private final DequeE out new ArrayDeque(); public void push(E e) { in.push(e); } public E pop() { if (out.isEmpty()) { while (!in.isEmpty()) { out.push(in.pop()); } } return out.pop(); } public E peek() { if (out.isEmpty()) { while (!in.isEmpty()) { out.push(in.pop()); } } return out.peek(); } public boolean empty() { return in.isEmpty() out.isEmpty(); } }均摊复杂度是 O(1)每个元素最多被倒一次从in搬到out之后要么被弹出要么一直待在out里。用两个队列实现栈思路是入栈时压到非空的队列出栈时把前 n-1 个元素搬到另一个空队列剩下的那个就是要弹出的public class StackByTwoQueuesE { private DequeE q1 new ArrayDeque(); private DequeE q2 new ArrayDeque(); public void push(E e) { DequeE nonEmpty q1.isEmpty() ? q2 : q1; nonEmpty.offer(e); } public E pop() { DequeE src q1.isEmpty() ? q2 : q1; DequeE dst q1.isEmpty() ? q1 : q2; while (src.size() 1) { dst.offer(src.poll()); } return src.poll(); } public E top() { DequeE src q1.isEmpty() ? q2 : q1; DequeE dst q1.isEmpty() ? q1 : q2; while (src.size() 1) { dst.offer(src.poll()); } E value src.poll(); dst.offer(value); return value; } }这个实现的pop是 O(n) 的比双栈方案差一档。但它的意义在于提醒你栈和队列之间不是完全对等的关系队列实现栈要付出更多代价。面试里如果被问到这道题先写出来再主动说明它是 O(n) 的往往比闷头写要加分。6. 踩坑记录与排查速查表6.1 常见报错与症状对照报错或症状常见原因排查方向EmptyStackException栈空还调pop/peek检查isEmpty判断和并发下的复合操作NoSuchElementException队列空调remove/element换成poll/peekNullPointerException往ArrayDeque里放了 null全链路排查是否有 null 值流入IllegalStateException: Queue full有界队列满还调add换offer并处理返回 falseOutOfMemoryError: Java heap spaceLinkedBlockingQueue没设容量检查构造函数是否传了容量出队顺序不对误用Stack的迭代器改用Deque或显式pop遍历元素取出来后还在内存里pop后没置空数组槽位检查自定义栈实现线程卡死不动put在没有消费者时一直阻塞换带超时的offer6.2 我踩过的几个坑第一个坑是拿Stack当并发容器用。早年做一个爬虫任务分发想着Stack的方法是synchronized的应该没问题结果消费线程判断完isEmpty到真正pop之间别的线程已经把元素取走了直接抛异常。后来改成每个线程各自一个ArrayDeque共享的任务池用ConcurrentLinkedQueue问题消失。这个教训是容器级别的同步不等于业务级别的原子性复合操作必须自己加锁或者用原子的判断方法。第二个坑是PriorityQueue的迭代顺序。排查一个排名功能时日志里打印出来的顺序乱七八糟一度以为比较器写错了。实际上PriorityQueue的迭代器是不保证顺序的因为它内部是堆堆的数组布局只保证父子关系不保证兄弟之间的顺序。要看有序结果只能反复poll。知道这一点之后我在需要打印的地方一律改成 while 循环出队。第三个坑是循环队列的容量计算。用牺牲一个槽位的写法时我按容量 100 创建数组结果第 100 个元素放不进去找了好久才反应过来需要capacity 1。这种约定式的东西最好在构造函数的注释里写死不然过两个月自己都会忘。第四个坑是ArrayDeque和LinkedList的性能差异。有一次做批量数据缓冲用了LinkedList当队列压测时吞吐上不去。换成ArrayDeque之后同样的逻辑吞吐涨了将近一倍。后来看 JFR 的火焰图大量时间花在节点对象的分配和 GC 上。从那以后只要没有中间插入删除的需求队列我一律用数组版本。6.3 刷题与工程中的习惯建议写题的时候我建议养成两个习惯。一个是初始化时就给出容量比如已知数据规模是 nnew ArrayDeque(n)能省掉多次扩容另一个是统一用Deque接口声明用ArrayDeque实例化不要把变量类型写成Stack或者LinkedList这样以后换实现只改一个地方。工程代码里还有一条我越写越认同的原则把队列的空/满当成正常状态处理不要当成异常。异常应该留给真正的程序错误而队列满只是背压的一种表现形式用返回值加上监控指标远远好过让异常在日志里刷屏。我在项目里落地过一个简单约定所有入队操作必须处理返回值静态检查工具会扫描未处理的offer调用这个约束帮我们避免了好几次线上堆积。最后再分享一个小技巧。如果你在排查队列相关问题时想知道某段时间内队列的深度变化不要只打点size()因为那是一个瞬时值。可以把size()和当前的System.nanoTime()一起记录下来事后画成曲线你能很清楚地看到是生产者突增还是消费者变慢。这个办法比在代码里到处加日志高效得多我在两个项目里都用它定位过问题根源一次是下游接口超时导致消费变慢一次是定时任务集中触发导致生产峰值都是看曲线一眼就出来了。
