232.用栈实现队列

题目

LeetCode 简单

题目

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

实现 MyQueue 类：

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

说明：
你 只能 使用标准的栈操作 —— 也就是只有  push to top, peek/pop from top, size, 和  is empty  操作是合法的。

题解

方法：双栈 O(1)

栈 双栈 均摊 O(1) O(n)

两个栈可以同时有值：

• push 时，入到 inStack
• pop 和 peek 时
  • 如果 outStack 不为空，直接从 outStack 取值
  • 如果 outStack 为空，把 inStack 倒到 outStack，再取值

class MyQueue {
  private inStack: number[] = []
  private outStack: number[] = []

  push(x: number): void {
    this.inStack.push(x)
    console.log('stacks', this.inStack, this.outStack)
  }

  pop(): number {
    if (!this.outStack.length) {
      this._in2out()
    }
    console.log(this.inStack, this.outStack)

    return this.outStack.pop()
  }

  peek(): number {
    if (!this.outStack.length) {
      this._in2out()
    }
    console.log('stacks', this.inStack, this.outStack)
    return this.outStack[this.outStack.length - 1]
  }

  private _in2out(): void {
    const inStack = this.inStack
    const outStack = this.outStack
    while (inStack.length) {
      outStack.push(inStack.pop())
    }
  }

  empty(): boolean {
    return this.inStack.length === 0 && this.outStack.length === 0
  }
}

const q = new MyQueue()
console.log(q.push(1)) // queue is: [1]
console.log(q.push(2)) // queue is: [1, 2] (leftmost is front of the queue)
console.log(q.peek()) // return 1
console.log(q.pop()) // return 1, queue is [2]
console.log(q.push(3)) // queue is: [2,3]
console.log(q.push(4)) // queue is: [2,3,4]
console.log(q.push(5)) // queue is: [2,3,4,5]
console.log(q.pop()) // return 2, queue is [3,4,5]
console.log(q.empty()) // return false
console.log(q)

方法：双栈 O(n)

栈 双栈 O(n) O(n)

只有 inStack 栈一直有值：

• push 时，入到 inStack
• pop 和 peek 时，从 inStack 倒到 outStack，取完值，再从 outStack 倒回 inStack

class MyQueue2 {
  private inStack: number[] = []
  private outStack: number[] = []

  push(x: number): void {
    this.inStack.push(x)
    console.log('stacks', this.inStack, this.outStack)
  }

  pop(): number {
    return this._getTop(true)
  }

  peek(): number {
    return this._getTop(false)
  }

  private _getTop(needDelete: boolean): number {
    const inStack = this.inStack
    const outStack = this.outStack
    //入栈放到出栈
    while (inStack.length) {
      outStack.push(inStack.pop())
    }
    const res = outStack.pop()
    if (!needDelete) {
      inStack.push(res)
    }
    //出栈放回入栈
    while (outStack.length) {
      inStack.push(outStack.pop())
    }
    console.log('stacks', this.inStack, this.outStack)
    return res
  }

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

const q2 = new MyQueue2()
console.log(q2.push(1)) // queue is: [1]
console.log(q2.push(2)) // queue is: [1, 2] (leftmost is front of the queue)
console.log(q2.peek()) // return 1
console.log(q2.pop()) // return 1, queue is [2]
console.log(q2.push(3)) // queue is: [2,3]
console.log(q2.push(4)) // queue is: [2,3,4]
console.log(q2.push(5)) // queue is: [2,3,4,5]
console.log(q2.pop()) // return 2, queue is [3,4,5]
console.log(q2.empty()) // return false
console.log(q)