用队列实现栈

问题

使用队列实现栈的以下操作：

• push(x) - 元素入栈
• pop() - 移除栈顶元素并返回
• top() - 获取栈顶元素
• isEmpty() - 判断栈是否为空

解答

方法一：单队列实现

每次 push 时，将新元素加入队列后，把它前面的所有元素依次出队再入队，使新元素排到队首。

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

  // 入栈：将新元素移到队首
  push(x) {
    this.queue.push(x);
    // 把新元素前面的所有元素移到后面
    let size = this.queue.length;
    while (size > 1) {
      this.queue.push(this.queue.shift());
      size--;
    }
  }

  // 出栈：直接取队首
  pop() {
    return this.queue.shift();
  }

  // 查看栈顶
  top() {
    return this.queue[0];
  }

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

// 测试
const stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.top());   // 3
console.log(stack.pop());   // 3
console.log(stack.pop());   // 2
console.log(stack.isEmpty()); // false

方法二：双队列实现

使用两个队列，一个主队列存数据，一个辅助队列用于 pop 操作。

class MyStack {
  constructor() {
    this.queue1 = []; // 主队列
    this.queue2 = []; // 辅助队列
  }

  push(x) {
    this.queue1.push(x);
  }

  pop() {
    // 把 queue1 的元素（除最后一个）移到 queue2
    while (this.queue1.length > 1) {
      this.queue2.push(this.queue1.shift());
    }
    // 取出最后一个元素（栈顶）
    const top = this.queue1.shift();
    // 交换两个队列
    [this.queue1, this.queue2] = [this.queue2, this.queue1];
    return top;
  }

  top() {
    while (this.queue1.length > 1) {
      this.queue2.push(this.queue1.shift());
    }
    const top = this.queue1.shift();
    this.queue2.push(top); // top 也要放回去
    [this.queue1, this.queue2] = [this.queue2, this.queue1];
    return top;
  }

  isEmpty() {
    return this.queue1.length === 0;
  }
}

复杂度对比

方法	push	pop	top
单队列	O(n)	O(1)	O(1)
双队列	O(1)	O(n)	O(n)

关键点

• 栈是 LIFO（后进先出），队列是 FIFO（先进先出）
• 单队列方案：push 时调整顺序，使新元素在队首
• 双队列方案：pop 时将元素倒腾到辅助队列，取最后一个
• 单队列方案更简洁，push 慢但 pop 快
• JavaScript 数组的 shift() 和 push() 可模拟队列操作