In this post you will learn how to implement such data structure in Javascript which is called queue.

Inside plain Javascript we don't get queue out of the box. But this is something that you might want to use in your application or you might get such question really often in the interview when they ask you about data structures.

What is Queue?

This is just a list of elements with the rule "First In - First Out".

Which means that we add an elements to the list and the first element that we take from the list is the first element that we added to the list. This is exactly why it is called queue. It works just like a normal queue in the real world.

Interview question

But here is a huge problem. Almost all people when they get a question to build a queue on the interview are doing it wrong and then they fail the interview.

What is the problem here? If you never implemented a queue you typically would use for that an array because it sounds logical. We have just an array of items, we push items inside and we use unshift to remove element from the array.

But the main problem is that this is not an efficient implementation. Yes array sounds really simple for this case.

Let's first implement a bad variant and then refactor it to a good one so you can understand the difference better.

The bad way

class BadQueue {
  items = []

  enqueue(element) {
    this.items.push(element)
  }

  dequeue() {
    return this.items.unshift()
  }
}

Here we implemented a basic class of our bad queue. We have an array of items inside and we use push and unshift to add and remove elements from the array.

The main problem in performance is exactly in dequeue function. It makes the time complexity not constant. If our array is big then dequeue takes more time to be executed.

With such implementation our time complexity is not constant but it is linear. Now we need to implement several helper methods.

class BadQueue {
  items = []

  enqueue(element) {
    this.items.push(element)
  }

  dequeue() {
    return this.items.unshift()
  }

  isEmpty() {
    return this.size() === 0
  }

  size() {
    return this.items.length
  }

  peek() {
    return this.items[0]
  }
}

isEmpty returns true if our queue is empty, size returns the amount of elements and peek allows us to see what next element is removed.

This is how people typically implement queue on the interview. Now let's check how it works.

const badQueue = new BadQueue()
badQueue.enqueue({id: '1', name: 'foo'})
badQueue.enqueue({id: '2', name: 'bar'})
badQueue.enqueue({id: '3', name: 'baz'})
console.log(badQueue.size())
console.log(badQueue.isEmpty())
const firstElement = badQueue.dequeue()
console.log(firstElement, badQueue.items)

Here we can see the size our our queue, that is it not empty and the first element that is removed.

The whole implementation is good but this dequeue method really breaks our performance.

The correct way

In the correct implementation we want to store data as an object and not as an array. We also need tail and head properties to get access to the first and last element in the list.

class GoodQueue {
  items = {};
  tail = 0;
  head = 0;

  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }

  dequeue() {
    const item = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return item;
  }
}

Here we implemented basic enqueue and dequeue function. We store elements in the object similar to the array implementation by index. Every time when we add an element to the object we increase our tail.

When we call dequeue we don't use unshift like previously but remove a key from the object and increase our head.

Let's implement our helper methods now.

class GoodQueue {
  items = {};
  tail = 0;
  head = 0;

  enqueue(element) {
    this.items[this.tail] = element;
    this.tail++;
  }

  dequeue() {
    const item = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return item;
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return this.tail - this.head;
  }

  peek() {
    return this.items[this.head];
  }
}

Our size method calculates the amount of elements as a difference between tail and head. In order to see next element that is removed we can use head as a key.

Let's check if it's working.

const goodQueue = new GoodQueue();
goodQueue.enqueue({ id: "1", name: "foo" });
goodQueue.enqueue({ id: "2", name: "bar" });
goodQueue.enqueue({ id: "3", name: "baz" });
console.log(goodQueue.size());
console.log(goodQueue.isEmpty());
const firstElement = goodQueue.dequeue();
console.log(firstElement, goodQueue.items);

As you can see we are getting exactly the same result but now our implementation has good performance.

And actually if you want to improve your Javascript knowledge and prepare for the interview I highly recommend you to check my course Javascript Interview Questions.