How the Stack Data Structure Works in JavaScript

Everything about the stack data structure in JavaScript.

The stack data structure is great in tracking things in an order that allows you to trace back to the origin. When you control-z or undo something, click the back or forward browser button — when your code editor tells you are missing a closing parenthesis on line 13 — you may be dealing with some sort of stack data structure.

Video Version of This Article

This post is a more detailed article version of the Stack Data Structure Series on Youtube that you can check if you prefer videos.

Watch Videos

What is a Stack?

The stack data structure is a collection of elements that implements the LIFO principle — Last In First Out. Its main actions are “pop” — to remove an element — , “push” to add and peek(or peep) to look at the top element.

It is a linear data structure and also an abstract data type. That means that the elements are placed linearly rather than nested (like a tree) or interconnected (like a graph) and that it is defined by its behavior rather than being a mathematical model.

So a stack is a list and what makes it a stack is how it behaves and not how it is seeing by the computer or what it contains.

When to use Stack?

A stack is great for whenever you need to trace back all your steps or actions. It is like the Hansel and Gretel solution to head back home by leaving breadcrumbs behind as they adventure into the forest.

That's why it is used in browser history tracking and routing or to manage your actions in a program or system so you can ctrl-z or undo the action. Any program or problem which requires you to trace back can be implemented using a stack.

A stack is also used in complex tree and graph algorithms since it helps trace back a path.

Stack implemented with Array

Because the stack is a list and what matters is how it behaves and works rather than a specific detail about the list, we can use any other list data structure to implement it. For this section, I’ll use an Array.

To start, I’ll create a class with a private list that is initialized to an empty array and Ill also add a getter to get the size and to check if the stack is empty.

class Stack {
#list = [];

get size() {
return this.#list.length;
}
get isEmpty() {
return this.size === 0;
}
}

Using JavaScript arrays makes it easier because it already contains the methods in common with a stack. Let's add a push and pop method which simply uses the array equivalent methods.

push(element) {
return this.#list.push(element);
}
pop() {
return this.#list.pop();
}

For the peek method, we simply return the last element in the list.

peek() {
return this.#list[this.size - 1];
}

As you can see, it is a very simple concept to implement and you may be asking why bother with creating a class if you can just use the array directly as a stack? Let’s look at the difference.

Array vs Stack

Both array and stack are collections of elements. An array is an indexed list that allows random read and writes whereas a stack implements the LIFO principle. The only element you access in a stack is the last element by peeking or popping it out.

They both serve a different purpose and just because you can use an array to implement a stack does not make them closely equal. The JavaScript array can contain anything so it is more like a list rather than an array compared to other languages like C++ and Java. So, it is easy to be confused about the need to implement a stack or what the difference can be.

It is these restrictions and characteristics in a list that makes a stack a totally different list and one that solves a very specific problem. An array does not implement the LIFO principle and using an array means you must follow a convention and resist the temptation to perform other operations. If you want to be strict, implementing a stack is ideal.

Max Stack

One feature we can add to our stack implementation is the capability to limit the number of elements it can contain.

We can add a “capacity” private member and a constructor to take the capacity which we ensure is never going to be less or equal to zero. A nice detail is the ability to check if the stack is full since we now have a max number of items that we can have.

class Stack {
#list = [];
#capacity = null;
constructor(capacity = null) {
this.#capacity = Math.max(Number(capacity), 0) || null;
}
get isFull() {
return this.#capacity
? this.size === this.#capacity
: false;
}
...

With this new detail, we need to change our push method to take into consideration the capacity. We only push to the stack if it hasn’t reached the limit. This prevents new things from being added to the stack.

push(item) {
if (!this.isFull) {
this.#list.push(item);
}
return this.size;
}

To finalize this implementation, let's add a “toString” method to make this easier for JSON or any other printing situations.

toString() {
return this.#list.toString();
}

Source Code: Check this full code on Github

Stack implemented with Linked List

To fully understand the following implementation, I recommend you read the Linked List Data Structure article for more details. Using a linked list to implement a stack really illustrates that a stack is just based on a principle a list implements and not the nature of the list.

Let’s set this Stack class and there are a few things we do differently. First, we have the private “#lastItem” that we use to track the top element in the stack that was inserted last. We don't have a list so we add a “#size” to track how big the list is. Everything else is the same as the previous implementation.

class Stack {
#lastItem = null;
#size = 0;

#capacity = null;

constructor(capacity = null) {
this.#capacity = capacity;
}
get size() {
return this.#size;
}
get isEmpty() {
return this.size === 0;
}
get isFull() {
return this.#capacity ? this.size === this.#capacity : false;
}
...

A linked list element has pointers that point to the next and previous element. You can have both pointers but for this one, we only need one. We introduce a private method that given a value, returns the linked list element with the value, and the previous pointer set to null.

#createItem(value) {
return {
prev: null,
value
}
}

For our push method, we check if it hasn't reached the limit still and then proceed to use the provided item to create our linked list element. If the stack is not empty we make the new item point back to the current last item because it will become the new last item. This is what links the elements together and that's why it is called a linked list. Then, because we added a new item, we increment size.

push(item) {
if(!this.isFull) {
const newItem = this.#createItem(item);
if(!this.isEmpty) {
newItem.prev = this.#lastItem;
}
this.#lastItem = newItem;
this.#size += 1;

}
return this.size;
}

For our pop method, we initialize a null removed item to be returned at the end. If the stack is not empty we grab the last item value as the item to be removed and use the previous item in the list to set the last item property. Because we removed an item, we have to decrement the size.

pop() {
let removedItem = null;
if(!this.isEmpty) {
removedItem = this.#lastItem.value;
this.#lastItem = this.#lastItem.prev;
this.#size -= 1;
}
return removedItem;
}

Our peek method is also very simple. All we do is return the last item value. I used the JavaScript optional chaining operator to make sure I am not trying to access value on a null or undefined last item.

peek() {
return this.#lastItem?.value;
}

To wrap this implementation, our toString method is a little more detailed. With a linked list you use its pointers to navigate through the list and for this one we can only go backward.

So if the list is empty we simply return an empty string. We have to create a current variable to hold our current element we are iterating and to start we use the only element we have a hold on, the last item. We initialize the string to be returned with its value and look backward while there is still a previous element to go to update the string and the current variable with the current element in the list value. In the end, we return the string.

toString() {
if(this.isEmpty) {
return '';
}
let current = this.#lastItem;
let str = `${current.value}`;
while(current.prev) {
current = current.prev;
str = `${current.value},${str}`;
}
return str;
}

A linked list is really powerful because it connects data that can be anywhere in memory with pointer references. If you want to learn more about it and how it compares against other lists check its dedicated article in this blog series.

Source Code: Check this full code on Github

Conclusion

A stack is a very simple concept and yet can be a very powerful data structure to take advantage of in a project. When implemented using a linked list it really stands out more and becomes more fun to work with.

A common problem used to test stack data structure knowledge is the Balance Parenthesis problem. Try it and let me know in the comments.

YouTube Channel: Before Semicolon
Website: beforesemicolon.com

More content at plainenglish.io

Blog & YouTube Channel for Web, UI & Software Development - beforesemicolon.comyoutube.com/c/BeforeSemicolon

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store