Reverse a String using Stack

We have given a string s of length n which contains lower case letters, upper case letters, integers, and some special symbol. Reverse the given string using stack. Let’s see some examples for better understanding.

Example

Input 

s = “TutorialCup”

Output 

puClairotuT

Input

s = “Stack”

Output

kcatS

Using Stack

Algorithm for Reverse a String using Stack

1. Initialize a string of length n.
2. Create a stack of the same size to store the characters.
3. Traverse the string and push each and every character into the stack one by one.
4. Traverse again and start popping the characters out and concatenate them together into a string.
5. Print the reversed string.

Implementation

C++ Program

#include <bits/stdc++.h> 
using namespace std; 
  
class Stack{  
    public: 
        int top;  
        unsigned capacity;  
        char* array;  
};  
  
Stack* createStack(unsigned capacity){
    
    Stack* stack = new Stack(); 
    stack->capacity = capacity;  
    stack->top = -1;  
    stack->array = new char[(stack->capacity * sizeof(char))];  
    return stack;  
}  
  
int isFull(Stack* stack){ 
    return stack->top == stack->capacity - 1; 
}  
  
int isEmpty(Stack* stack){ 
    return stack->top == -1; 
}  
  
void push(Stack* stack, char item){  
    if (isFull(stack))  
        return;  
    stack->array[++stack->top] = item;  
}  
  
char pop(Stack* stack){
    if (isEmpty(stack))  
        return -1;  
    return stack->array[stack->top--];  
}  
  
void reverse(char s[]){  
    int n = strlen(s);  
    Stack* stack = createStack(n);  
  
    int i;  
    for(i = 0; i < n; i++){  
        push(stack, s[i]); 
    }    
  
    for(i = 0; i < n; i++){  
        s[i] = pop(stack);
    }    
}  
  
int main(){  
    char s[] = "TutorialCup";  
  
    reverse(s);  
    cout<<s;  
  
    return 0;  
}

puClairotuT

Java Program

import java.util.*; 
  
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; 
        } 
    } 
} 
  
  
class Main{ 
    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[]){ 
         
        StringBuffer s= new StringBuffer("TutorialCup"); 
          
        reverse(s); 
          
        System.out.println(s); 
    } 
}

puClairotuT

Complexity Analysis

Time Complexity: O(n) where n is the number of characters in the string.

Auxiliary Space: O(n) because we used space in the stack to store n characters.

Without Using Stack

Algorithm for Reverse a String using Stack

1. Initialize a string of length n.
2. Traverse the string till half of it’s the length and swap the character at the current index with character at length – current index – 1 position.
3. Print the string.

Implementation

C++ Program

#include <bits/stdc++.h> 
using namespace std; 
  
void swap(char *a, char *b){  
    char temp = *a;  
    *a = *b;  
    *b = temp;  
}  
  
void reverse(char s[]){  
      
    int n = strlen(s), i;  
  
    for (i = 0; i < n/2; i++)  
        swap(&s[i], &s[n-i-1]);  
}  
  
int main(){  
    char s[] = "animatedworld";  
  
    reverse(s);  
    cout<<s;  
  
    return 0;  
}

dlrowdetamina

Java Program

class stringRev{ 

    static void swap(char a[], int index1, int index2){ 
        char temp = a[index1]; 
        a[index1] = a[index2]; 
        a[index2] = temp; 
    } 
  
    static void reverse(char s[]){ 
    
        int n = s.length, i; 
  
        for(i = 0; i < n/2; i++) { 
            swap(s, i, n-i-1); 
        } 
    } 
  
    public static void main(String[] args){
        
        char s[] = "animatedworld".toCharArray(); 
  
        reverse(s); 
        System.out.printf(String.valueOf(s)); 
        
    } 
}

dlrowdetamina

Complexity Analysis for Reverse a String using Stack

Time Complexity: O(n) where n is the number of characters in the string.

Auxiliary Space: O(1) because we are using constant extra space.

References