LeetCode 232. 用栈实现队列

2026-03-09 HGNULB 约 5 分钟

文章信息 29 个分类 3 个标签

分类

LeetCode CodeTop 简单已解决已掌握 100-200 腾讯字节阿里微软亚马逊美团京东小米百度网易小红书快手滴滴携程虾皮米哈游 OPPO vivo 招行深信服爱奇艺猿辅导作业帮

题目描述

✅ 232. 用栈实现队列

题意分析

只使用两个栈实现队列，支持入队 push、出队 pop、查看队首 peek 和判空 empty。队列要求先入队的元素先出队；pop 会删除队首并返回它，peek 只返回队首，不改变队列内容。

底层只能使用栈的压栈、弹栈、查看栈顶和判空等操作，不能直接从容器底部取元素。题目保证 pop 和 peek 只在非空队列上调用，因此不需要自行约定空队列时的返回值。

解法：双栈延迟搬运

核心思路

[!blue]

单个栈的栈顶是最近加入的元素，与队列要先取最早元素相反。把一个栈中的全部元素依次弹出、压入另一个栈，顺序会反转：最早入队的元素最后被搬过去，恰好位于第二个栈的栈顶。

因此用 inStack 接收新元素，用 outStack 提供队首。队列的完整次序始终是：先读 outStack 从栈顶到栈底的元素，再读 inStack 从栈底到栈顶的元素。只要 outStack 还有元素，它们就都比 inStack 中后来加入的元素更早入队。

pop 和 peek 调用同一个搬运操作：outStack 非空时直接使用它的栈顶；只有它为空时，才把 inStack 全部倒入。提前搬运会把较新的元素压在较旧的元素上面；只搬一部分又会让最早入队的元素留在输入栈底部。这两种做法都会破坏队列顺序。

元素搬入 outStack 后就留在那里，直到被弹出，不需要再搬回输入栈。每个元素最多经历一次输入栈入栈、一次转移和一次输出栈出栈，所以虽然某次操作可能搬很多元素，多次操作的总搬运次数仍是线性的。

解题步骤

创建输入栈 inStack 和输出栈 outStack，二者开始时都为空。

push 将新元素压入 inStack，已有输出栈保持原状。

pop 和 peek 先调用 move：输出栈为空时，将输入栈的元素全部逐个弹出并压入输出栈；否则不搬运。

pop 弹出并返回输出栈栈顶，peek 只读取并返回该栈顶。

empty 同时检查两个栈，只有二者都为空，队列才为空。

代码实现

class MyQueue {
    private final Deque<Integer> inStack = new ArrayDeque<>();
    private final Deque<Integer> outStack = new ArrayDeque<>();

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

    public int pop() {
        move();

        return outStack.pop();
    }

    public int peek() {
        move();

        return outStack.peek();
    }

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

    private void move() {
        // 只有旧输出栈耗尽，才搬运后来进入的元素。
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                // 全部倒入会反转顺序，使最早入队元素来到栈顶。
                outStack.push(inStack.pop());
            }
        }
    }
}

type MyQueue struct {
    inStack  []int
    outStack []int
}

func Constructor() MyQueue {
    return MyQueue{}
}

func (q *MyQueue) Push(x int) {
    q.inStack = append(q.inStack, x)
}

func (q *MyQueue) Pop() int {
    q.move()
    x := q.outStack[len(q.outStack)-1]
    q.outStack = q.outStack[:len(q.outStack)-1]
    return x
}

func (q *MyQueue) Peek() int {
    q.move()
    return q.outStack[len(q.outStack)-1]
}

func (q *MyQueue) Empty() bool {
    return len(q.inStack) == 0 && len(q.outStack) == 0
}

func (q *MyQueue) move() {
    // 输出栈还有更早的元素，不能让新元素越过它们。
    if len(q.outStack) > 0 {
        return
    }
    for len(q.inStack) > 0 {
        i := len(q.inStack) - 1
        // 全部倒入会反转顺序，使最早入队元素来到栈顶。
        q.outStack = append(q.outStack, q.inStack[i])
        q.inStack = q.inStack[:i]
    }
}

复杂度分析

时间复杂度：push、pop、peek 的摊还时间为 $O(1)$，empty 为 $O(1)$。一次 pop 或 peek 可能搬运全部元素，最坏为 $O(n)$；这里使用的动态数组栈在扩容时也可能有线性开销。对连续的 $m$ 次操作，每个加入的元素最多搬运一次，动态数组扩容的总开销也可摊还，因此总时间为 $O(m)$。

空间复杂度：$O(n)$，两个栈保存的元素总量随队列规模增长。动态数组可能保留已申请的容量，因此按操作过程中的最大队列规模计算空间上界。

关键点总结

[!green]

输出栈提供较早加入的元素，输入栈暂存较晚加入的元素，两者共同组成队列。

仅在输出栈为空时，把输入栈全部倒入，才能让最早元素位于栈顶。

每个元素只从输入栈转移到输出栈一次，这是摊还常数时间的原因。

易错点总结

[!yellow]

输出栈非空时仍搬运，新元素会越过旧元素，破坏先进先出的顺序。

只从输入栈搬一个元素，取到的是最近入队的元素；必须全部倒入，才能反转整段顺序。

每次出队后再把元素倒回去，会让同一元素反复搬运，失去摊还 $O(1)$ 的性质。

peek 也要在必要时搬运，但不能从输出栈删除队首，否则它的行为就变成了 pop。

empty 只检查一个栈，会漏掉另一个栈中仍然存在的元素。

把摊还 $O(1)$ 写成每次操作最坏 $O(1)$，忽略了单次集中搬运的开销。

相似题目

题目	难度	关联与区别
225. 用队列实现栈	简单	原题反过来用队列实现栈，本题利用两次倒序恢复FIFO。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/06263683

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！