双栈实现队列

题目介绍

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

解题思路

栈有个特点就是进栈出栈一轮顺序会相反，两轮则顺序会恢复正常。

因此可以采用两个栈stackIn和stackOut，push时候直接将值推进stackIn即可，pop时候如果stackOut还有值则直接弹出，没有值则先将stackIn的值全部推进来再弹出。

代码

class MyQueue {
  stackIn: number[] = []; // 存储值
  stackOut: number[] = []; // 实际推出值
  constructor() {
    this.stackIn = [];
    this.stackOut = [];
  }
  // 推进值
  push(x: number): void {
    this.stackIn.push(x);
  }
  // 弹出值
  pop(): number {
    // 有值直接pop
    if (this.stackOut.length > 0) {
      return this.stackOut.pop()!;
    }
    // 没有值将stackIn的值push进来在pop
    while (this.stackIn.length > 0) {
      this.stackOut.push(this.stackIn.pop()!);
    }
    return this.stackOut.pop()!;
  }
  // 获取队首
  peek(): number {
    const x = this.pop();
    this.stackOut.push(x);
    return x;
  }
  // 是否为空
  empty(): boolean {
    return this.stackIn.length === 0 && this.stackOut.length === 0;
  }
}