Stacks in JavaScript

by kirupa   |   24 August 2017

Have you ever used Undo or Redo when working on something?

Have you ever wondered how your favorite programming languages tend to turn the things you write into sequential steps that your computer knows what to do? Have you ever gone forward and backward in your browser? Do you like pancakes?

If you answered Yes to any of the above questions, then you have probably run into the star of this tutorial, the stack data structure. In the following sections, we'll learn more about stacks and how you can use one in JavaScript.

Onwards!

Meet the Stack

At some point in your life, I am pretty sure you have seen a stack of things arranged on top of each other...such as these pancakes:

The thing about stacks of things is that you always add items to the top. You remove items from the top as well:

This concept applies to things in the computer world as well. The stack is a well known data structure you will frequently encounter where, just like our pancakes, you keep adding data sequentially:

You remove the data from the end of your stack in the same order you added them:

In computer speak, this is known as a Last In First Out system - more commonly abbreviated as LIFO. The data that you end up accessing (aka removing) is the last one you added. That's really all there is to knowing about stacks, at least conceptually.

A JavaScript Implementation

To use stacks in JavaScript and see the awesomeness for yourself, just add the following lines of code to your project:

class Stack {
    constructor(...items) {
        this.items = items;
    }
    clear() {
        this.items.length = 0;
    }
    clone() {
        return new Stack(...this.items);
    }
    contains(item) {
        return this.items.includes(item);
    }
    peek() {
        var itemsLength = this.items.length;
        var item = this.items[itemsLength - 1];
        return item;
    }
    pop() {
        var removedItem = this.items.pop();
        return removedItem;
    }
    push(item) {
        this.items.push(item);
        return item;
    }
}

This code defines our Stack object and the various methods that you can use. To use it, all you have to do is something like the following:

var myStack = new Stack();
	  
// Add items
myStack.push("One");
myStack.push("Two");
myStack.push("Three!");

// Preview the last item
myStack.peek(); // Three

// Remove item
var lastItem = myStack.pop();
console.log(lastItem) // Three

myStack.peek(); // Two

// Create a copy of the stack
var newStack = myStack.clone();

// Check if item is in Stack
newStack.contains("Three")	// false

The first thing you need to do is create a new Stack object. You can create it an empty stack as shown or pre-fill it with some items as follows:

var stuffStack = new Stack("One", "Two", "Three");

To add items to the stack, use the push method and pass in whatever you wish to add. To remove an item, use the pop method. If you want to preview what the last item is without removing it, the peek method will help you out. The clone method returns a copy of your stack, and the contains method allows you to see if an item exists in the stack or not.

Conclusion

If you glance at the code, our stack implementation is just a wrapper over the Array object. Because items are added to the end and removed from the end, using the array's push and pop method works without any extra modification. The performance of adding and removing items from the end of an array is really good - constant time aka O(1) if you are keeping track.

For a discussion about this approach, check out the Simple Stack Implementation in JavaScript thread where senocular gave some great suggestions that made their way into the Stack code you saw earlier.

If you have a question about this or any other topic, the easiest thing is to drop by our forums where a bunch of the friendliest people you'll ever run into will be happy to help you out!

THE KIRUPA NEWSLETTER

Get cool tips, tricks, selfies, and more...personally hand-delivered to your inbox!

( View past issues for an idea of what you've been missing out on all this time! )

WHAT DO YOU THINK?

NEWSLETTER

No spam. No fluff. Just awesome content sent straight to your inbox!

Awesome and high-performance web hosting!
BACK TO TOP
new books - yay!!!