225. 用队列实现栈

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

分析：

1. 队列特点是先进先出，而栈的特点是后进先出
2. 栈顶通过队列前端来模拟。

使用两个队列来实现栈

这种方式的思路是以一个队列用做存储所有栈元素的数据结构。以另外一个队列作为临时队列，确保新入栈的元素可以放在队首。

// 封装数组，实现一个标准的队列操作
class MyQueue {
  arr = []
  enqueue(x: number) {
    this.arr.push(x)
  }
  dequeue(): number {
    return this.arr.shift()
  }
  peek(): number {
    return this.arr[0]
  }
  isEmpty(): boolean {
    return this.arr.length === 0
  }
}

class MyStack {
  queue1 = new MyQueue()
  queue2 = new MyQueue()

  constructor() {}

  /** 时间复杂度是 O(n) */
  push(x: number): void {
    this.queue2.enqueue(x)
    while (!this.queue1.isEmpty()) {
      this.queue2.enqueue(this.queue1.dequeue())
    }
    const tmp = this.queue1
    this.queue1 = this.queue2
    this.queue2 = tmp
  }

  /** 时间复杂度是 O(1) */
  pop(): number {
    return this.queue1.dequeue()
  }

  /** 时间复杂度是 O(1) */
  top(): number {
    return this.queue1.peek()
  }

  /** 时间复杂度是 O(1) */
  empty(): boolean {
    return this.queue1.isEmpty()
  }
}

进阶：使用一个队列来实现栈

观察前面使用两个队列来实现栈的主要逻辑，其实是在 push 这个方法中。这个方法主要的操作，就是将入栈的 x 放到队列的头部。这个过程其实我们也可以用一个队列来完成，新入栈的元素 x 正常入列，随后将原来队列中的所有元素出列再入列，这样就确保了最新入栈的元素在队列的首位了。

class MyQueue {
  arr = []
  enqueue(x: number) {
    this.arr.push(x)
  }
  dequeue(): number {
    return this.arr.shift()
  }
  peek(): number {
    return this.arr[0]
  }
  isEmpty(): boolean {
    return this.arr.length === 0
  }
  get size(): number {
    return this.arr.length
  }
}

class MyStack {
  queue = new MyQueue()

  push(x: number): void {
    const size = this.queue.size
    this.queue.enqueue(x)
    for (let i = 0; i < size; i++) {
      const e = this.queue.dequeue()
      this.queue.enqueue(e)
    }
  }

  pop(): number {
    return this.queue.dequeue()
  }

  top(): number {
    return this.queue.peek()
  }

  empty(): boolean {
    return this.queue.isEmpty()
  }
}