String: Program to reverse a string using a stack data structure

Write a program to reverse a string using stack data structure

In Java the String class is Immutable, and it is not possible to directly apply any operations to the Java String class.
So we have converted the string to StringBuffer, used the stack to reverse the sequence of chars and add that back to StringBuffer.

Approach

1. Define an Empty stack
2. Pick the characters one by one from the StringBuffer and push it in the stack
3. After processing all chars, the last element of the StringBuffer will be at the top of the stack and the first element will be at the bottom of the stack
4. Pop the elements from the stack and add that to the StringBuffer
5. Finally print the final StringBuffer object

Complexity

Time Complexity: O(N) where n is the length of the string
Space Complexity: O(N) since we are using a stack to hold all the chars of string

Java Code

import java.util.*;

    class ReverseStringUsingStack{
    
        static class Stack{ 
            int size; 
            int top; 
            char[] a;  
          
            boolean isEmpty(){ 
                return (top < 0); 
            } 
              
            Stack(int n){ 
                top = -1; 
                size = n; 
                a = new char[size]; 
            } 
          
            boolean push(char x){ 
                if (top >= size){ 
                    System.out.println("Stack Overflow"); 
                    return false; 
                } 
                else{ 
                    a[++top] = x; 
                    return true; 
                } 
            } 
          
            char pop(){ 
                if (top < 0){ 
                    System.out.println("Stack Underflow"); 
                    return 0; 
                } 
                else{ 
                    char x = a[top--]; 
                    return x; 
                } 
            } 
        }
    
        public static void reverse(StringBuffer s){ 
            int n = s.length(); 
            Stack obj = new Stack(n); 
              
            int i; 
            for(i = 0; i < n; i++){ 
                obj.push(s.charAt(i));
            }    
          
            for(i = 0; i < n; i++){  
                char ch = obj.pop(); 
                s.setCharAt(i, ch); 
            } 
        }  
          
        public static void main(String args[]){ 
             
            String wordToReverse = "Reverse";
            System.out.println("Original word: " + wordToReverse);
            
            StringBuffer s = new StringBuffer(wordToReverse);  
            reverse(s); 
              
            System.out.println("After reversing using stack: " + s); 
        } 
    
 }

Output

Original word: Reverse
After reversing using stack: esreveR