从“500万躺平”聊到“用栈实现队列”：老码农的算法杂谈与Java实现

最近在网上刷到一个挺有意思的吐槽贴，一位自称38岁被裁的朋友说，自己卡里躺着500万，却感觉这笔钱“冰冷”，因为无房、未婚，对未来充满担忧。

这笔钱看着不少，但如果放在一线城市，考虑到买房、父母养老、个人医疗以及未来十几二十年的生活开销，500万确实不经花。所以他感到纠结非常正常：想直接躺平，又怕坐吃山空；想继续上班，又厌倦了职场的内耗。在我看来，这笔钱最大的价值在于提供了选择权，而不是用来硬撑或者随意挥霍的。真正的“躺平”，靠的或许不是两千万，而是一份清醒的规划和稳定的心态。

一道经典的面试题：用栈实现队列

那天正吃着外卖呢，油都快把键盘腌入味了，技术群里突然有人问我：“哥，算法题‘用栈实现队列’怎么写啊？” 你可别笑，这题目虽然基础，但在实际的老系统里还真可能遇到类似的场景。

比方说，有些遗留模块只暴露了一个“栈”的抽象接口，或者你为了统一调用方式，硬是把底层数据操作封装成了栈。但上层的业务逻辑明明需要的是队列的特性：先进来的任务必须先处理。最典型的就是“排队打单”、“排队发货”或者“失败任务排队重试”这类需求。很多人一着急，可能就直接用个 List，然后每次都 remove(0)。结果线上流量一上来，好家伙，性能直接卡成PPT。这时候，就得用两个栈来巧妙地“倒腾”一下，把顺序给“翻”过来。

思路其实很直观：准备两个栈，栈A专门负责入队（enqueue），栈B专门负责出队（dequeue）。入队操作很简单，新元素直接压入栈A。出队时，先看看栈B是不是空的。如果栈B里有元素，直接从栈B弹出栈顶元素（这就是最早该被处理的）；如果栈B是空的，那就把栈A里的所有元素一个一个地弹出来，再依次压入栈B。经过这么一倒，原本在栈A底部的（最先进入的）元素就跑到了栈B的顶部，下次出队时它就能第一个被弹出来。这个过程有点像洗牌，别管它像不像，能达到队列的FIFO效果就行。

下面给出一段能直接跑的Java代码，咱们不整那些花里胡哨的：

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;

public class StackQueue<E> {

    // 进队栈：只负责 push
    private final Deque<E> in = new ArrayDeque<>();
    // 出队栈：只负责 pop/peek
    private final Deque<E> out = new ArrayDeque<>();

    public void offer(E x) {
        in.push(x);
    }

    public E poll() {
        moveIfNeeded();
        if (out.isEmpty()) {
            return null; // 你也可以改成抛异常，看题目要求
        }
        return out.pop();
    }

    public E peek() {
        moveIfNeeded();
        if (out.isEmpty()) {
            return null;
        }
        return out.peek();
    }

    public boolean isEmpty() {
        return in.isEmpty() && out.isEmpty();
    }

    public int size() {
        return in.size() + out.size();
    }

    private void moveIfNeeded() {
        // 只有 out 为空时才倒腾，别每次都倒，会变慢
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }

    // 简单自测
    public static void main(String[] args) {
        StackQueue<Integer> q = new StackQueue<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);

        System.out.println(q.poll()); // 1
        q.offer(4);

        System.out.println(q.poll()); // 2
        System.out.println(q.peek()); // 3
        System.out.println(q.poll()); // 3
        System.out.println(q.poll()); // 4
        System.out.println(q.poll()); // null
    }
}

这段代码的关键就在于 moveIfNeeded() 这个方法。很多人容易犯的一个错误是，每次执行 poll 或 peek 操作时，都机械地把 in 栈的所有元素倒入 out 栈，处理完再倒回去，这就成了纯粹的“自我折磨”，时间复杂度会变得非常糟糕。正确的姿势是：只要 out 栈里还有元素，出队操作就只从 out 栈取。只有当 out 栈被取空时，才一次性将 in 栈的所有元素倒入 out 栈。这样摊还下来，每个元素最多被搬运两次（进in一次，进out一次），整体时间复杂度是 O(1) 的，非常高效。

当时我在群里还特意提醒了一句：实现这种数据结构时，别忘了考虑边界情况，比如空队列时 poll 或 peek 应该返回 null 还是抛出 NoSuchElementException。有些面试官就喜欢考察这种细节，看看你写的到底是一个健壮的队列，还是一个“不靠谱的盒子”。说到这儿，我的外卖也彻底凉了……不过话说回来，把这些基础算法和数据结构吃透，无论是应对面试还是优化实际项目中的老代码，都大有裨益。如果你对这类Java实现和优化技巧感兴趣，欢迎到云栈社区和更多开发者一起交流探讨。