232. 用栈实现队列

题目链接：232. 用栈实现队列

这个题目跟 225. 用队列实现栈 思路是相似的。

思路：这个题目要用两个队列去实现一个栈。首先队列的特点是先进先出，而栈的特点是后进先出。关键的一点是用队列头去模拟栈顶。

class MyStack {
  arr: number[] = []

  push(x: number): void {
    this.arr.push(x)
  }

  pop(): number {
    return this.arr.pop()
  }

  peek(): number {
    return this.arr[this.arr.length - 1]
  }

  get size(): number {
    return this.arr.length
  }

  isEmpty(): boolean {
    return this.arr.length === 0
  }
}

class MyQueue {
  stack1 = new MyStack()
  stack2 = new MyStack()

  constructor() {}

  // 时间复杂度为 O(n)
  push(x: number): void {
    while (!this.stack1.isEmpty()) {
      this.stack2.push(this.stack1.pop()!)
    }
    this.stack2.push(x)

    while (!this.stack2.isEmpty()) {
      this.stack1.push(this.stack2.pop()!)
    }
  }

  // 时间复杂度为 O(1)
  pop(): number {
    return this.stack1.pop()
  }

  // 时间复杂度为 O(1)
  peek(): number {
    return this.stack1.peek()
  }

  // 时间复杂度为 O(1)
  empty(): boolean {
    return this.stack1.isEmpty()
  }
}

进阶：实现每个操作均摊时间复杂度为 O(1) 的队列

前面的解法 push 方法时间复杂度是 O(n)。要满足每个操作的均摊时间复杂度为 O(1)，思路是将一个栈当做输入栈，保存 push 传入的数据。另一个栈作为输出栈，用于 pop 和 peek 的操作。当 pop 或 peek 发现输出栈为空时，则将输入栈的全部数据依次弹出并压入输出栈。

class MyStack {
  arr: number[] = []

  push(x: number): void {
    this.arr.push(x)
  }

  pop(): number {
    return this.arr.pop()
  }

  peek(): number {
    return this.arr[this.arr.length - 1]
  }

  get size(): number {
    return this.arr.length
  }

  isEmpty(): boolean {
    return this.arr.length === 0
  }
}

class MyQueue {
  inStack = new MyStack()
  outStack = new MyStack()

  constructor() {}

  push(x: number): void {
    this.inStack.push(x)
  }

  inToOut() {
    if (this.outStack.isEmpty()) {
      while (!this.inStack.isEmpty()) {
        this.outStack.push(this.inStack.pop())
      }
    }
  }

  pop(): number {
    this.inToOut()
    return this.outStack.pop()
  }

  peek(): number {
    this.inToOut()
    return this.outStack.peek()
  }

  empty(): boolean {
    this.inToOut()
    return this.outStack.isEmpty()
  }
}