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

用队列实现栈

题目链接：https://leetcode.cn/problems/implement-stack-using-queues/

题型判断

这题和“用栈实现队列”相反，是用先进先出的队列去模拟后进先出的栈。

核心是：

如何让最新放进去的元素，始终最先被取出来。

核心思路

用一个队列即可。

每次 push(x) 时：

• 先把 x 入队
• 再把之前已有的元素依次出队后重新入队

这样做完后，最新元素就被转到了队首。

于是：

• pop()：直接出队
• top()：直接看队首

为什么可行

因为我们在 push 阶段主动重排顺序，让队首始终对应“栈顶”。

这题的难点不是代码，而是接受：

• 栈的顺序可以在入栈时维护
• 不一定非要在出栈时处理

JavaScript

class MyStack {
    constructor() {
        this.queue = [];
    }

    push(x) {
        this.queue.push(x);

        let size = this.queue.length - 1;
        while (size > 0) {
            this.queue.push(this.queue.shift());
            size--;
        }
    }

    pop() {
        return this.queue.shift();
    }

    top() {
        return this.queue[0];
    }

    empty() {
        return this.queue.length === 0;
    }
}

一句话总结

每次新元素入队后，把旧元素轮转到后面，就能让“最新元素”稳定占据队首。