By Elson Correia
Everything about the stack data structure in JavaScript.
The stack data structure is great for tracking things in an order that allows you to trace them 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.
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 seen 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 Hansel and Gretel's 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 I'll 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 reads 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 an 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 elements. You can have both pointers but for this one, we only need one. We introduce a private method that gives 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 the 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 the 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 SemicolonWebsite: beforesemicolon.com