Reverse a String with a Stack in JavaScript

Photo by Johnson Wang on Unsplash

In this article, we will learn how to reverse a string using a stack in JavaScript.

What is a stack?

A stack is a linear data structure that follows a particular order in which the operations are performed. The order is Last In First Out (LIFO).

A simple visualization of a stack

Stacks use push() and pop() for adding and removing elements respectively. A stack can have as many elements as you want, but the way of adding and removing elements remains LIFO. You cannot operate on elements from the bottom/in between the stack. In this article, we will implement a basic stack in JavaScript and use it for reversing a string!

Implementing the stack

For implementing the stack, we will use a class-based approach. The following methods will be utilized in the stack.

1. push() — Adds an element to the stack.
2. pop() — Removes and returns the topmost element of the stack.
3. isEmpty() — Returns true or false based on if the stack is empty or not.

Let us write the code for the stack!

First, let us create a class stack with a constructor that initializes an array called elements which will store the elements.

class stack { 
    constructor(){  
        this.elements = []; 
    }
}

Now, let us add all the methods.

The push method:

push(element){ 
    this.elements.push(element) 
}

The pop method:

pop(){ 
    if(this.elements.length === 0) return "Underflow situation"; 
    else return this.elements.pop();
}

The isEmpty method:

isEmpty(){ 
    if(this.elements.length > 0) return false;
    else return true;
}

Reversing a string overview

First and foremost, it is important to visualize how will we reverse a string to make development much easier.

The reversing of the string will follow 3 steps:

1. The string’s each character will be added (pushed) to the stack.
2. After step 1, the stack will be popped and a reversed string is created.
3. Return the reversed string.

A visual representation of the algorithm

The code

The stack:

class Stack {
 
    constructor(){  
        this.elements = []; 
    }
    push(element){ 
        this.elements.push(element) 
    }
    pop(){ 
        if(this.elements.length === 0) return "Underflow situation"; 
        else return this.elements.pop();
    }
    isEmpty(){ 
        if(this.elements.length > 0) return false;
        else return true;
    }
}

The reverse function:

function reverse(str){
     //Creates a new stack
     let stack = new Stack();
      
     let i = 0;
     let reversedStr = "";
     //Adds all the characters to the stack.
     while (i !== str.length) {
         stack.push(str.charAt(i));
         i++;
     }
   
     //Creates a reversed string by popping the stack.
     while (!stack.isEmpty()) {
         reversedStr += stack.pop();
     }
     //returns the reversed string.
     return reversedStr;
}

Testing the above function

Let us test the function. Here are some test cases: BrEAd, MeDIum, javascript.

Input: BrEAd             Input: MeDIum           Input: javascript
Output: dAErB            Output: muIDeM          Output: tpircsavaj

The function works perfectly!

Time and space complexity

The time complexity of the algorithm is O(n), and the space complexity is also O(n).

Explanation

The space complexity is O(n) as we are pushing and storing each element (character of the string) in the stack.

The time complexity is O(n) because we are accessing each character of the string, and pushing it on the stack. After this, we again pop each character from the stack and create the reversed string [O(n) + O(n) = O(n)].

The final code

Repository link: https://github.com/Megh-Agarwal/reverse-string-using-stack-js

Conclusion

Thank you for reading this article. I hope you have found it useful. If so, be sure to leave a comment to let me know :)