Implement a Stack in JavaScript

Implement a Stack in JavaScript

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:

(referencing the image below) In the first block (top left), 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.

1_dnyizg-yoAJBUiAqhzhtuA.png

Analysis

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

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.