Queue from two stacks

Medium TimeO(1) amortised SpaceO(n)

A stack hands back whatever arrived most recently; a queue hands back whatever arrived first. Build the second using only the first — the only operations available are stack push and pop. Values have to be served in the order they arrived however the pushes and pops are interleaved, and the cost may be uneven between calls as long as it is constant averaged over a run.

Examples

Example 1

Input
demo()
Output
[1,2,3]
1 and 2 arrive, 1 is served, then 3 arrives — and 2 and 3 follow in the order they came.

Example 2

Input
makeQueue().dequeue()
Output
undefined
Nothing has arrived, so there is nothing to serve.

The Code

function makeQueue() {
  const inbox = [];
  const outbox = [];
  function transfer() {
    if (outbox.length === 0) {
      while (inbox.length > 0) {
        outbox.push(inbox.pop());
      }
    }
  }
  return {
    enqueue(v) {
      inbox.push(v);
      return inbox.length;
    },
    dequeue() {
      transfer();
      return outbox.pop();
    }
  };
}
function demo() {
  const q = makeQueue();
  q.enqueue(1);
  q.enqueue(2);
  const first = q.dequeue();
  q.enqueue(3);
  return [first, q.dequeue(), q.dequeue()];
}
demo();
Done
Step through demo() call by call

More like this

All stacks & queues examples (8) →