javascript - 具有两个堆栈的队列

Question

我实现了一个带有两个堆栈的队列，如下所示:

class QueueTwoStacks {
  constructor() {
    this.stack1 = []
    this.stack2 = []
  }
  enqueue(item) {
    this.stack1.push(item)
    const lastItem = this.stack1.pop()
    this.stack2.push(lastItem)
    const lastItem2 = this.stack2.pop()
    this.stack1.push(lastItem2)
  }

  dequeue() {
    if(this.stack1.length === 0) throw Error
    return this.stack1.shift();
  }
}

我正在学习的类(class)给出了这个答案:

class QueueTwoStacks {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }

  enqueue(item) {
    this.inStack.push(item);
  }

  dequeue() {
    if (this.outStack.length === 0) {

      // Move items from inStack to outStack, reversing order
      while (this.inStack.length > 0) {
        const newestInStackItem = this.inStack.pop();
        this.outStack.push(newestInStackItem);
      }

      // If outStack is still empty, raise an error
      if (this.outStack.length === 0) {
        throw new Error("Can't dequeue from empty queue!");
      }
    }
    return this.outStack.pop();
  }
}

其中一个比另一个更好吗？如果是，为什么？我觉得我的解决方案更好，因为您不必循环，但也许您不应该在入队方法中执行所有操作？

Answer 1

问题是您的实现每次出队的时间复杂度都是O(n)，因为您正在调用shift。另一方面，pop 是一个 O(1) 操作。更多详情，您可以查看this question 。

请注意，在您的实现中，您几乎可以完全摆脱 stack2 并且它仍然可以工作(当然，具有相同的缺点，即您将拥有 O(n) 出队):

class QueueTwoStacks {
  constructor() {
    this.stack1 = []
    // this.stack2 = []
  }
  enqueue(item) {
    this.stack1.push(item)
    // const lastItem = this.stack1.pop()
    // this.stack2.push(lastItem)
    // const lastItem2 = this.stack2.pop()
    // this.stack1.push(lastItem2)
  }

  dequeue() {
    if(this.stack1.length === 0) throw Error
    return this.stack1.shift();
  }
}

但是，第二种实现只是偶尔将元素移动到 outStack(即仅当它为空时)，并使用 pop 进行出列 > 操作。因此，虽然最坏情况仍然是 O(n)，但在平均情况下，此实现中的 dequeue 应该是 O(1)，这比 O(n) 要好得多，特别是如果您将多次调用它。