Reverse a string using stack

An algorithm to reverse a string using stack.

We will implement a simple algorithm to reverse a string using stack in javascript. Everything will be written in ES6.

Example

Input:
'prashant'

Output:
'tnahsarp'

Implementation

As we know data in stack is stored in LIFO (Last In First Out) order, we can use this to reverse a string efficiently.

  • We will extract each character of the given string and add it to the stack.
  • Then we will remove each character from the stack and join it to form the reversed string.
  • As stack works in LIFO order we will get the last character first, then second last character and so on. Concatenating them together will form the string in reverse order.
let reverseString = (str) => {
   //Create a new stack
   let stack = new Stack();
   
   //Add each character to the stack
   for(let char of str){
     stack.push(char);
   }
   
   let reversed = '';
  
   //Form the reversed string by accessing each character from the stack
   while(!stack.isEmpty()){
      reversed += stack.pop();
   }
   
   //Return the reversed string
   return reversed;
}
Input:
console.log(reverseString('prashant'));

Output:
"tnahsarp"

Time complexity: O(n).
Space complexity: O(n).

Time and Space complexity

  • We are adding each character of the string in the stack which will take O(n) and then we are again removing the characters from the stack to form the reversed string in O(n), so Time complexity is O(n) + O(n) = O(n).
  • We are storing each character of the given string in stack, so Space complexity is O(n).

Leave a Reply

Your email address will not be published. Required fields are marked *