[!info] related notes 算法面试题型 MOC 栈

用栈实现队列

[!info] related notes

• 相关概念: 栈, [[queue|队列]], 单调队列

题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/

题型判断

这是典型设计题。

目标是用后进先出的栈，模拟先进先出的队列。

关键不在于“每次都立刻倒腾”，而在于：

什么时候真的需要把元素从输入栈搬到输出栈。

核心思路

维护两个栈：

• inStack：负责入队
• outStack：负责出队 / 看队头

流程：

• push(x)：直接压入 inStack
• pop() / peek()：如果 outStack 为空，就把 inStack 全部倒进去
• empty()：两个栈都为空才是真的空

为什么这样能保证 FIFO

因为：

• 新元素总是先进 inStack
• 当需要出队时，把 inStack 全部倒入 outStack
• 顺序翻转后，最早入队的元素就会跑到 outStack 栈顶

这相当于做了一次“批量反转”。

JavaScript

class MyQueue {
    constructor() {
        this.inStack = [];
        this.outStack = [];
    }

    push(x) {
        this.inStack.push(x);
    }

    move() {
        if (!this.outStack.length) {
            while (this.inStack.length) {
                this.outStack.push(this.inStack.pop());
            }
        }
    }

    pop() {
        this.move();
        return this.outStack.pop();
    }

    peek() {
        this.move();
        return this.outStack[this.outStack.length - 1];
    }

    empty() {
        return this.inStack.length === 0 && this.outStack.length === 0;
    }
}

一句话总结

不要每次操作都倒栈，只有当 outStack 空了，才把 inStack 一次性倒过去。