具有两个堆栈的队列

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 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( 的时间复杂度dequeue，因为你调用的是shift.另一方面，pop是 O(1( 操作。有关更多详细信息，您可以查看此问题。

请注意，在您的实现中，您几乎可以完全摆脱stack2并且它仍然可以工作(当然，具有与O(n(dequeue相同的缺点(：

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进行dequeue操作。因此，虽然最坏的情况仍然是 O(n(，但在平均情况下，此实现中的dequeue应该是 O(1(，这比 O(n( 好得多，特别是如果您要多次调用它。