双队列实现栈

题目介绍

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

实现思路

队列有个特点就是入队出队不会影响顺序，比如1 2 3无论经历多少次入队出队，最终出队结果依然是 1 2 3。

因此可以采用两个队列，每次将值都push进主队列，待需要pop时候，将主队列的值转移到从队列中直到剩一个，弹出这个值就是需要的栈顶。如果主队列没有值，则交换主从队列的值。

代码

class MyStack {
  /** 主队列 */
  queue1: number[];
  /** 备份队列 */
  queue2: number[];
  constructor() {
    this.queue1 = [];
    this.queue2 = [];
  }
  // 添加值
  push(x: number): void {
    // 有值直接推送到主队列 下次pop所有值都会备份到备份队列
    this.queue1.push(x);
  }
  // 弹出值
  pop(): number {
    // 如果主队列没值 说明都在备份队列中 直接交换两者的值
    if (this.queue1.length === 0) {
      [this.queue1, this.queue2] = [this.queue2, this.queue1];
    }
    // 备份值直到最后一个
    while (this.queue1.length > 1) {
      this.queue2.push(this.queue1.shift()!);
    }
    // 返回剩下的元素
    return this.queue1.shift()!;
  }
  // 获取栈顶
  top(): number {
    const x = this.pop();
    this.queue1.push(x);
    return x;
  }
  // 是否为空
  empty(): boolean {
    return this.queue1.length === 0 && this.queue2.length === 0;
  }
}