Implement a Stack in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital, I write about tech topics and teach…

Implement a Stack in JavaScript

Having worked across sites raking in over 50 billion website visits annually with Higglo Digital, I write about tech topics and teach engineers to have solid foundations that will help them get ahead in their career. I also build awesome products for digital nomads — check it out!

JavaScript eBook

I’ve written an eBook on JavaScript that will take you from beginner to professional. Having been in your shoes moving to making over $200,000 per year in just a few years as a software engineer, I know exactly what it takes to get there. Check out the ebook now!

This is the first of a series of articles on implementing data structures in JavaScript. If you’re new to data structures, be sure to read this introduction (link to come) to data structures first. Already know about stacks? Head on over to the next article on Queues.

Stacks and queues are the most basic of the more advanced data structures that you’ll be learning. The good news is that they are easy to implement in JavaScript. Throughout this article, I’m going teach you everything you need to know about stacks and how to implement your own.

If you’re familiar with a little bit of JavaScript but don’t yet know what stacks are… you’re in luck! That’s because you can imagine a stack as an array, except simpler. Both have methods that include push() and pop(). A stack, however, is LIFO (Last In First Out). Think of it as a stack of dishes. You’ve already put dishes in a stack, and now you want to take them off, so you grab the one directly on top and remove it. Below is an example of this dishwasher continuously ‘popping’ a value off the stack.

This sounds way too simple to be a valuable data structure, right? Let’s talk about a simple use-case — your browser’s back button. You would create a stack of URLs… then push every new URL on top of that stack. If you press the back button, it would pop off the current URL. Let’s take a look at how this would work:

In the first image (top right), we just opened up facebook.com, so we add it on top of the stack of sites that we’ve already visited previously. The second image (middle) is what the stack now looks like while we’re visiting facebook.com. The third image (bottom right) is where we pressed the back button to navigate back to twitter.com, so we pop() off the most recent url.

Analysis

So you might be wondering why the heck you’d use a stack instead of the array, especially when there are so many built in methods on the Array prototype to utilize! The reasons are two fold:

Most methods on the Array Prototype have a time complexity of O(n). Let’s look at a specific example like splice(). When you splice an array, it has to find the specific index, remove a specified number of elements, then shift all the following elements forward to fill the place of the removed elements. Contrast this with using the stack (object) which has direct look-up of properties and does not have to be kept ‘in-order’.
Arrays take up a block of space because they have to keep their order, where as an object does not.

Pseudo Code

Create Stack class/constructor create and set count to 0 create storage object

 Add the given value into storage w/ a key of current count
 Increment count

 Check to see if stack is empty
 if so, return undefined
 Decrement count
 Save element at top of stack to a var (to later return)
 Delete that element from storage
 Return saved element

 Return count

Time complexity

If you don’t know much about time complexity, you’ll be lost until you read this short article on time complexity in JavaScript. For each method on the stack, the worst-case time complexity is constant — O(1). This means that as the stack grows to n size, each method completes its job in the same amount of time.

push: Constant — O(1)
pop: Constant — O(1)
peek: Constant — O(1)
empty: Constant — O(1)
size: Constant — O(1)
swap: Constant — O(1)

Why Use a Stack in JavaScript

Using a Stack is highly useful in various programming scenarios. The LIFO (Last-In-First-Out) nature of a Stack makes it ideal for managing function calls and handling recursion. It allows for tracking the execution flow and easily returning to previous function calls when necessary. Stacks are also valuable in implementing undo/redo functionality, as operations can be pushed onto the Stack and undone or redone by popping elements. Additionally, a Stack can be employed in solving problems that involve depth-first search, backtracking, or parsing and evaluating expressions. The simplicity and efficiency of Stack operations, such as push, pop, and peek, make it a versatile tool for organizing and managing data in a wide range of applications, making it a fundamental data structure for JavaScript developers.

Code

This implementation does not include swap, empty or peek.

Interview questions regarding stacks

Describe stack operations:

pop* — Pulls (removes) the element out of the stack. The location is specified by the pointer*
push* — Pushes (inserts) the element in the stack. The location is specified by the pointer.*
***peek — ***returns the item on the top of the stack, without removing it.
***empty — ***returns true if the stack is empty, false otherwise
swap* — the two top most elements of the stack can be swapped*

Explain stacks in detail:

A stack is a data structure based on the principle Last In First Out. stack is container to hold nodes and has two operations — push and pop. The push operation is to add nodes into the stack and pop operation is to delete nodes from the stack and returns the top most node.

Are you ready to take on some more advanced data structures? Next up is the queue!

JavaScript eBook

I founded Higglo Digital and we can help your business crush the web game with an award-winning website and cutting-edge digital strategy. If you want to see a beautifully designed website, check us out.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!

Add the given value into storage w/ a key of current count Increment count Check to see if stack is empty if so, return undefined Decrement count Save element at top of stack to a var (to later return) Delete that element from storage Return saved element Return count