zhangdizhangdi

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，再取值
js
class MyQueue {
  private inStack= []
  private outStack= []

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

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

    return this.outStack.pop()
  }

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

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

  empty() {
    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
js
class MyQueue {
  private inStack= []
  private outStack = []

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

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

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

  private _getTop(needDelete) {
    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() {
    return this.inStack.length === 0
  }
}

const q2 = new MyQueue()
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)