Building a Stack

Data Structures in JavaScript

Photo by nikldn on Unsplash

There is nothing better than a stack of buttermilk pancakes to calm that early morning sweet tooth. Now, I normally slice through the whole stack and eat a bit from each pancake at once but lets pretend, for the sake of this discussion, that I am a reasonable person that eats a single pancake at a time. To do so, the top most pancake would be pulled off of the stack and consumed followed by the next pancake on top. This is the same way the linear data structure of a stack works. In the data structure world, this methodology is referred to as “last in first out”.

Node Class

In the pancake analogy, each pancake 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 Stack class which defines properties such as which node is on the top of the stack as well as several functions including push, pop, peek, and isEmpty.

Stack Class

To start, the Stack class needs to have a property that points to the top Node. This property should default to null as the Stack will likely start empty.

Figure 2: Stack Class

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

Push Function

Borrowing the function naming from standard arrays, push will add data to the top of the Stack. To do this, a new Node will be created, it’s next property will be set to the current top node, and then the current node will be set to the top node. See Figure 3 for the implementation of these actions in JavaScript.

Figure 3: Stack Class Push Function

Pop Function

Once again, similar to the array function naming the pop will remove the last node in the Stack which in this case is the top. The node being removed will be provided as a return value. The top property of the Stack must also be updated to represent the new state.

Figure 4: Stack Class Pop Function

Peek Function

With the push and pop functions in place the Stack class is completely functional but some utility functions would be helpful. The peek function will simply return the top node without mutating the Stack.

Figure 5: Stack Class Peek Function

isEmpty Function

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

Figure 6: Stack Class isEmpty Function

Additional Discussion

The above Stack and Node class successfully implement the linear data structure know as a stack but there is room for improvement. For example it would be ideal if the Node class was nested inside the Stack class and was only accessible by the Stack class itself. That is, an instance of Stack should not have access to the Node class. Another potential source of errors is that the user has direct access to the top property of Stack and could therefore overwrite it manually resulting in erroneous behavior of the class functions. Finally, the data types for the Node and Stack are not enforced in any way because well, that can’t be done in JavaScript but it is a good argument to use TypeScript.

It is always good practice to take a second look at your code and see what else could be refactored and improved. Keep a look out for a future article which will address some of these concerns! In the meantime, check out a very similar data structure in Building a Queue.