A Quick Guide To Stacks In JavaScript

Understanding And Implementing Stacks

Kenneth Young
Nov 3 · 5 min read
Stacks — image by Gabriela Rivera Mejias © 2019

What are Stacks?

Stacks are a way to structure data. They are based on the concept of LIFO (Last In First Out). They can be implemented in various ways (which will be covered later on) but the idea is that you have 2 ways of interacting with the data: push an element on top of the stack or remove an element from the top of the stack.

Why are Stacks used?

For handling LIFO logic, Stacks have a Big O of:

  1. Insertion O(1)
  2. Removal O(1)
  3. Find element O(n)
  4. Access Element O(n)

They are used because they are almost instant for inserting and removing elements. In some other data structures, it takes O(n) to handle insertion because you first have to find where you will insert it (looking at you Binary Search Trees!). In others, to remove, you have to find the element to remove first or, like in Arrays, you have to relocate every element inside.

Where are Stacks used? You might recognize some of these.

  • JavaScript call stack
  • Applications that implement undo/redo
  • Applications that include recently used
  • Any data that needs to be handled with Last In First Out logic
  • Programming interviews — so take notes 👀

JavaScript Arrays as Stacks

You can handle Stacks using JavaScript Arrays. Although they are a bit slower than other alternatives, they are already implemented in JavaScript. It works completely out of the box. Remember, stacks need to implement two things; they have to be able to remove the last element added to the list and be able to add an element to the end of the list.

Here are two ways of handling Stacks using Arrays:

  1. You can use Array’s push and pop methods (add to the end, remove from the end)
Arrays as stacks example with push and pop
Arrays as stacks example with push and pop — GIF by Gabriela Rivera Mejias © 2019

2. You can use Array’s unshift and shift methods (add to the beginning, remove from the beginning)

Arrays as stacks example with unshift and shift
Arrays as stacks example with unshift and shift — GIF by Gabriela Rivera Mejias © 2019

Creating your own Stack with Linked Lists

Using Stacks with Linked Lists is the way to go if you want speed. They don’t come implemented in JavaScript, but they are faster than Arrays. That’s because when you remove an element from an Array, you have to relocate the Array’s indexes). When you remove an element from a Linked List, it’s near-instant. If Linked Lists sound confusing, check out this guide explained with images and gifs.

Implementing the Node class

A node has two properties: data and next. It looks like this:

Node class example

Implementing the Stack class

A Stack has three properties: the first node, the last node and the length of the Stack. It looks like this:

Stacks constructor example

Stack push and pop methods

There are two ways of handling push and pop. Similar to Arrays, we can insert and remove at the end of the Linked List, or at the beginning of the Linked List.

There are huge differences between them. Here they are:

  1. Insert and remove at the end of the Linked List (think Array push and pop methods)
  • Insertion O(1)
  • Removal O(n)

2. Insert and remove at the beginning of the Linked List (think Array unshift and shift methods)

  • Insertion O(1)
  • Removal O(1)

Although it’s normally called push and pop, we will implement it as if it was unshift and shift. That’s because if you insert and remove at the end of the Linked List, removing the last node involves iterating over the whole stack. This is because you have to change the last of the Stack to be the element previous to it. Since we don’t have access to previous with Linked Lists, you have to iterate over the whole Stack to get it.

Inserting and removing at the beginning of the Linked List doesn’t involve using previous elements, just the next ones, which we do have access to in Linked Lists. This makes insertion and removal happen in constant time, achieving our goal of O(1).

Implementing Stack push (unshift) method

There are two different cases to handle when adding an element to a Stack:

  1. The Stack is empty.
  2. There are elements in the Stack.

In both cases, you have to create a new node with the given data and increase the length by one.

In code, push (unshift) looks something like this:

Stacks push method example

Case 1: When the Stack is empty

Make both the first and last properties of the Stack to be the new node.

Case 1: push with no elements in the Stack — GIF by Gabriela Rivera Mejias © 2019

Case 2: When the Stack has elements

Make the new node point to the first property of the Stack and then change the first to be the new node.

Case 2: push with elements in the Stack — GIF by Gabriela Rivera Mejias © 2019

Implementing Stack pop (shift) method

There are three different cases when removing an element from the Stack:

  1. There are no elements in the Stack.
  2. There is only one element in the Stack.
  3. There are multiple elements in the Stack.

In code, pop (shift) looks something like this:

Stacks pop example

Case 1: When there are no items in the Stack

Do nothing and return null.

Case 1: pop with no elements in the Stack — GIF by Gabriela Rivera Mejias © 2019

Case 2: When there is only one element in the Stack

Remove the node that has the element by setting both first and last to be null. Decrease the length of the Stack by one and return the data that was in the removed node.

Case 2: pop with one element in the Stack — GIF by Gabriela Rivera Mejias © 2019

Case 3: When there are multiple elements in the Stack

Remove the first node by setting the first element of the Stack to be the next element in the list. Decrease the length of the Stack by one and return the data that was in the removed node.

Case 3: pop with multiple elements in the Stack — GIF by Gabriela Rivera Mejias © 2019

Complete Stack code

Altogether, a Stack implemented with Linked Lists looks something like this:

Stack class example

Thank you for making it this far! That was a quick guide to Stacks in JavaScript. If you found this helpful, leave a clap. If you have any ideas for future topics or questions leave a response below!

JavaScript in Plain English

Learn the web's most important programming language.

Kenneth Young

Written by

I am a programming enthusiast that likes to develop solutions and teach others how to write their own code.

JavaScript in Plain English

Learn the web's most important programming language.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade