Building a Queue

Data Structures in JavaScript

Photo by Halacious on Unsplash

Every person has waited in a queue, whether it is at the grocery store or to get into you favorite concert. A queue’s operation is simple and intuitive, you get in the back of the line and wait your turn until your in the front of the line before exiting the queue. This is the same way the data structure of a queue works.

Node Class

In the person queue analogy, each person can be considered a node that contains some data and points the the next node. This node structure sounds very similar to the Node class create in the previous article Building a Singly Linked List, so let's pull that code.

Figure 1: Node Class

It is noted that the next property of this Node class defaults to null so it doesn't have to be defined at instantiation. From this point we need to create an overall Queue class which defines properties such as the front as well as back node of the queue in addition to several functions including add, remove, peek, and isEmpty.

Queue Class

To start, the Queue class needs to have a property that points to the front and back Node. Both of these property should default to null as the Queue will likely start empty.

Figure 2: Queue Class

From this point we can start adding functions to add and remove data to the Queue as well as a few helper utility functions.

Add Function

The add function will take in some data and add it to the back of the Queue. This will be done by first instantiating a new Node, assigning its data property to the passed in data. If the Queue already populated then the current last node’s next property must be updated to point to the newly created Node. Then the the last property of the Queue must be updated to be the newly created node. There is a second case where the Queue is empty so the last and first Node are the same.

Figure 3: Queue Class Add Function

Remove Function

In a Queue, the first Node is removed first and then the next one after it is assigned to be first. There is a special case when the Node being removed is the last Node therefore the last property of Queue must be set to null. This nuance can be hard to grasp at first but if you think about what happens as the Queue goes from two to one Node, the first node is set equal to the last node via the next function. Therefore when removing the last Node from the Queue the last property must be explicitly updated otherwise the add function would keep adding to the Queue.

Figure 4: Queue Class Remove Function

Peek Function

With the add and remove functions in place the Queue class is completely functional but some utility functions would be helpful. The peek function will simply return the front node without mutating the Queue.

Figure 5: Queue Class Peek Function

isEmpty Function

Finally, the isEmpty function will check if Queue itself is empty or not. This leverages the peek function and compares it return against null and then returns a boolean.

Figure 6: Queue Class isEmpty Function

Additional Discussion

If you have been keeping up with my “Data Structures in JavaScript” series you might have noticed that a Queue is very similar to a Stack. If you haven't, check out Building a Stack.