# Building a Queue

## Data Structures in JavaScript

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.

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.

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.

## 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`

.

## 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`

.

# 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.

# 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.