#232

简单

中频

栈

用栈实现队列

这是一道围绕栈、队列展开的高频练习。建议先掌握「栈」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

栈

队列

原题练习

题目分析

这道题表面上是在处理「用栈实现队列」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考栈、队列这些能力。这类题的重点往往不是代码量，而是识别“后进先出”的顺序是否正好对应题目的处理需求。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：一个输入栈负责入队，一个输出栈负责出队；只有输出栈空时才把输入栈整体倒过去。

推荐代码

推荐解法：栈

时间复杂度：均摊 O(1)

空间复杂度： O(n)

核心思路：一个输入栈负责入队，一个输出栈负责出队；只有输出栈空时才把输入栈整体倒过去。

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new ArrayDeque<Integer>();
        outStack = new ArrayDeque<Integer>();
    }

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会用两个栈模拟队列，一个负责输入，一个负责输出。

核心过程

push 时只往输入栈压。
当需要 pop 或 peek 且输出栈为空时，再把输入栈整体倒到输出栈。
此时输出栈顶就是队首元素。
由于每个元素最多只被搬运一次，所以均摊复杂度是 O(1)。

复杂度总结

均摊时间复杂度 O(1)，空间复杂度 O(n)。

面试补一句：双栈队列最值钱的一句解释是“懒搬运”。

核心思路

用栈实现队列的关键，是把“先进先出”拆成两次“后进先出”。输入栈负责收集新元素，输出栈负责把顺序翻转成可出队状态。

步骤讲解

入队只压输入栈

push 操作直接把元素压入 input 栈。

为什么这样做：入队不需要立刻调整顺序。

对应代码提示：input.push(x);

输出栈空时再整体倒栈

只有当需要 peek/pop 且 output 为空时，才把 input 元素逐个倒入 output。

为什么这样做：这样每个元素最多只会被搬运一次，保证均摊复杂度。

对应代码提示：while (!input.isEmpty()) output.push(input.pop());

出队和取队首都看输出栈顶

完成倒栈后，output 栈顶就代表队列最前面的元素。

为什么这样做：倒栈把原本最早进入的元素翻到了最上面。

对应代码提示：return output.pop();

易错点

每次 push 都立刻倒栈

虽然能实现功能，但没有必要，效率也差。

正确理解：采用懒搬运策略，只在 output 为空时转移。

没理解均摊 O(1)

看到倒栈循环就误以为单次最坏成本代表整体复杂度。

正确理解：说明每个元素最多进出两次栈，因此均摊仍是 O(1)。

peek 和 pop 使用逻辑不一致

两个接口若一个倒栈一个不倒栈，状态就会混乱。

正确理解：统一抽出 moveIfNeeded() 之类的辅助逻辑。

复杂度与适用判断

时间复杂度：均摊 O(1)

空间复杂度：O(n)

比其他方案更好在哪里：比每次出队都重排所有元素高效很多。

适用判断：如果要用一种数据结构模拟另一种顺序语义，常见技巧就是延迟转换。

额外提醒

输入栈收集新元素，输出栈暴露队首元素。

动画演示

如果你还没完全看懂，可以展开动画演示。

栈动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

操作序列

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。