Implement a Queue | JavaScript

This post will teach you how to create a queue in JavaScript and the difference between a queue and a stack.

So what is a queue, anyway? A queue is just a data structure in which the oldest element added is the first element removed. You may see this referred to as “FIFO”, which just stands for First In First Out. Think of it like standing in line at a grocery store. The first customer in line is the first to be helped.

So what’s the difference between a stack and a queue? The removal method in stacks have the opposite behavior of queues. They are LIFO, or Last In First Out. This means that the last element to be added to it is the first to be removed. Think of it like a stack of plates. Even though the first plate may have been added days ago, the first one you’ll wash is the one at the top.

Now, to the code.

Let’s initialize the variables we need in the constructor so that they can be accessed by any method in the queue. We need a way to keep track of the index of the oldest added element and the index of the next added element to be added. We’ll call the index of the next element to be added “top” and the index of the oldest added element ”bottom”. They’ll both be initialized to 0 to simulate a zeroth-based index.

constructor() {
    this.top = 0;
    this.bottom = 0;
}

And we also need a way to store the elements we’re adding, along with their indeces. We’ll call it “storage” and initialize it to en empty object.

constructor() {
    this.top = 0;
    this.bottom = 0;
    this.storage = {};
}

Picture it like this. If the first element you add is the letter “a”, it will look something like

0: a

because like almost any data structure, the first index is 0. If you add another element “b”, it will look something like this:

0: a,
1: b

Now, on to the methods.

enqueue(val) {
    this.storage[this.top] = val;
    this.top++;
}

The enqueue() method adds an element to the top of the queue. Take note that after the element is added, the “top” variable is incremented. Because of this, the “top” index is always one more than the index of the last-added element.

dequeue() {
    let removedElement = this.storage[this.bottom];
    delete this.storage[this.bottom];
    this.bottom++;
    return removedElement;
}

The dequeue() method removes an element from the bottom (oldest-added element) of the queue and returns the value of that element. Take note that the variable “bottom” is always the index of the oldest-added element (unless no elements have been added), so it is incremented after the element is removed. For example, if the “bottom” element has an index of 0, when that element is removed, the reference of the “bottom” element has to be changed to 1 since the element at 0 no longer exists.

peek() {
    return this.storage[this.bottom];
}

The peek() method just returns the oldest-added element. This element will change when the dequeue() method is used since the dequeue method removes the oldest-added element. The peek() method will then refer to the oldest-added element of the remaining elements.

size() {
    return this.top - this.bottom;
}

The size() method returns how many elements are in the queue. It’s a simple calculation of the index of the next element to be added (“top”) minus the index of the “bottom” element. Remember that “top” has a value of *one more* than the index of the last element added. So if the last element added has an index of 6, “top” has a value of 7 (6 + 1). If “bottom” is 5, we know that the queue has a size of 2 (“top” [7] – “bottom” [5]).

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

The isEmpty() method returns whether the queue has no elements in it. Since we already calculated the size, we can just check if the size is zero.

And that’s it! The full implementation is at the bottom of this page, but if you want to support us and are interested in the resources we use to make this content, check out the links below.

AFFILIATE LINKS

Great resource I use to learn algorithms.
40% off Tech Interview Pro: http://techinterviewpro.com/terriblewhiteboard
20% off CoderPro: http://coderpro.com/terriblewhiteboard

Last, but not least, here is the full implementation.

class Queue {
  constructor() {
    this.top = 0;
    this.bottom = 0;
    this.storage = {};
  }

  enqueue(val) {
    this.storage[this.top] = val;
    this.top++;
  }

  dequeue() {
    let removedElement = this.storage[this.bottom];
    delete this.storage[this.bottom];
    this.bottom++;
    return removedElement;
  }

  peek() {
    return this.storage[this.bottom];
  }

  size() {
    return this.top- this.bottom;
  }

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