Stack Implementation in Javascript

Stack is a very popular data structure. It is a LIFO or Last-In-First-Out data structure. It has practical applications in various use-cases. In this post, we will look at Stack Implementation in Javascript.

In general, Stacks are used in operating systems and programming languages to maintain the call stack. Another common use-case for a stack is the undo/redo functionality in word processors.

In real life, you can see a stack in action while picking up a dinner plate at a restaurant. You pick up the plate from the top of the pile. However, it is the latest plate in the pile.

1 – Important Stack Methods

A stack is not a very complicated data structure. Basically, it only has two important methods.

• Push – This method pushes an item into the stack. A new item
• Pop – This method removes the top-most item from the stack.

Many programming languages (such as Java) provide native implementations of Stack data structure. However, in Javascript, there is no specific implementation.

Basically, we can easily model a Stack data structure using an Array or a Linked List.

2 – Stack using Array in Javascript

A simple way to use Stacks in Javascript is by using an array. We can simply define an array in Javascript as below:

let Stack = []

Once we have the array, we can use two different approaches to use this array as a Stack.

2.1 – Using Push and Pop

We can then push new items into the array using the in-built push() function. See below:

Stack.push(3)
Stack.push(4)
Stack.push(5)

First element on the stack is 3. And the last element or the latest element is 5. Below is the how the array looks like.

[3, 4, 5]

We can now simply use the in-built pop() function to pop the latest item from the Stack.

Stack.pop()

The first execution of the above statement will return 5. When all elements have been popped, the pop() function returns undefined.

2.2 – Using Unshift and Shift

The second approach is to use the built-in functions known as Unshift and Shift.

Using the unshift() function, we can insert to the beginning of the array.

Stack.unshift(3)
Stack.unshift(4)
Stack.unshift(5)

After the execution of the above three commands, below is the how the array appears.

[5, 4, 3]

Basically, the element 5 is the latest on the pile. And the element 3 is the first element.

To replicate a Stack’s behavior, we can use the shift() function to remove an element from the beginning of the array.

Stack.shift()

2.3 – Comparing Push/Pop versus Unshift/Shift

In general, using Push and Pop approach is better than Unshift and Shift approach.

This is because inserting and removing an element from the beginning of an array is costly in terms of time complexity. Basically, when we add or remove from the beginning, each and every element in the list has to be re-indexed.

3 – Stack Implementation from scratch in Javascript

The use of in-built functions and the Javascript array is a perfectly fine approach to use as a Stack. However, internally it still relies on an array.

In case you need a more robust solution specific to your needs, we can also do a Stack Implementation in Javascript.

We will use Linked List to implement a Stack. You can read more about Linked List Implementation in Javascript in case you want more details about Linked List.

3.1 – The Node Class

The Node class basically defines a single element within a Stack.

class Node {
    constructor(val){
        this.val = val;
        this.next = null; 
    }
}

Here, we have only two attributes. The val attribute stores the value of the node. And the next attribute is like a pointer to the next element in the list.

3.2 – The Stack Class

The Stack class is the main class for our Stack Implementation in Javascript.

class Stack {
    constructor(){
        this.first = null;
        this.last = null;
        this.length = 0;
    }
}

Basically, here we have properties such as first, last and the length. When the Stack is initialized, we set the first and the last nodes to null and the length to 0. In other words, it is an empty stack.

3.3 – The Push Function

As we discussed earlier, the Push function for a Stack adds an element to the Stack.

Below is the implementation of such a function.

push(val){
        let newNode = new Node(val)
        if (this.length === 0){
            this.first = newNode;
            this.last = newNode;
            
        }else{
           let temp = this.first;
           this.first = newNode;
           this.first.next= temp;
        }
        this.length++;     
        return length;
}

To make things efficient, we will insert a new element in the beginning. To achieve that, we basically, update the current first element with the new node and assign that element as the new node’s next element.

We also increase the length of the Stack and return the same.

3.4 – The Pop Function

The Pop function is to return the latest element from the Stack. Since we inserted the new element in the beginning, we can very easily pop the first element from the beginning. We don’t have to traverse our Linked List in this case.

Below is the implementation for the Pop function.

pop(){
        if (this.length === 0) return null;

        let temp = this.first;

        if (this.length === 1){
            this.last = null;
        }        
        this.first = this.first.next;        
        this.length--;
        return temp;
}

Conclusion

With this, we have finished our Stack Implementation in Javascript. We also understood how Javascript arrays support Stacks out-of-the-box.

The code for this is available on this Gist.