How to implement a queue in javascript in a short time when coding during interview?

Question

I am wondering is there any built-in module or package that I could use for implementing the queue in javascript when I am coding on leetcode. As you know, it is not possible to use much time to implement a queue by hands during interview. When I was using python, I always like to use a module called collections which includes a class deque. But after browsing on stack overflow, I found most of answers are telling people how to implement a queue in javascript from scratch. I am looking for such a convenient way to implement it. Could someone help?

Hmmmmmmmm, there seems to be not a better way for implementing a queue than just using Arrays. It seems to be based on the javascript engine itself. This is a link about it: time complexity of unshift() vs. push() in Javascript

Answer 1

A queue is a FIFO structure, where the first inserted element in the list is the first one to be taken off.

In JavaScript, you can easily use Arrays in order to implement this logic.

The shift method returns and removes the first element of the array (as dequeue does), so if you add elements using push, and remove elements with shift, you are actually using a queue.

Below is an example:

const a = [];
a.push(3);
a.push(5);
a.push(7);

console.log(a.shift());

In the same way, you can have a FIFO even using unshift for adding at the begin of the array and pop for removing from the end of the array.

The result is always a FIFO structure where the first element you have added, is the first one to be taken off:

const a = [];
a.unshift(3);
a.unshift(5);
a.unshift(7);

console.log(a.pop());

While implementing a stack in JavaScript could be done in O(1) with simple arrays, through push and pop which take O(1), the queue implemented as above should take O(1) for inserting and O(n) in the worst case for removals.

A better time complexity approach that you could take, which should let you implement a queue in O(1) for both insertions and removals, could be done using Map, as below:

class MyQueue extends Map {
  constructor() {
    super();
    this.insertionIndex = 0;
    this.removalIndex = 0;
  }

  queue(element) {
    this.set(this.insertionIndex, element);
    this.insertionIndex++;
  }

  dequeue() {
    const el = this.get(this.removalIndex);
    if (typeof el !== 'undefined') {
      this.delete(this.removalIndex);
      this.removalIndex++;
    }
    return el;
  }
}

const q = new MyQueue();
q.queue(1);
q.queue(2);
console.log(q.dequeue());
console.log(q.dequeue());
q.queue(3);
console.log(q.dequeue());
console.log(q.dequeue()); // now is empty so dequeue will return undefined with no errors
q.queue(4);
console.log(q.dequeue());

Answer 2

For Breath First Search. Rotate 2 array(s) might help. Average O(1) time for FIFO.