The Stack Data Structure Explained In JavaScript

Algorithms and Data S­tructures are the heart and soul of computer science and programming. They are part of the fundamentals of computer programming. In this series, I'm going to make an effort to explain the most commonly used data structures in JavaScript.

To begin with a data structure is simply a format of organizing and storing data.

In this article we're going to cover the stack. By the end of this article you'll have understood what a stack is, the methods used on a stack and how to implement a stack by yourself in JavaScript.

What Is A Stack?

A stack is a last in first out type of data structure. This means that the last element to go in a stack is the first to come out.

You can think of it as a stack of books. In order to obtain the last book in the stack, you must first remove all the books on top. And when you wish to add a book, you simply put it on top.

There are four main operations that we can perform on stacks.

1. Adding to the stack. For this operation we use the push method which adds an item on top of the stack

2. Removing from the stack. For this operation we use the pop method which simply removes the item on top of the stack and returns it.

3. Checking the item on top the stack. For this method we use the peek method to simply return the item on top of the stack.

4. Lastly, we can check for the size of the array.

In JavaScript, arrays give us the properties of a stack. With arrays we can push, pop and check the length of the array.

A classic example that we can use to see how we would use a stack in JavaScript is the palindrome checker. A palindrome checker is a program that checks whether a word is spelt the same way both backwards and frontwards. For example ana is a palindrome and so is racecar and bob. Here is the implementation in JavaScript.

const checkPalindrome(word) {
    const stack = [];
    let reverseWord = '';

    for (let x = 0; x < word.length; x++) {
    stack.push(word[x]);
    };

    for (let y = 0; y < word.length; y++) {
    reverseWord += stack.pop();
    }

    return reverseWord === word ? `"${word}" is a palindrome` : 
    `${word} is not a palindrome`;
}

console.log(checkPalindrome('racecar')) // "racecar" is a palindrome

In the example above we used an array as a stack and to it we added every letter in the word. We then removed every last element in the array or stack in this case in order to create the reverse word. And lastly we checked whether the reversed word was the same as the word we received in the function.

When it comes to the time complexity of a stack, the worst case scenario of searching a stack is O(n) because the bigger the stack the more time we'll take searching it. The best case scenario of searching a stack is Ω(1) assuming the item we're searching for is the first item in the stack and the average case is O(n)

When it comes to deletion and insertion both the best, worst and average cases are O(1) simply because we can only add or remove one item on the stack

If you would like to further understand Big O notation, space and time complexity then consider reading this article.

In most cases we would never need to create an own stack, arrays suffice well enough. But in order to further understand stacks, we will implement a stack from scratch in JavaScript.

In this example we will use JavaScript classes to create the stack. I will implement the stack then explain what's going on. You can also try to figure out what's going on.

class Stack {
    constructor() {
        this.length = 0;
        this.stack = {}
    }

    push(value) {
        this.stack[this.count] = value;
        this.length++;
    }

    pop() {
        const result = this.stack[this.length];
        length--;
        delete this.stack[this.length];
        return result;
    }

    size() {
        return this.length;
    }

    peek() {
        return this.stack[this.length - 1];
    }
 }

Our stack will be an object and we will use the length variable to keep track of the size of the stack.

The push method accepts the value we want to add on the top of the stack. Instead of indices, each value will be paired to a property in which case the property will be the position of the value in the stack. This will allow us to still use the concept of indices to access items. Finally we increment the length.

The pop method does not accept an argument because it simply returns the item on top of the stack. Since the length keeps track of the stack's size, the length will represent the last item in the stack. We store the last item in the result variable before deleting it from the stack.

The size method is probably the simplest because all we do is simply return the length of the stack. That will be it's size.

And lastly the peek method simply returns the item on top of the stack. We subtract one from the length because the first item in the stack is stored at position 0 not 1. So whereas the length might be for example five, the first value is at position 0 and the last at 4.

Now let's see if indeed our stack works.

const myStack = new Stack();
myStack.push(12);
myStack.push(75);
myStack.push(28);
myStack.push(91);
myStack.push(19);
myStack.push(36);
console.log(myStack.size()) // 6
console.log(myStack.pop()) // 36
console.log(myStack.size()) // 5
console.log(myStack.peek()) // 19

Conclusion

This was a simple implementation of the Stack Data Structure in JavaScript. I hope you learnt something. I put this code in a repository on github in case you would like to refer to it later.
If you have any feedback or would just like to say hi feel free to do so via my Twitter account @joelpmugalu