Reversing a String using Stack

This question provides a really good example of how learning 'tools' is important, but understanding efficiency is better.

The purpose of the task was probably to teach you to use a stack, but there are properties of this challenge which are not well suited to an actual stack solution, and, more importantly, there are other ways of implementing a stack than a Stack object.

Let me make an assertion here: A Stack can be implemented with an array

Now, consider the things we know about this problem.... we know:

• the input is a string
• the output will be a string with the same length
• an array of char (char[]) can be used as the stack

How do you use an array of char as a stack? Well, you add the chars from the input string to an array, and as you do that, you increment the index in the array, so you are 'pushing' to the end, and then you can pop from the end to get the reverse mechanism.

Now, a quick way to create and push the chars from the input, to a stack, is:

char[] stack = input.toCharArray();

Then, a new String can be created with:

char[] reversed = new char[stack.length];
int pos = stack.length - 1;
for (int i = 0; i < stack.length; i++) {
    reversed[i] = stack[pos--]; // pop the stack on to the reversed array
}
return new String(reversed);

This will be significantly faster, it does use a stack, but implemented in an array.

The code look good so far.

The only thing I would change is o use a StringBuilder for the reversed String as String concatenation with + is very inefficient as in your loop the compiler creates the following:

String reversed = "";
// some code
for (int i = 0; i < originalString.length(); i++) {
    char ch = stack.pop();
    StringBuffer tmp = new StringBuffer(reversed);
    tmp.append(ch);
    reversed = tmp.toString();
}
return reversed;

You create a whole lot of objects without any need.

Replace this part of the code with

StringBuffer reverse = new StringBuffer();;
// some code
for (int i = 0; i < originalString.length(); i++) {
    char ch = stack.pop();
    reversedappend(ch);
}
return reversed.toString();

This is much more efficient in time and memory consumption.

Sure, the code is ok, but it's not going to be the fastest way to reverse a string(*) (I'm assuming performance is not the main concern here).

Temporary Variables

You don't really need the two ch variables, you are using them only once, right on the next line. Just write:

stack.push(originalString.charAt(i));
[...]
reversed = reversed + stack.pop();

Naming

• ch is too short, I would name it char.
• reverseString could also be named reverse, it's obvious from the method signature (string in, string out), that it's reversing a string.
• originalString vs reversed: one contains String, one doesn't, this seems inconsistent.

Misc

• remove the additional newlines before closing }.
• reversed = reversed + ch; can be written as reversed += ch; (if you care about performance, use a StringBuilder).

_{(*) just for fun some quick numbers, reversing a string 10k times:}

reverseStack:               187900620 <- your method
reverseStackBuilder:        46680501  <- your method with StringBuilder
reverseBuilder:             20020504  <- new StringBuilder(originalString).reverse().toString()
reverseIt:                  21517253  <-- see http://stackoverflow.com/questions/7569335/reverse-a-string-in-java

@amon wrote a great answer. With Java 8 handling of surrogate pairs is even easier. There is a codePoints() method on the CharSequence interface.

public static String reverseString(String originalString) {
    Stack<Integer> stack = new Stack<>();
    StringBuilder reversed = new StringBuilder();

    originalString.codePoints().forEach(cp -> stack.push(cp));
    while (!stack.empty()) {
        reversed.appendCodePoint(stack.pop());
    }
    return reversed.toString();
}

In a professional project I would expect:

new StringBuilder(originalString).reverse().toString();