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