232. 用栈实现队列

LeetCode 原题链接

题目描述

只使用栈的标准操作实现先进先出队列，支持 push、pop、peek 和 empty。

题型判断

单个栈只能后进先出。把元素从一个栈倒入另一个栈会反转顺序，因此可以用两个栈组合出先进先出效果。

核心思路

  • inputStack：所有新元素都压入这里。
  • outputStack：队头位于栈顶，从这里读取或弹出。
  • 只有 outputStack 为空时，才把 inputStack 全部倒入其中。
依次写入 1, 2, 3：
inputStack  = [1, 2, 3]

倒入输出栈：
outputStack = [3, 2, 1]  ← 栈顶是最早写入的 1

不能每次读取都来回倒栈。输出栈非空时继续使用它，才能保证均摊 O(1)。

代码实现

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

MyQueue.prototype.moveIfNeeded = function () {
  if (this.outputStack.length > 0) return;

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

MyQueue.prototype.push = function (x) {
  this.inputStack.push(x);
};

MyQueue.prototype.pop = function () {
  this.moveIfNeeded();
  return this.outputStack.pop();
};

MyQueue.prototype.peek = function () {
  this.moveIfNeeded();
  return this.outputStack[this.outputStack.length - 1];
};

MyQueue.prototype.empty = function () {
  return this.inputStack.length === 0 && this.outputStack.length === 0;
};

复杂度与易错点

  • push：O(1)。
  • pop、peek：均摊 O(1)；单次最坏 O(n)。
  • 空间复杂度：O(n)。
  • 每个元素最多进入、离开两个栈各一次，因此一组操作的总搬运成本是线性的。
  • 判断队列为空时必须同时检查两个栈。