Reverse a String using a Stack

Last Updated on December 14, 2022 by Prepbytes

Problem Statement

You are given a string, and your task is to reverse the string using a stack data structure.

Input: String.
Output: Reversed string.

Test cases:

Input: “Prepbytes”
Output: “setybpreP”

Explanation:

Reading the input string “Prepbytes” from right to left we get “setybpreP”.
Approach – Using Stack
The idea is to traverse the given string from left to right and push each character in the stack. Then, pop the characters from the stack one by one and append them to a new string. The newly created will be the reverse of the input string because of the LIFO (Last-in-first-out) property of the stack data structure. The last character pushed into the stack will be the first to get popped.

Algorithm

1. Initialize an empty stack and an array.
2. Traverse the given string from left to right
   • Push the current character to the stack
3. Initialize an empty StringBuilder
4. Pop from the stack one by one.
   • Append the current character at last.
5. Return the newly created StringBuilder as a string.

Dry Run:

Code Implementation:

import java.util.*;

public class Prepbytes
{
	public static void main(String[] args) {
		System.out.println(reverseString("Prepbytes"));
	}
	
	public static String reverseString(String str){
	    
	    // Initialize an empty stack.
	    Stack<Character> st = new Stack<>();
	    
	    // Traverse the given string from left to right
	    for(char ch : str.toCharArray()){
	        
	        // Push the current character to the stack.
	        st.push(ch);
	    }
	    
	    // Initialize an empty StringBuilder
	    StringBuilder reverseStr = new StringBuilder();
	    
	    // Pop from the stack one by one.
	    while(!st.isEmpty()){
	        
	        // Append the current character at the last.
	        reverseStr.append(st.pop());
	    }
	    
	    return reverseStr.toString();
	}
}

Output:
setybperP

Time complexity: O(n), where n is the length of the input string. Each character gets pushed and popped from the stack at most once. And it takes constant time to append a character at the end of a StringBuilder.

Space Complexity: O(n). We are using StringBuilder to store the reversed string and it will have n characters.

We tried to discuss Reverse a String using a Stack. We hope this article gives you a better understanding of Reverse a String using a Stack. Prepbytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program that will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.