JavaScript Data Structures Queue

Learn about the queue data structure. We will also code a queue from scratch using JavaScript.

Table of Contents 📖

• What is a Queue?
• Coding a Queue Element
• Coding a Queue Constructor
• Coding a Queue Enqueue
• Coding a Queue Dequeue
• Running the Code

What is a Queue?

A queue is a data structure that follows the First In First Out (FIFO) principle. This means that elements can only be added to the back of the queue and elements can only be removed from the front of the queue. For example, in the image below, every time a new element joins the queue, it joins at the back and every time an element leaves the queue it leaves from the front.

Queues should be used when you want to get things out in the order you put them in. A classic example is printer software. When printing a document, the document that enters the printer's queue first is the one that gets printed first (FIFO).

Coding a Queue Element

To begin, lets create a queue element. We will create a class called QueueElement that represents an element in a queue.

class QueueElement {
  constructor(value) {
    this.value = value;
    this.behind = null;
  }
}

An element in the queue holds both its value and a reference to the element behind it in the queue.

Coding a Queue Constructor

Now lets code the constructor of the queue. An instance of a queue will have 3 properties: front, back, and size.

class Queue {
  constructor() {
    this.front = null;
    this.back = null;
    this.size = 0;
  }
}

Initially a queue will be empty which is why the front and back properties are set to null and the size is set to 0.

Coding a Queue Enqueue

Lets now work on adding an element to a queue. Remember, elements can only be added to the back of the queue. We will call this method enqueue.

enqueue(val) {
  const newQueueElement = new QueueElement(val);
  if (!this.front) {
    this.front = newQueueElement;
    this.back = newQueueElement;
  } else {
    const prevBack = this.back;
    prevBack.behind = newQueueElement;
    this.back = newQueueElement;
  }
  this.size = this.size + 1;
  return this.size;
}

• Create a new queue element out of the provided value
• Check if the queue is empty. If it is, we set the front and back properties to the new queue element
• If the queue is not empty, we set the behind property of the previous back queue element to the new queue element and then set the back element to be the new queue element

Because an element is always added to the back of the queue, the size of the queue has no impact on the time complexity for adding an element. Therefore, the time complexity for the addition of an element is O(1).

Coding a Queue Dequeue

Lets now work on removing an element from a queue. Remember, elements can only be removed from the front of the queue. We will call this method dequeue.

dequeue() {
  if (!this.front) {
    return null;
  }
  const prevFront = this.front;
  if (this.front === this.back) {
    this.front = null;
    this.back = null;
  } else {
    this.front = this.front.behind;
  }
  this.size = this.size - 1;
  return prevFront.value;
}

• First we check if the queue is empty. If it is we return null
• Next we create a temporary variable to hold the front of the queue
• If the queue has only one element, we set the front and back properties to null
• If the queue has more than one element, we set the front property to the next element in the queue as the front of the queue has been removed
• Decrease the size of the queue and return the value of the temporary variable which is the previous front element

Because an element is always taken from the front of the queue, the size of the queue has no impact on the time complexity for removing an element. Therefore, the time complexity for the removal of an element is O(1).

Running the Code

Now lets create an instance of our Queue class and use it.

const myQueue = new Queue();
myQueue.enqueue(1);
myQueue.enqueue(2);
myQueue.enqueue(3);
myQueue.enqueue(4);
myQueue.enqueue(5);
myQueue.dequeue();
myQueue.dequeue();
console.log(myQueue);

We can then run the code to get the following output.

Queue {
  front: QueueElement {
    value: 3,
    behind: QueueElement { value: 4, behind: [QueueElement] }
  },
  back: QueueElement { value: 5, behind: null },
  size: 3
}

Notice how in the output there is no element behind the back element and the element in the front is now the third one added to the queue.