Check if given string is a palindrome using stack

Question

Folks,

I was recently interviewed and got a question on Palindrome.

Given a string ( which might represent a date ), check if it's a palindrome or not using Stack.

I tried to come up with solution, but he didn't like that.

Can anyone show me the code snippet for it in Java ?

Thanks

PS : This is not a homework, actual interview question.

Answer 1

import java.util.Stack;

public class PalindromeTest {

    public static void main(String[] args) {

        String input = "test";
        Stack<Character> stack = new Stack<Character>();

        for (int i = 0; i < input.length(); i++) {
            stack.push(input.charAt(i));
        }

        String reverseInput = "";

        while (!stack.isEmpty()) {
            reverseInput += stack.pop();
        }

        if (input.equals(reverseInput))
            System.out.println("Yo! that is a palindrome.");
        else
            System.out.println("No! that isn't a palindrome.");

    }
}

Answer 2

The general idea of doing this with a stack is extremely simple. I don't have time to syntax and Java code, but this is the concept in pseudocode.

string s = "test"
for i=0 to s.length
stack->push(s[i])

This would push t->e->s->t from left to right. So the resulting stack would look like this:

TOP -> |t|s|e|t| <- BOTTOM

Now, since the LAST character of the string is on top, you just need to pop until the stack is empty and store it in a string. This will be the reverse of the original string. You can then compare this string with the original, and if it matches you have a palindrome.

In this case you would do:

while(pop != '')
string s += pop'd character

So you would grab t, then s, then e and finally the first t and have s = tset. Comparing this to "test", it is not a palindrome.