Implement a Stack in JavaScript

Data Structures
September 20, 2016

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.

  1. 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.

Example of push() and pop () for back-button

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:

  1. 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’.
  2. 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 Create push method on Stack prototype Add the given value into storage w/ a key of current count Increment count Create pop method on Stack prototype 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 Create size method on Stack prototype 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)

Code

This implementation does not include swap, empty or peek.

// This Stack is written using the pseudoclassical pattern // Creates a stack var Stack = function() { this.count = 0; this.storage = {}; } // Adds a value onto the end of the stack Stack.prototype.push = function(value) { this.storage[this.count] = value; this.count++; } // Removes and returns the value at the end of the stack Stack.prototype.pop = function() { // Check to see if the stack is empty if (this.count === 0) { return undefined; } this.count--; var result = this.storage[this.count]; delete this.storage[this.count]; return result; } // Returns the length of the stack Stack.prototype.size = function() { return this.count; }

Interview questions regarding stacks

Describe stack operations:

  1. pop — Pulls (removes) the element out of the stack. The location is specified by the pointer
  2. push — Pushes (inserts) the element in the stack. The location is specified by the pointer.
  3. peek returns the item on the top of the stack, without removing it.
  4. empty returns true if the stack is empty, false otherwise
  5. 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!

Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.

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

More Blog Posts