loading...
Cover image for How (and Why) To Implement a Stack in JavaScript

How (and Why) To Implement a Stack in JavaScript

mattpopovich profile image Matt Popovich Originally published at popovich.io ・6 min read
  1. What's a Stack?
  2. Implementing a Basic Stack
  3. Preventing Stack Underflows & Overflows
  4. Why Would We Want to Use a Stack?

# What's a Stack?

In computer science, a stack is a data structure, specifically an abstract data type. It's a type of collection (meaning a list of items, similar to an array). What makes a stack distinct is that it's constrained by specific rules governing how items can be added and removed.

A stack only allows items to be added to, or removed from, one end of the list (the top of the stack). This is known as Last In, First Out. Items are added with a push() operation and removed with a pop() operation.

Think of it like a stack of pancakes:

You can push a pancake onto the top end of the stack...

Someone putting a pancake onto a stack of pancakes

...and you can pop a pancake off of the top end of the stack...

Someone pulling a pancake off the top of a stack

...but you can't add pancakes to, or remove pancakes from, the middle of the stack or the bottom end of the stack. Otherwise they'll go flying.

Someone trying to pull a pancake out of the middle of a stack, but other pancakes are falling

# Implementing a Basic Stack

In its most basic implementation, a stack has to keep track of two internal variables:

  1. A number representing the size of the stack, and
  2. A hash table (in other words, an object) representing the data in the list.

To begin implementing our stack, we'll need to set these:

function Stack () {
  this.size = 0;
  this.data = {};
}

Implementing .push()

Because the hash table is zero-indexed, the size value is always one greater than the last value that was added to the hash table. Whenever we push a new value onto the hash table, we'll add the data to the hash table, keyed by current size, and then increment the size value.

function Stack () {
  this.size = 0;
  this.data = {};

  // Add a value to the top of the stack
  this.push = function (value) {
    this.data[this.size] = value;
    this.size++;
  }
}

Now, we can push values onto the stack, and view its size:

let stackOfOnes = new Stack();
stackOfOnes.push(1);
stackOfOnes.push(1);
stackOfOnes.push(1);
console.log(stackOfOnes.size); // 3

Implementing .pop()

To pop off the last value, we access it from the hash table using the size value to determine its key, delete it from the hash table, decrement the size value, and return the retrieved value.

function Stack () {
  this.size = 0;
  this.data = {};

  // Add a value to the top of the stack
  this.push = function (value) {
    this.data[this.size] = value;
    this.size++;
  }

  // Remove a value from the top of the stack, and return it
  this.pop = function() {
    let lastKey = this.size - 1;
    let result = this.data[lastKey];
    delete this.data[lastKey];
    this.size--;
    return result;
  }
}

Now, we've got a basic functional stack: we can push values onto the stack, pop them off the stack, and view its size.

let fruitStack = new Stack();
fruitStack.push('apple');
fruitStack.push('banana');
fruitStack.push('orange');
console.log(fruitStack.size); // 3
let lastFruit = fruitStack.pop();
console.log(lastFruit); // 'orange'
console.log(fruitStack.size); // 2

# Preventing Stack Underflows & Overflows

Now, you're probably already starting to realize that we could run into some issues here. What happens, for example, if we try to to .pop() a value off an empty stack?

Attempting to pop an empty stack is called a stack underflow. You've probably also heard of a stack overflow, which is when a stack's size exceeds a certain limit. Stacks usually set a predetermined bound in order to prevent infinite-loop bugs that attempt to push items onto the stack over and over indefinitely.

To make our stack more resilient, let's add some guardrails against underflows and overflows.

First, we'll add a check in .pop() to ensure we aren't popping an empty stack:

function Stack () {
  this.size = 0;
  this.data = {};

  // Add a value to the top of the stack
  this.push = function (value) {
    this.data[this.size] = value;
    this.size++;
  }

  // Remove a value from the top of the stack, and return it
  this.pop = function() {
    if (this.size === 0) {
      console.log(`Stack underflow!`);
      return;
    }
    let lastKey = this.size - 1;
    let result = this.data[lastKey];
    delete this.data[lastKey];
    this.size--;
    return result;
  }
}

Next, we'll set an internal bound variable when the stack is created, and add a check in .push() to ensure we aren't exceeding that bound.

