Given a string, reverse it using stack. For example “GeeksQuiz” should be converted to “ziuQskeeG”.

Following is simple algorithm to reverse a string using stack.

1) Create an empty stack.
2) One by one push all characters of string to stack.
3) One by one pop all characters from stack and put 
   them back to string.

Following are C and Python programs that implements above algorithm.

Java Programming:

/* Java program to reverse 
   String using Stack */
     
import java.util.*;
  
//stack
class Stack
{
    int size;
    int top;
    char[] a; 
   
    //function to check if stack is empty
    boolean isEmpty()
    {
        return (top < 0);
    }
      
    Stack(int n)
    {
        top = -1;
        size = n;
        a = new char[size];
    }
   
    //function to push element in Stack
    boolean push(char x)
    {
        if (top >= size)
        {
           System.out.println("Stack Overflow");
           return false;
        }
        else
        {
            a[++top] = x;
            return true;
        }
    }
   
    //function to pop element from stack
    char pop()
    {
        if (top < 0)
        {
           System.out.println("Stack Underflow");
           return 0;
        }
        else
        {
            char x = a[top--];
            return x;
        }
    }
}
  
  
// Driver code
class Main
{
    //function to reverse the string
    public static void reverse(StringBuffer str)
    {
        // Create a stack of capacity 
        // equal to length of string
        int n = str.length();
        Stack obj = new Stack(n);
         
        // Push all characters of string 
        // to stack
        int i;
        for (i = 0; i < n; i++)
           obj.push(str.charAt(i));
       
        // Pop all characters of string 
        // and put them back to str
        for (i = 0; i < n; i++)
           { 
             char ch = obj.pop();
             str.setCharAt(i,ch);
           }
    } 
      
    //driver function
    public static void main(String args[])
    {
        //create a new string
        StringBuffer  s= new StringBuffer("GeeksforGeeks");
           
        //call reverse method
        reverse(s);
           
        //print the reversed string
        System.out.println("Reversed string is : " + s);
    }
}

Output:

Reversed string is ziuQskeeG


Time Complexity: O(n) where n is number of characters in stack.
Auxiliary Space: O(n) for stack.

A string can also be reversed without using any auxiliary space. Following C and Python programs to implement reverse without using stack.

[ad type=”banner”]

 

Categorized in:

AlgorithmJAVAStack

Tagged in:

, , , , , , , , ,