LeetCode 面试题 03.04. 化栈为队

约 5 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 程序员面试金典（第 6 版） 拼多多
标签
栈 设计 队列

题目描述

✅ 面试题 03.04. 化栈为队

image-20260929105710366

题意分析

只使用两个栈的压栈、弹栈、查看栈顶和判空等操作，实现先进先出的队列。难点是新元素位于栈顶，而队列需要先取出最早加入的元素；可以借另一个栈反转顺序。

解法：双栈延迟倒序

核心思路

[!blue]
入口栈 stk1 接收新元素，出口栈 stk2 保存等待出队的旧元素。 队列顺序始终是“出口栈从顶到底，再接入口栈从底到顶”：出口栈顶是最早的元素，入口栈顶是最新的元素。push 只向入口栈追加，不干扰出口栈已有的队首。

pop 或 peek 需要队首时，若出口栈非空，直接使用它的栈顶；若出口栈为空，才把入口元素逐个弹出并压入出口。入口中最新的元素先进入出口底部，最早的元素最后进入出口顶部，于是整批元素恢复为先进先出的出队顺序。必须整批倒完，不能只搬一个元素。

出口栈仍有旧元素时不能搬入新元素，否则新元素会覆盖旧队首。等这批旧元素全部出队后，再反转后加入的一批，批次之间与批次内部的先后次序都能保持。两个栈只要有一个非空，队列就还有元素，所以判空要使用“且”。

每个元素最多压入入口一次、从入口搬到出口一次、再从出口弹出一次，不会反复倒回。一次搬运虽然可能处理很多元素，但所有操作的总搬运量与入队元素数成正比，因此出队和查看队首的均摊时间为常数。

解题步骤

  1. push 将新元素压入入口栈。
  2. pop 和 peek 共用 move：出口为空时，把入口元素全部逐个搬入出口，否则保持不动。
  3. pop 删除并返回出口栈顶，peek 只读取栈顶，不改变队列内容。
  4. empty 检查两个栈是否同时为空。题目保证操作有效，因此 pop、peek 调用时队列中一定有元素。

代码实现

class MyQueue {
    private Deque<Integer> stk1 = new ArrayDeque<>();
    private Deque<Integer> stk2 = new ArrayDeque<>();

    public MyQueue() {}

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

    public int pop() {
        move();

        return stk2.pop();
    }

    public int peek() {
        move();

        return stk2.peek();
    }

    public boolean empty() {
        // 队列元素可能位于任一栈，两侧都空才算整体为空。
        return stk1.isEmpty() && stk2.isEmpty();
    }

    private void move() {
        // 只有出口为空才倒入入口，避免新元素盖住旧队首。
        if (stk2.isEmpty()) {
            while (!stk1.isEmpty()) {
                stk2.push(stk1.pop());
            }
        }
    }
}

type MyQueue struct {
    stk1 []int
    stk2 []int
}

func Constructor() MyQueue {
    return MyQueue{
        []int{},
        []int{},
    }
}

func (this *MyQueue) Push(x int) {
    this.stk1 = append(this.stk1, x)
}

func (this *MyQueue) Pop() int {
    this.move()
    answer := this.stk2[len(this.stk2)-1]
    this.stk2 = this.stk2[:len(this.stk2)-1]
    return answer
}

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

func (this *MyQueue) Empty() bool {
    // 队列元素可能位于任一栈，两侧都空才算整体为空。
    return len(this.stk1) == 0 && len(this.stk2) == 0
}

func (this *MyQueue) move() {
    // 只有出口为空才倒入入口，避免新元素盖住旧队首。
    if len(this.stk2) == 0 {
        for len(this.stk1) > 0 {
            this.stk2 = append(this.stk2, this.stk1[len(this.stk1)-1])
            this.stk1 = this.stk1[:len(this.stk1)-1]
        }
    }
}

复杂度分析

  • 时间复杂度：push、pop、peek 均摊 $O(1)$；触发搬运的单次 pop 或 peek 最坏 $O(n)$，empty 为 $O(1)$。
  • 空间复杂度：$O(H+1)$，H 为历史最大队列规模，两个容器可能保留已经分配的容量。

关键点总结

[!green]

  • 搬运条件是出口为空，不是入口非空。
  • 每个元素只向出口移动一次，不反复倒回。
  • 整体判空必须覆盖两个容器。

易错点总结

[!yellow]

  • 出口非空仍倒入入口：新元素盖住未出队的旧元素。
  • peek 不执行必要搬运：只有入队操作时出口可能为空。
  • 判空使用或条件：一个栈空不代表整个队列空。
  • 整体追加入口内容而不逐个弹栈：顺序没有被反转。

相似题目

题目 难度 关联与区别
225. 用队列实现栈 简单 原题反过来用队列实现栈，本题利用两次倒序恢复FIFO。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/56030565
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！