用栈实现队列

问题

使用栈实现队列的 push、pop、peek 和 empty 操作。

栈是后进先出（LIFO），队列是先进先出（FIFO），如何用栈模拟队列？

解答

使用两个栈：一个负责入队，一个负责出队。

class MyQueue {
  constructor() {
    this.inStack = [];  // 入队栈
    this.outStack = []; // 出队栈
  }

  // 入队：直接放入 inStack
  push(x) {
    this.inStack.push(x);
  }

  // 出队：从 outStack 取，为空时先把 inStack 倒过来
  pop() {
    this._transfer();
    return this.outStack.pop();
  }

  // 查看队首元素
  peek() {
    this._transfer();
    return this.outStack[this.outStack.length - 1];
  }

  // 判断是否为空
  empty() {
    return this.inStack.length === 0 && this.outStack.length === 0;
  }

  // 把 inStack 的元素倒入 outStack
  _transfer() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
  }
}

使用示例

const queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.push(3);

console.log(queue.peek()); // 1
console.log(queue.pop());  // 1
console.log(queue.pop());  // 2

queue.push(4);

console.log(queue.pop());  // 3
console.log(queue.pop());  // 4
console.log(queue.empty()); // true

原理图解

入队 1, 2, 3:
inStack: [1, 2, 3]  (3在栈顶)
outStack: []

出队时，先 transfer:
inStack: []
outStack: [3, 2, 1]  (1在栈顶，最先出)

pop() 返回 1，符合队列 FIFO

关键点

• 两个栈配合：inStack 负责入队，outStack 负责出队
• 延迟转移：只有 outStack 为空时才把 inStack 倒过来
• 倒一次顺序就反过来了，正好把 LIFO 变成 FIFO
• 均摊时间复杂度：每个元素最多入栈出栈各两次，均摊 O(1)
• 空间复杂度：O(n)，两个栈共存储 n 个元素