跳到主要内容

用队列实现栈

为什么一个队列不足以模拟栈？​

  • 队列: 队尾入队, 队首出队;
  • 栈: 同一端入栈出栈, 后进先出;
  • 冲突: 最新入队的元素停在队尾, 而栈要求最先弹出它;
  • 结论: 需要额外的队列把最新元素搬到队首;

如何用两个队列让队首始终是最新元素？​

  • 维护 in 和 out 两个队列;
  • 压栈: 新元素先入 in, 再把 out 中已有元素依次搬到 in;
  • 交换: 交换 in 与 out, 此后 out 的队首就是最新入栈的元素;
  • 弹栈: 对 out 出队, 即弹出栈顶;
  • 取栈顶: 读取 out 的队首;
  • 判空: 判断 out 是否为空;
class MyStack {
  private inQueue: number[] = [];
  private outQueue: number[] = [];

  push(x: number): void {
    this.inQueue.push(x);
    while (this.outQueue.length > 0) this.inQueue.push(this.outQueue.shift()!);
    [this.outQueue, this.inQueue] = [this.inQueue, this.outQueue];
  }

  pop(): number | undefined {
    return this.outQueue.shift();
  }

  top(): number | undefined {
    return this.outQueue[0];
  }

  empty(): boolean {
    return this.outQueue.length === 0;
  }
}

这种实现的复杂度是多少？​

  • 压栈: O(n), 每次都要搬运当前全部元素;
  • 弹栈、取栈顶、判空: O(1);
  • 空间: O(n), n 为栈内元素数;