Data Structures and Algorithms: Queues

Introduction

Building on our knowledge of linked lists, we can now discuss queues.

A queue is a very specific implementation of a linked list, where we have a First In First Out(FIFO) structure. You can think of FIFO as being similar to people lining up at a cashier at a supermarket. The first one to be served is the person at the front of the line/queue, leaving the front once they have been served. Anyone who wants to join the line/queue must go to the back. Similarly, new values can only be added to the Tail of our structure, whilst values can only be removed from the Head. We are basically constraining the operations that we can perform with a linked list.

Below is a simple illustration of a queue, notice the similarities to a linked list as previously discussed.

Queue Methods in JavaScript

There are three methods associated with queue data structures, namely Enqueue, Dequeue and Peek. Before we get started, it would be a good idea to create a Node class.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Then we can create a Queue class with the following constructor:

 constructor() {
    this.head = this.tail = undefined;
    this.length = 0;
  }

Enqueue

The Enqueue method is used to add new nodes to the queue. Remembering that what defines a queue is its FIFO structure, so all new nodes must be added to the Tail of the queue. Here is an illustration to help visualize an enqueue operation.

Before declaring the new node as the Tail of the queue, the previous Tail points its next value to the new Node.

We can perform an Enqueue by creating the new node and increasing our length property accordingly.

    const newNode = new Node(data);

    this.length++;

Next we check for the Tail, which is another way of checking if the queue has any nodes.

 if (!this.tail) {
      this.tail = this.head = undefined;
      return;
    }

Finally, we point the current Tail's next value to the new node, followed by declaring the Tail to be the new node.

    this.tail.next = newNode;

    this.tail = newNode;

Here is what the final Enqueue code will look like:

  enqueue(data) {
    const newNode = new Node(data);

    this.length++;

    if (!this.tail) {
      this.tail = this.head = undefined;
      return;
    }

    this.tail.next = newNode;

    this.tail = newNode;
  }

Dequeue

The Dequeue method is used to remove the first node from our linked list.

This is done by setting the second node of the queue to the Head, before removing the previous Head from the queue.

To do this in code, first we need to check if the queue has any nodes. We can do this by checking for a Head.

 if (!this.head) {
      return undefined;
    }

Next we need to create a reference to the current Head, before assigning the queue's Head to the following node.

    const head = this.head;

    this.head = this.head.next;

Then we point the previous Head to undefined, thus removing it from the queue.

head.next = undefined;


Here is the code for the Dequeue method:

 deque() {
    if (!this.head) {
      return undefined;
    }

    this.length--;

    const head = this.head;

    this.head = this.head.next;

    head.next = undefined;

    return head.data;
  }

Peek

The peek method is used to get the data from the Head of a queue. This is what it looks like in code:

  peek() {
    return this.head.data;
  }

Conclusion

This covers the basics of queues as a data structure in JavaScript. Another way to approach this would be to use arrays and their inbuilt methods, but I thought that it would be interesting to use linked lists in this case. I hope this guide helps with your understanding of queues.