用栈实现队列

发表于 更新于 分类于

算法-用栈实现队列

背景

  • 算法–用栈实现队列

  • 博主以代码随想录算法公开课进行学习

题目

  • 使用栈实现队列的下列操作：

    push(x) – 将一个元素放入队列的尾部。
    pop() – 从队列首部移除元素。
    peek() – 返回队列首部的元素。
    empty() – 返回队列是否为空。

    示例:

    1
    2
    3
    4
    5
    6
    MyQueue queue = new MyQueue();
    queue.push(1);
    queue.push(2);
    queue.peek();  // 返回 1
    queue.pop();   // 返回 1
    queue.empty(); // 返回 false

    说明:

    • 你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
    • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
    • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

思路

  • 核心矛盾：栈是「后进先出（LIFO）」，队列是「先进先出（FIFO）」，单个栈无法实现队列，需用两个栈（输入栈 + 输出栈） 配合；

  • 输入栈（stackIn）：专门处理 push 操作，所有新元素先压入输入栈；

  • 输出栈（stackOut）：专门处理 pop/peek 操作，当输出栈为空时，将输入栈的所有元素「倒序」压入输出栈（此时输出栈的栈顶就是队列的队首）；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class MyQueue {
    // 输入栈：仅用于push操作，存储待倒序的元素
    Stack<Integer> stackIn;
    // 输出栈：仅用于pop/peek操作，存储已倒序的元素（栈顶=队首）
    Stack<Integer> stackOut;
    // 初始化两个栈
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    // 入队：直接压入输入栈
    public void push(int x) {
        stackIn.push(x);
    }
    // 出队：先倒腾元素到输出栈，再弹出输出栈栈顶
    public int pop() {
        // 核心：输出栈为空时，才将输入栈元素倒压入输出栈
        dumpstackIn();
        return stackOut.pop();
    }
    // 查看队首：逻辑同pop，仅不弹出元素
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }
    // 判断队列是否为空：两个栈都为空时，队列才为空
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
    //将输入栈元素倒压入输出栈（仅当输出栈为空时执行）
    private void dumpstackIn(){
        // 输出栈非空时，直接返回
        if(!stackOut.isEmpty()){
            return;
        }
        // 输入栈元素依次弹出，压入输出栈
        while(!stackIn.isEmpty()){
            stackOut.push(stackIn.pop());
        }
    }
}

总结

  • 面试中需掌握「双栈→队列」和「双队列→栈」的双向转换思路，以及时间复杂度分析。
  • 面试可能考点：
    • 为什么需要两个栈？
      • 核心原因：栈是「后进先出（LIFO）」，队列是「先进先出（FIFO）」，单个栈无法扭转元素的顺序。
      • 简单说：一个栈负责「进」，一个栈负责「出」，两个栈配合完成「先进先出」的转换。
    • 倒腾元素的时机？（核心优化点）
      • 倒腾时机：仅当输出栈为空时，才把输入栈的所有元素倒腾到输出栈（「懒加载」策略）。
    • 拓展问题：如何用队列实现栈？（反向思路）
      • 栈是「后进先出」，队列是「先进先出」，核心思路：用两个队列，每次入队后倒腾 n-1 个元素，让「最后入队的元素」留在队列头（模拟栈顶）。