Building a Queue
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.
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
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.
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
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
Node are the same.
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
last property must be explicitly updated otherwise the
add function would keep adding to the
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
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.