Why does this queue built from two stacks return items in the wrong order after alternating operations?

programming web dev
1

I’m implementing a queue using two stacks, but mixed enqueue/dequeue calls produce unexpected order. I expected FIFO for every sequence.

class Queue {
  constructor() { this.a = []; this.b = []; }
  enqueue(x) { this.a.push(x); }
  dequeue() {
    if (!this.b.length) this.b = this.a;
    this.a = [];
    return this.b.pop();
  }
}

For enqueue(1), enqueue(2), dequeue(), enqueue(3), dequeue(), dequeue() I get 2, 3, 1 instead of 1, 2, 3. What invariant am I breaking, and what’s the minimal fix?

Arthur :grinning_face:

2

You must move items from a to b in reverse order one by one, because this.b = this.a keeps the same stack order and the first dequeue returning 2 is the debugging sign.

BobaMilk