Implement Queue using Stacks（用栈实现队列）

题目 / Problem

中文： 仅使用两个栈实现一个先进先出（FIFO）队列。实现的队列需要支持普通队列的所有操作：push、peek、pop 和 empty。

实现 MyQueue 类：
Implement the MyQueue class:

• void push(int x)：将元素 x 添加到队列末尾。
  Pushes element x to the back of the queue.
• int pop()：移除并返回队首元素。
  Removes the element from the front of the queue and returns it.
• int peek()：返回队首元素，但不移除它。
  Returns the element at the front of the queue without removing it.
• boolean empty()：如果队列为空，返回 true；否则返回 false。
  Returns true if the queue is empty and false otherwise.

English: Implement a first-in, first-out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue: push, peek, pop, and empty.

限制说明 / Notes

• 只能使用栈的标准操作：向栈顶添加元素、查看或移除栈顶元素、获取栈的大小以及判断栈是否为空。
  You may use only standard stack operations: push to the top, peek or pop from the top, size, and empty checks.
• 如果语言没有原生栈，可以使用列表或双端队列模拟，但只能使用栈操作。
  If the language has no native stack, a list or deque may simulate one as long as only standard stack operations are used.
• JavaScript 数组的 push() 和 pop() 可以模拟栈；本题不应使用 shift()。
  JavaScript arrays can simulate stacks with push() and pop(); shift() should not be used here.

示例 / Example

Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output:
[null, null, null, 1, 1, false]

const myQueue = new MyQueue();
myQueue.push(1); // 队列 / Queue: [1]
myQueue.push(2); // 队列 / Queue: [1, 2]，最左侧是队首 / Leftmost is front
myQueue.peek();  // 返回 / Return: 1
myQueue.pop();   // 返回 / Return: 1；队列 / Queue: [2]
myQueue.empty(); // 返回 / Return: false

约束 / Constraints

• 1 <= x <= 9
• 最多调用 push、pop、peek 和 empty 共 100 次。
  At most 100 calls will be made to push, pop, peek, and empty.
• 所有对 pop 和 peek 的调用都是有效的。
  All calls to pop and peek are valid.

进阶 / Follow-up

能否让每个操作的均摊时间复杂度为 O(1)？也就是说，即使某一次操作耗时较长，执行 n 次操作的总时间仍为 O(n)。
Can you implement the queue so that each operation has amortized O(1) time? In other words, even if one operation takes longer, n operations should take O(n) total time.

解题思路：两个栈与延迟搬运 / Approach: Two Stacks with Lazy Transfer

使用两个栈承担不同职责：
Use two stacks with separate responsibilities:

• inputStack：保存新加入的元素，栈顶对应队尾。
  inputStack stores newly pushed elements; its top represents the back of the queue.
• outputStack：保存等待出队的元素，栈顶对应队首。
  outputStack stores elements ready to leave; its top represents the front of the queue.

push(x)

直接将 x 压入 inputStack。
Push x directly onto inputStack.

pop() 和 peek()

1. 如果 outputStack 不为空，直接读取它的栈顶。
   If outputStack is non-empty, use its top directly.
2. 如果 outputStack 为空，将 inputStack 中的元素逐个弹出并压入 outputStack。
   If outputStack is empty, pop every element from inputStack and push it onto outputStack.
3. 搬运过程将元素顺序反转，使最早进入队列的元素出现在 outputStack 栈顶。
   The transfer reverses the order, placing the earliest enqueued element on top of outputStack.

只有当 outputStack 为空时才进行搬运。这样可以避免每次操作都来回移动元素。
Transfer elements only when outputStack is empty. This avoids moving elements back and forth on every operation.

empty()

只有当两个栈都为空时，队列才为空。
The queue is empty only when both stacks are empty.

JavaScript 实现 / JavaScript Implementation

class MyQueue {
  constructor() {
    this.inputStack = [];
    this.outputStack = [];
  }

  /**
   * @param {number} x
   * @return {void}
   */
  push(x) {
    this.inputStack.push(x);
  }

  /**
   * @return {number}
   */
  pop() {
    this.moveToOutput();
    return this.outputStack.pop();
  }

  /**
   * @return {number}
   */
  peek() {
    this.moveToOutput();
    return this.outputStack[this.outputStack.length - 1];
  }

  /**
   * @return {boolean}
   */
  empty() {
    return this.inputStack.length === 0 && this.outputStack.length === 0;
  }

  moveToOutput() {
    if (this.outputStack.length > 0) {
      return;
    }

    while (this.inputStack.length > 0) {
      this.outputStack.push(this.inputStack.pop());
    }
  }
}

执行过程 / Walkthrough

执行示例中的操作：
Execute the operations from the example:

搬运后，outputStack 的栈顶是最早入队的元素 1，所以 peek() 和 pop() 都能按照 FIFO 顺序工作。
After the transfer, the top of outputStack is 1, the earliest enqueued element, so peek() and pop() follow FIFO order.

为什么是均摊 O(1)？ / Why Is It Amortized O(1)?

单次 pop() 或 peek() 在触发搬运时可能需要 O(n) 时间，但每个元素最多经历：
A single pop() or peek() may take O(n) when it triggers a transfer, but each element is moved at most as follows:

1. 被压入 inputStack 一次。
   Pushed onto inputStack once.
2. 从 inputStack 弹出并压入 outputStack 一次。
   Popped from inputStack and pushed onto outputStack once.
3. 最终从 outputStack 弹出一次。
   Finally popped from outputStack once.

每个元素参与的栈操作次数是常数，因此执行 n 次队列操作的总时间为 O(n)，每次操作的均摊时间为 O(1)。
Each element participates in only a constant number of stack operations, so n queue operations take O(n) total time and O(1) amortized time per operation.

复杂度 / Complexity

• 空间复杂度：O(n)，两个栈合计保存队列中的 n 个元素。
  Space: O(n), because the two stacks together hold the queue's n elements.

易错点 / Common Pitfalls

• 只有在 outputStack 为空时才能搬运，否则会破坏已有元素的出队顺序。
  Transfer only when outputStack is empty; otherwise the existing dequeue order will be corrupted.
• empty() 必须同时检查两个栈。
  empty() must check both stacks.
• peek() 只读取 outputStack 的栈顶，不能移除元素。
  peek() reads the top of outputStack without removing it.
• 不要使用数组的 shift()，它是队列操作，不属于允许使用的栈操作。
  Do not use the array method shift(); it is a queue operation, not an allowed stack operation.
• 单次搬运可能是 O(n)，但题目要求的是均摊 O(1)，不是每次操作严格为 O(1)。
  A single transfer may take O(n), but the requirement is amortized O(1), not strict O(1) for every individual operation.