Queue with Two Stacks

Question

I implemented a queue with two stacks like so:

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();
  }
}

The course I'm following gave this as an answer:

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();
  }
}

Is one better than the other, and if so, why? I feel like my solution is better because you don't have to loop, but maybe you're not supposed to do all the operation in the enqueue method?

slider · Accepted Answer · 2018-10-07T03:18:39.107

The problem is that your implementation has O(n) time complexity for dequeue EVERY time, because you're calling shift. On the other hand, pop is an O(1) operation. For more details, you can check out this question.

Notice that in your implementation, you can pretty much get rid of stack2 altogether and it'll still work (of course, with the same drawback that you'll have 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();
  }
}

The second implementation, however, only occasionally moves elements to the outStack (i.e. only when it is empty) and uses pop for its dequeue operation. So, while worst case is still O(n), in the average case, dequeue in this implementation should be O(1), which is considerably better than O(n), especially if you're going to be calling it many times.

Queue with Two Stacks

1 Answers1