function Stack (bound = 10) {
  this.size = 0;
  this.bound = bound;
  this.data = {};

  // Add a value to the top of the stack
  this.push = function (value) {
    if (this.size >= this.bound) {
      console.log(`Stack overflow!`);
      return;
    }
    this.data[this.size] = value;
    this.size++;
  }

  // Remove a value from the top of the stack, and return it
  this.pop = function() {
    if (this.size === 0) {
      console.log(`Stack underflow!`);
      return;
    }
    let lastKey = this.size - 1;
    let result = this.data[lastKey];
    delete this.data[lastKey];
    this.size--;
    return result;
  }
}

Now we've got a more resilient structure that will prevent invalid pushes and pops:

let nsync = new Stack(5);
nsync.pop(); // Stack underflow!
nsync.push(`Justin Timberlake`);
nsync.push(`Lance Bass`);
nsync.push(`Joey Fatone`);
nsync.push(`JC Chasez`);
nsync.push(`Chris Kirkpatrick`);
nsync.push(`Michael Bublé`); // Stack overflow!

We don't like that dirty pop.

# Why Would We Want to Use a Stack?

1. Performance? (Probably not)

In some languages, a stack has the advantage of being more performant than alternative data structures like arrays. However, JavaScript arrays are optimized so that you're not likely to be able to beat them at efficiency.

Array.prototype.push() and Array.prototype.pop() are already O(1) efficient. So no matter the size of the array, it won't take any longer to push items onto or pop them off of the array.

However, this isn't true about other array methods. When we're not only appending to and removing from one end of an array, we lose the stack-like O(1) efficiency. For example, .shift()ing an item to the front of an array -- analogous to the bottom of the stack here -- is only O(n) efficient, because every single item in the array must have its index incremented. With a new array[0], the item previously at array[0] becomes array[1], the item at array[1] becomes array[2], etc. (Technically, this isn't strictly speaking true in JavaScript due to clever optimizations, but it's how it works conceptually, and the optimizations don't change the O(n) efficiency.)

2. Enforcing LIFO

Okay, so arrays' .push() and .pop() methods are pretty efficient in JavaScript. But that doesn't mean stacks are useless. They could be the right choice in situations where you only care about the value most recently added to a list, and you want to enforce that only that value can be accessed.

Say you're building an undo functionality into your drawing web app. Every time a user makes a change to their artwork, you need to push the previous state of the artwork onto a list. Every time a user undoes an action, you need to pop that previous state off the list, so that it becomes the active state of the artwork again.

In this case, it's likely we don't care about accessing artwork states other than the most recently added one. We don't care about needing to access the initial state of the artwork, a blank canvas (this would be the bottom of the stack). And the user isn't ever going to ask us to jump directly to the state it was exactly thirty-seven actions back (so we don't need to access by index, i.e. undoStates[37]). Only the last action ever matters.

A stack could be the right choice for this use case because it enforces the Last In, First Out (LIFO) access order, preventing less efficient O(n) array methods.

Discussion

markdown guide
 

C# has a Stack class defined in the framework and it has the functionality of peek. Why Peek? Sometimes we want to know what it's the "over-top" value (i.e. the last one) without removing it.

It's pretty easy to implement peek, it's exactly like pop but without pop.

this.peek= function() {
    if (this.size === 0) {
      console.log(`nothing here`);
      return;
    }
    let lastKey = this.size - 1;
    let result = this.data[lastKey];
    return result;
  }

Why LIFO anyways?

Let's say you are running a company in Australia that sells toilet paper.

And it is your stock

let paper= new Stack(5);
paper.push(`Regular paper`);
paper.push(`Premium one`);
paper.push(`2ply paper`);

But then, suddenly Aussies got crazy purchasing toilet paper.

paper.pop();

paper.pop(); // Stack underflow!

You don't want to runs out of stock, so you buy more paper but also you want to sell your recent paper because it's a cheap product that you could sell in quantities and the customers can't bargain because the hype to buy paper.


paper.push(`generic paper`);
paper.pop();
 
 

Doesn't JavaScript already have stack in Array, Array.push and Array.pop are exactly the same functions, why create a new stack?

 

This is more of a guide to implementing this specific data structure in JavaScript, as a means of teaching the concept of a stack. It's true that arrays can do all that stacks can do and more, so in most real-world situations, you'd probably want to use an array, unless you specifically want to prevent the use of methods other than .push() and pop(). Beyond that, this is also useful as a thought experiment of the type you might be asked in a technical interview.

 

Nice article. I Didn't now about shift complexity. Thanks.