0232.用栈实现队列

难度：🟢 简单

标签：栈、设计、队列

链接：232. 用栈实现队列

题目描述

请你仅使用两个栈实现一个先入先出（FIFO）队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾

• int pop() 从队列的开头移除并返回元素

• int peek() 返回队列开头的元素

• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

解题思路

核心思想

本题的挑战在于，栈是“后进先出”（LIFO）的数据结构，而队列是“先进先出”（FIFO）的。核心思想是通过一个或多个栈的操作来模拟出 FIFO 的效果。关键在于如何通过 LIFO 的操作，将最早进入的元素移动到可以被访问的位置（栈顶）。

思路选择

代码中采用的是 “单主栈+临时栈” 的思路。

• 一个主栈 stack 用于存储所有新加入的元素。

• 当需要 pop 或 peek 操作时，需要访问队首元素（即最早进入的元素）。此时，通过一个临时的辅助栈 tempStack 来进行一次“乾坤大挪移”：

  1. 将主栈 stack 的所有元素依次弹出并压入 tempStack。这个过程完成后，元素的顺序被完全反转，最早进入的元素现在位于 tempStack 的栈顶。

  2. 对 tempStack 的栈顶执行 pop (出队) 或 peek (查看队首) 操作。

  3. 再将 tempStack 的所有元素导回主栈 stack，以恢复原始的存储顺序，为下一次 push 做准备。

关键步骤

1. push(x): 直接将元素 x 压入主栈 stack。

2. pop(): a. 创建一个空的临时栈 tempStack。 b. 将 stack 的所有元素逐个 pop 并 push 到 tempStack 中。 c. 从 tempStack 弹出一个元素，这是队首元素，作为返回值。 d. 将 tempStack 的所有元素再导回 stack。 e. 返回结果。

3. peek(): 逻辑与 pop() 几乎完全相同，唯一的区别在于，在第 c 步中，只是查看 tempStack 的栈顶元素而不弹出，或者弹出后再立即压回。当前代码实现逻辑是弹出后，在导回的过程中将所有元素都放回主栈。

4. empty(): 判断主栈 stack 的长度是否为 0 即可。

代码实现

var MyQueue = function () {
    this.stack = [];
};

/** * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
    this.stack.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function () {
    let tempStack = [];
    while (this.stack.length !== 0) {
        tempStack.push(this.stack.pop());
    }
    let result = tempStack.pop();
    while (tempStack.length !== 0) {
        this.stack.push(tempStack.pop());
    }

    return result;
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
    let tempStack = [];
    while (this.stack.length !== 0) {
        tempStack.push(this.stack.pop());
    }
    let result = tempStack[tempStack.length - 1]; // 查看栈顶元素
    while (tempStack.length !== 0) {
        this.stack.push(tempStack.pop());
    }

    return result;
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
    return this.stack.length === 0;
};

复杂度分析

• 时间复杂度：push 和 empty 操作为 O(1)。pop 和 peek 操作在最坏情况下需要将所有元素移动两次，因此时间复杂度为 O(n)，其中 n 是队列中的元素数量。

• 空间复杂度：O(n)，pop 和 peek 操作中，临时栈 tempStack 最多需要存储 n 个元素。

相关题目

• 0225.用队列实现栈

总结

本题是考察利用基础数据结构组合实现新数据结构的经典设计题。当前解法思路清晰，但 pop 和 peek 的效率较低。更优化的方法是使用两个栈（一个输入栈 inStack，一个输出栈 outStack），push 时压入 inStack，pop/peek 时，如果 outStack 为空，则将 inStack 的所有元素一次性倒入 outStack，然后对 outStack 操作。这样可以使得 pop/peek 的均摊时间复杂度降为 O(1)。