Java Coding Challenge - Reverse a String using Stack

Introduction

Reversing a string is a classic coding challenge often asked in technical interviews. One of the most efficient ways to solve this problem is by using a stack. A stack follows the Last In, First Out (LIFO) principle, making it an ideal data structure for reversing elements.

In this blog post, we will discuss how to reverse a string using a stack in Java. We will walk through the implementation using a utility class Stacks, along with code snippets to illustrate each step.

Problem Statement

You are given a string, and your task is to reverse it using a stack.

Example:

• Input: "hello"
• Output: "olleh"

Approach

Steps:

1. Push Characters to Stack: Convert the string into a character array and push each character onto a stack.
2. Pop Characters from Stack: Pop characters from the stack in reverse order and place them back into a character array.
3. Return the Reversed String: Convert the character array back to a string and return it.

Let's walk through the implementation with detailed code snippets.

Java Code

We will use a utility class Stacks to reverse the string. Below is the complete implementation.

1. Create the Stacks Utility Class

package coding.challenge;

import java.util.Stack;

public final class Stacks {

    // Private constructor to prevent instantiation
    private Stacks() {
        throw new AssertionError("Cannot be instantiated");
    }

    // Method to reverse a string using stack
    public static String reverse(String str) {
        // Create a stack to hold characters
        Stack<Character> stack = new Stack<>();

        // Convert the string to a character array and push characters to stack
        char[] chars = str.toCharArray();
        for (char c : chars) {
            stack.push(c);
        }

        // Pop characters from the stack and place them back into the character array
        for (int i = 0; i < str.length(); i++) {
            chars[i] = stack.pop();
        }

        // Return the reversed string
        return new String(chars);
    }
}

Explanation

Step 1: Push Characters to the Stack

In the reverse() method, we first convert the input string into a character array and push each character onto a stack.

char[] chars = str.toCharArray();
for (char c : chars) {
    stack.push(c);
}

• toCharArray(): This method converts the string into an array of characters.
• stack.push(c): This pushes each character onto the stack. As the stack follows the LIFO principle, the last character pushed will be the first one popped.

Step 2: Pop Characters from the Stack

Once all the characters are pushed onto the stack, we start popping them in reverse order. As each character is popped, we place it back into the character array.

for (int i = 0; i < str.length(); i++) {
    chars[i] = stack.pop();
}

• stack.pop(): This method removes and returns the top element of the stack. The first element popped is the last element that was pushed.
• Rebuilding the string: The characters are placed back into the array in reverse order.

Step 3: Return the Reversed String

Finally, we convert the character array back into a string and return the reversed string.

return new String(chars);

Usage Example

Let's test the reverse() method by using it in a Main class.

package coding.challenge;

public class Main {
    public static void main(String[] args) {
        String input = "hello";
        String reversed = Stacks.reverse(input);

        System.out.println("Original String: " + input);
        System.out.println("Reversed String: " + reversed);
    }
}

Output

Original String: hello
Reversed String: olleh

Explanation of Output

• Input: "hello"
• Output: "olleh"

The original string is successfully reversed using a stack. Each character is pushed onto the stack and then popped in reverse order.

Time Complexity

• Pushing to the Stack: O(n), where n is the length of the string, since we iterate over each character to push it onto the stack.
• Popping from the Stack: O(n), as we pop each character from the stack and rebuild the string.
• Overall Time Complexity: O(n), as we process each character twice (once while pushing and once while popping).

Conclusion

In this blog post, we implemented a solution to reverse a string using a stack in Java. We walked through the logic step-by-step, explaining how the stack's LIFO principle helps reverse the order of characters. The approach is simple yet efficient, with a time complexity of O(n), making it ideal for reversing strings of any size.

This solution can be extended for various interview problems that require reversing data or managing ordered collections efficiently.